Cтраница 4
Теория машин Тьюринга и теория автоматов являются разделами теории алгоритмов. [46]
Рассмотрим машины Тьюринга с двумя входными символами Хг, Х2, двумя выходными символами Zb Z2 и двумя внутренними состояниями Qi, Q2 - Сколько разных таблиц полностью описывают всевозможные такие машины. Сколько разных таблиц неполностью описывают их. Существуют ли эквивалентные машины среди тех, которые описываются полными таблицами. Существуют ли эквивалентные машины среди тех, которые описываются неполными таблицами. [47]
Изучение машин Тьюринга представляет большой интерес с точки зрения теорий алгоритмов. [48]
Лента машины Тьюринга моделируется массивом Т со счет чиком / ( сначала его значение равно 0), указывающим поза цию головки машины Тьюринга. [49]
Понятие машины Тьюринга интересно, как уже отмечалось, тем, что в нем / понятие алгоритма уточняется в терминах общей теории вычислительных машин. Таким образом, это уточнение может считаться лишь косвенным и довольно. [50]
Объем машины Тьюринга полагается равным числу команд, определяющих машину. За один шаг вычисления принимается сдвиг ленты на один квадрат ( влево или вправо), или один акт печати, или одно стирание. [51]
Работа машины Тьюринга протекает следующим образом. Дальнейший процесс протекает уже автоматически и однозначным образом определяется функциональной схемой машины. [52]