Машина Тьюринга

Лента используется для хранения информации. Она бесконечна в обе стороны и разбита на клетки, которые никак не нумеруются и не именуются. В каждой клетке может быть записан один символ или ничего не записано. Содержимое клетки может менятся – в нее можно записать другой символ или стереть находящийся там символ.
Пустое содержимое клетки договорились называть символом «пусто» и обозначать знаком Λ. В связи с этим изображение ленты, показанное на рисунке справа, такое же, как на рисунке слева. Данное соглашение удобно тем, что операцию стирания символа в некоторой клетке можно рассматривать как запись в эту клетку символа , поэтому вместо длинной фразы «записать символ в клетку или стереть находящийся там символ» можно говорить просто «записать символ в клетку».