Машина Тьюринга – это теоретическая модель вычислений, предложенная Аланом Тьюрингом в 1936 году. Она представляет собой абстрактное устройство, состоящее из: 1. Бесконечной ленты: Лента разделена на ячейки, каждая из которых содержит один символ из конечного алфавита. Лента может быть как бесконечной вправо, так и вправо и влево, но важно, чтобы она была бесконечной в каком-то направлении. 2. Головки чтения/записи: Головка может двигаться по ленте влево или вправо, читать символ в текущей ячейке, записывать в неё другой символ и изменять своё состояние...

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