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

Машину Тьюринга можно представлять в виде некоторого автоматически действующего устройства, которое может находиться в конечном числе внутренних состояний и которое снабжено бесконечной внешней памятью – лентой. Среди состояний имеются два выделенных – начальное и заключительное. Лента разделена на клетки (ячейки) и не ограничена влево и вправо. В каждой клетке ленты может быть записан любой из символов, входящих в некоторый заранее заданный перечень (ради единообразия считают, что в пустой клетке записана «пустая буква»). В каждый (дискретный) момент времени машина Тьюринга находится в одном из своих состояний и, рассматривая (посредством специального устройства) одну из клеток ленты, воспринимает записанный в ней символ. Если в текущий момент времени машина Тьюринга находится в незаключительном состоянии, то в следующий за ним момент: она переходит в новое состояние, быть может совпадающее со старым или заключительное; в рассматриваемой клетке старый символ заменяется новым, может быть пустым или совпадающим со старым; лента машины Тьюринга сдвигается на одну клетку влево или вправо либо остаётся на месте. Этот шаг машины Тьюринга вполне определяется её текущим состоянием и текущим воспринимаемым символом. Таблица, содержащая полное перечисление возможных шагов данной машины Тьюринга, называется программой этой машины.

Текущее полное описание машины Тьюринга даётся её конфигурацией, которая состоит из указания для данного момента следующей информации: конкретного заполнения клеток ленты символами; клетки, находящейся в поле зрения машины; состояния, в котором машина находится.

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

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