Третий такт. Обозревается палочка из соседней ячейки справа
(сдвиг П), при состоянии Q2. Результат: знак ¦ заменен знаком _2b с переходом к команде НQ1 и т.д...
Из последнего столбца функциональной схемы видно, что останов- ка машины произойдет лишь при условии, что на некоторой стадии
процесса возникнет состояние Q_45. Действительно, каков бы ни был обозреваемый знак, он не будет заменен никаким другим, и машина будет продолжать обозревать его (сдвиг Н) при том же состоянии
Q_45. Это и есть стоп-состояние, сигнализирующее о результативном завершении процесса в том случае, когда машина применима к инфор- мации, поданной в нее до запуска.
По существу функциональной схемой может пользоваться и чело- век, для которого функциональная схема представляет некоторый
стандартный способ задания алгоритма преобразования исходных дан- ных, записанных во внешнем алфавите, в соответствующий результат, записанный в том же алфавите. Фактически мы так и поступили с функциональной схемой, приведенной выше, сознавая при этом, что машина Тьюринга сделала бы то же самое.
Итак, функциональная схема представляет собой некоторый стан- дартный способ задания алгоритма для машины Тьюринга (схематичес- кую запись тьюринговой программы)_2. А тьюрингова программа - спи- сок всех команд, реализующих алгоритм для машины Тьюринга. Каждая команда имеет вид: xq-->x'Pq', где x и q - название строки и столбца в функциональной схеме, а x'Pq'- тройка, расположенная на их пересечении. Естественно, эта команда выполняется так: если на данном такте символ _2x обозревается в состоянии _2q, то нужно его заменить символом _2x', а к началу следующего такта нужно совершить сдвиг _2P (например: Вправо, если _2P=П) и обозревать его в состоянии
_2q' символ, который попадает в поле зрения.
Таким образом, функциональную схему, приведенную выше, мы мо- жем записать и как последовательность команд. Тогда программа для машины Тьюринга (не функциональная схема!) будет иметь вид:
_1.1
^Q1_2 --_2> _2 ^ПQ4 аQ3_2 --_2> _2 ¦ЛQ3
¦Q1_2 --_2> _2 аНQ2 bQ3_2 --_2> _2 ^ЛQ3 аQ1_2 --_2> _2 аЛQ1 ^Q4_2 --_2> _2 ^НQ5
bQ1_2 --_2> _2 bЛQ1 ¦Q4_2 --_2> _2 ¦ЛQ1
^Q2_2 --_2> _2 ^ЛQ3 аQ4_2 --_2> _2 ^ПQ4
¦Q2_2 --_2> _2 bНQ1 bQ4_2 --_2> _2 ¦ПQ4 аQ2_2 --_2> _2 аПQ2 ^Q5_2 --_2> _2 ^НQ5
bQ2_2 --_2> _2 bПQ2 ¦Q5_2 --_2> _2 ¦НQ5
^Q3_2 --_2> _2 ^ПQ1 аQ5_2 --_2> _2 аНQ5
¦Q3_2 --_2> _2 ¦ПQ1 bQ5_2 --_2> _2 bНQ5
_1.5
_2§3. Реализация алгоритмов в машине Тьюринга.
_2Примеры алгоритмов
Рассмотрим ряд примеров и покажем как строятся тьюринговы ма- шины, реализующие некоторые простые арифметические алгоритмы, и
- 12 - как происходит в машине процесс реализации этих алгоритмов; под построением машины мы будем подразумевать построение функциональ- ной схемы ее логического блока, которая и представляет собою не- которую стандартную форму записи алгоритма. Кроме того, мы расс- мотрим общие соображения о методике построения тьюринговых машин
(функциональных схем).
_23.1. Алгоритм увеличения натурального числа на 1.
Дана десятичная запись числа n; требуется указать десятичную
запись числа n+1. Для этого берется внешний алфавит, состоящий из десяти цифр (0,1,2,3,4,5,6,7,8,9) и пустого знака ^.
Машина может пребывать лишь в двух состояниях: q0 (рабочее состояние) и Стоп (остановка).
Заданное число n, а также результирующее число n+1 будут запи- саны в десятичной системе, причем цифры будут помещаться по одной в ячейке ( ячейки следуют подряд одна за другой без пропусков ).
_3Функциональная схема:
_1.0
+-------------------------+
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.