Некоторые основные отличия между машиной Тьюринга и машиной Поста:

• Алфавит. 3 В машине Тьюринга в каждой ячейке может находиться один из символов некоторого конечного алфавита. 4 В машине Поста алфавит состоит всего из двух символов: 1 и 0, при этом 0 также играет роль пустого символа. 3
• Система команд. 3 В машине Тьюринга есть набор правил перехода, согласно которым действует головка. 3 В машине Поста все команды в программе делятся на 6 типов и пронумерованы. 3
• Назначение. 2 Машина Тьюринга предназначена для решения задач, в которых на ленте записано некоторое входное слово, а нужно получить выходное слово, которое будет результатом решения задачи. 2 Машина Поста работает с задачами, в которых нужно задать программу и её начальное состояние (т. е. состояние ленты и позицию каретки). 2
• Запоминающее устройство. 5 У машины Тьюринга запоминающее устройство представляет собой бесконечную ленту. 5 У реальных вычислительных машин запоминающее устройство может быть как угодно большим, но обязательно конечным. 5