Изменения
'''Машина Тьюринга''' (МТ) — это абстрактная вычислительная машина для выполнения программ, предложенная английским математиком Аланом Мэтисоном Тьюрингом в 1936 году.
== Состав МТ ==
МТ состоит из управляющего устройства (каретки или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны.
Правил нет только для заключительного состояния, попав в которое машина останавливается.
Работа МТ определяется программой, состоящей из конечного числа командных строк.
== Виды команд: ==
* сдвиг вправо
* запись символа алфавита в ячейку
* перейти в состояние из множества
Введём обозначения:
'''M''' — оставание на месте.
== Виды командных строк: ==
'''s<sub>1</sub>a<sub>1</sub>s<sub>2</sub>a<sub>2</sub>M''' — при считывании символа '''a<sub>1</sub>''' в состоянии '''s<sub>1</sub>''' записать символ '''a<sub>2</sub>''', перейти в состояние '''s<sub>2</sub>''' и остаться на месте;
* работа может закончиться если система переходит в терминальное (конечное) состояние;
* работа никогда не закончится (т.е.программа составлена не корректно).
== Пример задачи ==
[[файл:МТ11.JPG]], где '''x''', '''y''' - неотрицательные целые числа.
=== Программа для МТ ===
[[файл:МТ12.JPG]]
=== Таблица для программы ===
[[файл:МТ13.JPG]]
Введём обозначения:
'''1<sup>x+1</sup>λ1<sup>y+1</sup>''' — набор значений аргументов '''(x,y)'''.
Входные данные: '''1<sub>1</sub>1λ1'''.
Выходные данные: '''λ<sub>0</sub>λλλλ1'''.
Входные данные: '''1<sub>1</sub>λ111'''.
Выходные данные: '''λ1<sub>0</sub>11'''.
* Заметим, что [[машина Поста]] во многом аналогична машине Тьюринга.
== Ссылки ==
* Википедия
* [[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Алгоритмы]]
