26
правок
Изменения
Нет описания правки
* <tex>N \in Q</tex> — отвергающее состояние автомата,
* <tex>S \in Q</tex> — стартовое состояние автомата,
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата.
}}
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.
|id=conf
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где * <tex>q \in Q</tex> — текущее состояние автомата, а * <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки до первого пробельного символа соответственно.
}}
В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>v = \varepsilon</tex>).
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:
[[Файл:Mt3.jpgpng]]
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые Стековые машины]]* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые Счётчиковые машины]]* [[Линейный клеточный автомат, эквивалентность МТ|клеточные Клеточные автоматы]]* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные Произвольные формальные грамматики]]* [[Лямбда-исчисление|нетипизированное Нетипизированное лямбда-исчисление]]
== Источники информации ==
