математическая модель абстрактной вычислительной машины, представляемой в виде бесконечной ленты с пронумерованными ячейками, некоторого управляющего устройства У и некоторого элемента Э, который «обозревает» одну из ячеек ленты, может изменять запись в ячейке, а также сдвигаться на одну ячейку вправо или влево. Функционирование Тьюринга машины полностью определяется исходной информацией, записанной в ячейках ленты, и оператором преобразования, который задан таблицей переходов, записанной в управляющем устройстве. Английский математик Алан Тьюринг теоретически доказал, что при достаточно большой таблице переходов и достаточно большом числе шагов (тактов работы машины) можно решить сколь угодно сложную задачу. Разработка Тьюринга машины стала важным этапом развития теории цифровых ЭВМ и доказала принципиальную возможность решения на такой модели любых алгоритмически решаемых задач.