304
правки
Изменения
м
→Варианты машины Тьюринга: примеры других эквивалентных формализмов
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
=== Другие эквивалентные вычислительные формализмы ===
Существуют также другие формализации понятия алгоритма, которые по вычислительным возможностям эквивалентны машинам Тьюринга:
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|клеточные автоматы]]
== Универсальная машина Тьюринга ==
