Из интуитивного понятия алгоритма ясно, что вычисления в соответствии с некоторым алгоритмом производятся чисто механически; их можно поручить машине. Процесс, происходящий в такой машине, должен обладать свойствами алгоритми­ческого процесса, он должен идти в дискретном времени, должен быть направленным на получение определенного результата; машина должна быть полностью детерминированной и допускать ввод различных исходных данных для рассматриваемого класса задач.

Рассмотрим один из вариантов машины Тьюринга. Остановимся на элементах машины. Внешняя память— конечная лента, разбитая на конечное число ячеек одинаковой длины. В процессе работы справа от существующих ячеек машина может пристраивать новые ячейки, так что лента может считаться потенциально неограниченной в правом направлении. В каждой ячейке ленты может быть записан один из конечного множества символов a₁, …, a_m. Ячейка, не содержащая ни одного из этих символов, называется пустой. Все вновь пристраиваемые ячейки пристраиваются пустыми. Для обозначения пустой ячейки используют специальный символ a₀ (или 0). Если в ячейке записан символ a_i, говорят, что ячейка находится в состоянии a_i.

Совокупность символов a₀, a₁, …, a_m называется внешним алфавитом машины.

Считывающая и записывающая головка — устройство, которое в каждый определенный момент вре­мени располагается напротив некоторой ячейки ленты,  называемой обозреваемой, или воспринимаемой ячейкой. По командам, поступающим из управляющего устройства, головка может стереть символ, записанный в обозреваемой ячейке, и записать новый, а также может передвинуться вправо или влево вдоль ленты на одну ячейку.

Управляющее устройство—вырабатывает команды, поступающие на головку. В свою очередь с головки на вход управляющего устройства поступает символ обозреваемой ячейки. Управляющее устройство может находиться в одном из конечного числа состояний, обозначаемых какими-либо символами, не входящими во внешний алфавит машины, например: q₀, q₁, …, q_n. Совокупность этих символов называется внутренним, алфавитом машины, а состояние управляющего устройства называется состоянием, внутренней памяти. Одно из этих состояний называется заключительным, в это состояние внутренняя память приходит по окончании работы машины; символ, обозначающий заключительное состояние, назы­вается стоп-символом. Управляющее устройство работает в дискретном времени; команды, вырабатываемые управля­ющим устройством в i-м такте работы, определяются символом обозреваемой ячейки и состоянием внутренней памяти. В результате выполнения команд к началу (i+1)-го такта работы может быть изменен символ обозреваемой ячейки, записывающая головка может быть передвинута вправо или влево, а также может быть изменено состояние внутренней памяти.

Состоянием машины Тьюринга¹⁵, или ее конфигурацией, называется совокупность, образованная последовательностью символов состояний ячеек ленты

a, ,…, , символом состояния внутренней памяти q_j и номером k воспринимаемой ячейки. Совокупность всех этих данных можно записать с помощью машинного слова

, ,… q_j… .

Каждое машинное слово содержит лишь одно вхождение символа q_j из внутреннего алфавита. Этот символ записывается слева от обозреваемой ячейки. Очевидно, что работу машины Тьюринга можно представить как последовательное преобразование машинных слов в соответствии с некоторой программой. Цель работы машины - преобразование слова, записанного на ленте. Для того чтобы «запустить» машину, надо поместить ее головку напротив нужной ячейки и привести внутреннюю память машины в исходное состояние.

Преобразование машинного слова по данной программе в каждом такте работы определяется состоянием воспринимаемой ячейки и состоянием внутренней памяти. По окончании выполнения программы внутренняя память машины проходит в заключительное состояние, и машина останавливается. В результате исходное машинное слово a, … q_j… перерабатывается в некоторое заключительное слово. Однако в некоторых случаях машина не проходит в заключительное состояние; в этих случаях говорят, что данная программа (данная машина) не применима к слову a, … q_j… .

Назовем алфавитом произвольное конечное множество букв; например, русский алфавит: а, б, в, ..., я, или внутренний алфавит машины Тьюринга q0, q1, …, qn. Буквы рассматриваются как целые неделимые символы. Например, в алфавите a₁, a₂, …, a_m буквой является a_i но не а и не i в отдельности. Произвольная последовательность букв называется словом. Словом в данном алфавите называется каждое слово, все буквы которого принадлежат этому алфавиту. Например, слова окно, хлеб, ааабу, щщььсс—слова в русском алфавите; машинное слово - слово в алфавите a₁, a₂, …, a_m,  q₀, q₁, …, q_n

Пусть символы А, В, С, D обозначают слова, записанные в алфавите, не содержащем этих символов. Тогда слово А называется подсловом слова В, если В можно представить в виде В = CAD, где С, D — подходящие слова (возможно пустые, т. е. не содержащие ни одной буквы). Говорят также, что «слово А входит в В». Например, слово q_j входит в машинное слово, т.е. является его подсловом. Пусть Е — какое-либо слово; тогда слово CED называют словом, полученным из слова В = CAD подстановкой вместо слова А слова Е.

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

или

или

.

Выполнение этих команд означает изменение символа обозреваемой ячейки, изменение состояния внутренней .памяти и соответственно сдвиг головки влево, вправо и отсутствие сдвига. Команды этого вида называются подстановочными командами. Совокупность всех команд, определяющая работу машины, называется ее программой. Команды могут быть записаны также в ином виде с использованием символов Л, П, С, означающих сдвиг головки влево или вправо или сохранение ее положения до начала следующего такта. Например, команда

q₂a₃q₂a₄П

означает изменение символа воспринимаемой ячейки, сох­ранение состояния внутренней памяти и сдвиг головки вправо.

Работа машины в данном такте по условию полностью определяется состоянием внутренней памяти q_j и симво­лом воспринимаемой ячейки a_i, поэтому для каждой пары q_j, a_i (j = 1, ..., n; i = 0 1, ... m) программа машины содержит одну и только одну команду, начинающуюся словом q_ja_i. Программа не содержит команд, начинаю­щихся словом q₀a_i, где q₀ — символ, означающий заклю­чительное состояние машины.

Далее мы ограничимся рассмотрением машин с внешним алфавитом, состоящим из двух символов 0 (для обоз­начения пустых ячеек) и 1. Произвольное натуральное число х будем записывать на ленте в виде последовательности х+1 единиц

Эту последовательность будем обозначать как 1^x+1. При такой записи число ноль обозначается одной единицей, а пустые ячейки используются для разделения чисел на ленте. Поскольку любой алгоритм может быть сведен к алгоритму вычисления целочисленной функции, то дво­ичный внешний алфавит позволяет построить машину Тьюринга, реализующую любой алгоритм.