Связь машин Тьюринга и грамматик типа 0

Докажем, что язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется грамматикой типа 0. Для доказательства части "если" мы построим недетерминированную машину Тьюринга, которая будет недетерминированно выбирать выводы в грамматике и смотреть, является ли вывод входом. Если да, машина допускает вход.

Для доказательства части "только если" мы построим грамматику, которая недетерминированно генерирует представления терминальной строки и затем симулирует машину Тьюринга на этой строке. Если строка допускается некоторой Tm, строка конвертируется в терминальные символы, которые она представляет.

Теорема 2.4. Если L генерируется грамматикой типа 0, то L распознается машиной Тьюринга.

Доказательство. Пусть - грамматика типа 0 и L = L(G). Опишем неформально недетерминированную машину Тьюринга Tm, допускающую L.

где

Предполагается, что последние три символа не входят в .

Вначале Tm содержит на входной ленте . Tm вставляет # перед w, сдвигая все символы w на одну ячейку вправо, и#S# после w, так что содержимым ленты становится #w#S#.

Теперь Tm недетерминированно симулирует вывод в G, начиная с S. Каждая сентенциальная форма вывода появляется попорядку между последними двумя #. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с w. Если они совпадают, Tm допускает.

Формально, пусть Tm имеет на ленте #w#A₁A₂...A_k#. Tm передвигает недетерминированно головку по A₁A₂...A_k, выбирая позицию i и константу r между 1 и максимальной длиной левой части любого правила вывода в P. Затем Tm проверяет подстроки A_iA_i+1...A_i+r-1. Если A_iA_i+1...A_i+r-1 - левая часть некоторого правила вывода из P, она может быть заменена на правую часть. Tm может сдвинуть A_i+rA_i+r+1...A_k# либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от r.

Из этой простой симуляции выводов в G видно, что Tm печатает на ленте строку вида в точности, если . Если y = w, Tm допускает L.

Теорема 2.5. Если L распознается некоторой машиной Тьюринга,то L генерируется грамматикой типа 0.

Доказательство. Пусть допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из и затем симулирует поведение Tm на одной из копий. Если Tm допускает слово, то G трансформирует вторую копию в терминальную строку. Если Tm не допускает L, товывод никогда не приводит к терминальной строке.

Формально, пусть

, где

Продукции таковы:

1.

2. для каждого

3.

4.

5.

6. для каждого и каждого и такого, что

7. для каждого C, J, I из , a и b

8. для каждого .

Используя правила 1 и 2

где для некоторого

Предположим, что Tm допускает строку a₁a₂ ... a_n. Тогда для некоторого m Tm использует не более, чем m ячеек справа от входа. Используя правило 3, затем правило 4 m раз, и наконец, правило 5, имеем

Начиная с этого момента могут быть использованы только правила 6 и 7, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в никогда не меняются. Индукцией по числу шагов Tm можно показать, что если

, то

где a₁, a₂, ... a_n принадлежат , a_n+1 = a_n+2 = ... a_n+m = e,

X₁ X₂, ...X_n+m принадлежат и X_S+1=X_S+2=...X_n+m=B

Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для k - 1 шагов. Пусть

за k шагов. По предположению индукции

Пусть E = L, если j₂ = j₁ - 1 и E = R, если j₂ = j₁ + 1. В этом случае D(q₁, X_j1 ) = (q₂, Y_j1, E).

По правилам 6 или 7

в зависимости от того, равно ли E значению R или L.

Теперь X_i = Y_i для всех .

Таким образом,

что доказывает предположение индукции.

По правилу 8, если , легко показать, что

Таким образом, G может генерировать a₁a₂ ... a_n, если a₁a₂ ... a_n допускается Tm. Таким образом, L(G) включает все слова, допускаемые Tm. Для завершения доказательства необходимо показать, что все слова из L(G) допускаются Tm. Индукцией доказывается, что только если w допускается Tm.