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

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

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

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