Машина Тьюринга



бет4/4
Дата07.04.2023
өлшемі17.58 Kb.
#471879
түріРеферат
1   2   3   4
Машина Тьюринга

5. Варианты машины Тьюринга


Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.

5.1. Машина Тьюринга, работающая на полубесконечной ленте


В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.

5.2. Двумерные машины Тьюринга


  • Муравей Лэнгтона

Другие абстрактные исполнители и формальные системы вычислений


  • Нормальный алгоритм Маркова (продукционное программирование)

  • Машина Поста (автоматное программирование)

  • Рекурсивная функция (теория вычислимости)

  • Лямбда-исчисление (функциональное программирование)

  • Brainfuck (императивное программирование)


Достарыңызбен бөлісу:
1   2   3   4




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет