Я думаю, что путаница может возникнуть из-за того, что вы используете «шаги» вместо «состояний». Вы можете думать о состоянии машины как о значении, которое она имеет в своей памяти (хотя, как отмечалось ранее, некоторые люди также принимают состояние машины, чтобы включить содержимое ленты - однако, я не думаю, что определение уместно на ваш вопрос). Возможно, что это изменение в терминологии может быть причиной вашего замешательства. Позвольте мне объяснить, что я думаю, что вы думаете. :)
Вы дали списки из пяти чисел - например, (1,0,1,1,2). Как вы правильно заявили, это следует интерпретировать (читая слева направо) как «Если машина находится в состоянии 1 И текущий квадрат содержит 0, выведите 1, переместитесь вправо и перейдите в состояние 2». Однако использование вами слова «шаг», по-видимому, предполагает, что после «шага 2» должен следовать «шаг 3» и т. Д., Когда на самом деле машина Тьюринга может перемещаться между состояниями (и, конечно, может быть только конечное число возможных состояний).
Итак, чтобы ответить на ваши вопросы:
- Машины Тьюринга отслеживают «состояния», а не «шаги»;
- То, что вы описали, является законной машиной Тьюринга;
- Более простой (хотя и неинтересный) механизм Тьюринга будет запускаться в состоянии HALT.
Редактирует: грамматику, форматирование и удаляет ненужное описание машин Тьюринга.
Ответ на комментарий :
Поправьте меня, если я неверно истолковываю ваш комментарий, но я не имел в виду, что машина Тьюринга может находиться в нескольких состояниях одновременно, только то, что число возможных состояний может быть любым конечным числом. Например, для машины с тремя состояниями вы можете пометить возможные состояния A, B и C. (В приведенном вами примере вы пометили два возможных состояния как «1» и «2»). В любой момент времени точно одно из этих значений (состояний) будет в памяти машины. Мы бы сказали: «машина находится в состоянии A» или «машина находится в состоянии B» и т. Д. (Ваша машина запускается в состоянии «1» и завершает работу после того, как она переходит в состояние «2»).
Кроме того, мне больше не понятно, что вы имеете в виду под «более простой». Самая маленькая известная универсальная машина Тьюринга (то есть машина Тьюринга, которая может имитировать другую машину Тьюринга при наличии соответствующей ленты) требует 2 состояния и 5 символов (см. соответствующую статью Википедии ).
С другой стороны, если вы ищете что-то более простое, чем машина Тьюринга с той же вычислительной мощностью, машины после Тьюринга могут представлять интерес.