11. Сравните машины Тьюринга и Поста.

Обе машины — абстрактные модели исполнителя алгоритмов с лентой и строго заданными командами. У машины Тьюринга есть головка, которая читает и записывает символы, перемещается по ленте и действует в зависимости от текущего состояния и прочитанного символа. В машине Поста лента представляется ячейками, в которых может быть отметка или её отсутствие; команды предписывают проверять ячейку, ставить или стирать отметку и переходить к другой команде. Модели устроены по-разному, но обладают одинаковой вычислительной мощностью.