Что такое машина Алана Тьюринга?

Машина Тьюринга — абстрактный исполнитель (абстрактная вычислительная машина), предложенная Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. ru.ruwiki.ru ru.wikipedia.org

В состав машины Тьюринга входит неограниченная в обе стороны лента, разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения), способное находиться в одном из множества состояний. ru.ruwiki.ru

Управляющее устройство может перемещаться влево и вправо по ленте, оставаться в неподвижном положении, читать и записывать в ячейки символы некоторого конечного алфавита. ru.ruwiki.ru

Машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам перехода преобразует входные данные с помощью последовательности элементарных действий. ru.ruwiki.ru