Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
4. Машину Тьюринга можно определить посредством множества пятерок вида
(<7й 5/> Sk, qlt 6m),
таких, что если машина, находясь в состоянии qu обозревает символ Sj, то она пишет символ Sh, переходит в состояние qi и перемещает головку способом бщ, где бm принимает одно из трех значений:
— 1 : сдвиг влево;
О : отсутствие сдвига;
+ 1 : сдвиг вправо.
Переформулировать изложенные выше фрагменты теории машин Тьюринга и конкретные примеры тьюринговых вычислений, используя такой вариант определения машины.
5. Построить машину Тьюринга, которая вычисляла бы следующую функцию:
sue (де) = X + 1.
6. Выписать вычисления, реализующие вычитания 3—2 и 2—3 в машине, описанной в п. 4.3.3.
7. Построить машину Тьюринга, которая вычисляла бы і-ю проекцию и-ки натуральных чисел:
иТ\х„ X2.....хп) = X1, 1
8. Построить машину Тьюринга, которад вычисляла бы функцию х — у, определенную следующим образом:
х- у = х — у, если X ^ у,
х — у = 0, если х<у.
9. Построить машину Тьюринга, которая вычисляла бы ту же функцию х-2-у, но при этом на каждом шаге вычисления окаймляла непустую часть ленты маркерами.
10. а) Построить машину Тьюринга, которая вычисляла бы произведение (х + I) (у + 1). б) Изменить эту машину так, чтобы она на каждом шаге вычисления окаймляла непустую часть ленты маркерами. Глава V
ВЫЧИСЛИМОСТЬ И РАЗРЕШИМОСТЬ
В настоящей главе читатель найдет некоторые понятия, связанные с вычислимостью и разрешимостью; эти понятия оказываются необходимыми, поскольку они связаны с теорией формальных грамматик.
Во многих случаях, чтобы не перегружать изложение и лучше выделить основную линию рассуждений, мы вынесли в упражнения технические детали доказательств.
§ 5.1. ИСЧИСЛЕНИЕ ФУНКЦИЙ
Пример с вычитанием (п. 4.3.3), по-видимому, ясно показывает, что для вычисления даже простых функций могут понадобиться очень сложные машины Тьюринга. Чтобы избежать необходимости строить такие машины непосредственно, можно воспользоваться композицией элементарных стандартных машин подобно тому, как программа для ЭВМ составляется из элементарных программ.
5.1.1. Сочленение и стандартизация
Для достижения только что указанной цели мы будем использовать следующие средства.
Различение состояний. Когда некоторая машина Тьюринга строится из нескольких готовых машин, нужно уметь отличать состояния результирующей машины от состояний составляющих ее машин (каждая из них может иметь, например, состояние qi). Для этого мы примем следующее соглашение.
Если Z— машина Тьюринга, то через Z(™> обозначается аналогичная машина, все состояния которой получаются из состояний машины Z путем увеличения их индексов на п. (Таким образом, мы переходим от Z к Z(™> с помощью точно такой же операции, которая используется в программировании для ЭВМ: в машину вводится подпрограмма, первая команда которой помещается в ячейку с адресом п.)
Стандартная машина. При композиции машин Тьюринга необходимо, чтобы результаты вычислений, полученных одной машиной, могли служить исходными данными для другой машины. Для этого целесообразно ввести так называемое стоп-со стояние. 82
Часть /. Предварительные сведения из логики и алгебры
Мы уже приняли соглашение, что любая машина начинает любое вычисление в состоянии qi. Аналогично будем предполагать, что любая машина заканчивает вычисления в таком состоянии qB, что 0 есть наибольший из индексов, приписываемых символам внутренних состояний машины, и при этом ни одна из ситуаций машины Z не допускает состояния q6.
Машина, снабженная стоп-состоянием, является по определению стандартной машиной.
Чистка. Напомним, что результат тьюрингова вычисления — это число палочек, оказавшихся на ленте машины в конце ее работы. Однако алфавит машины может содержать символы, отличные от пробела и палочки. Поэтому, чтобы результат работы одной машины мог служить «входным заданием» для другой, необходимо сгруппировать все палочки вместе, а затем стереть все прочие символы.
Маркировка. Когда машина Тьюринга «изучает» свои исходные данные (которые могут быть результатом работы предыдущей машины), возникает опасность бесконечного протягивания ленты. Чтобы избежать этого, всякая стандартная машина Z преобразуется в другую стандартную машину Z', которая выполняет те же вычисления, что и Z, но, кроме того, обрамляет любой результат двумя специальными маркерами — левым и правым. Построению подобных машин для отдельных частных случаев были посвящены некоторые упражнения в конце предыдущей главы. Общий случай рассматривается в упр. 5.1.2.
Сохранение промежуточных результатов. Поскольку при композиции машин Тьюринга они не всегда сочленяются линейно, может оказаться необходимым сохранять в ходе вычислений некоторые промежуточные результаты. Подобное запоминание также может быть выполнено с помощью маркеров.
Более точно, если машина Z ставит в соответствие заданию (di, ..., d{) результат (ги ..., г,-), то можно построить такую машину Z1, которая ставила бы в соответствие заданию (рi, ..., рн, di, ..., di) результат (ри ..., ри, ги ..., п).
