Untitled

Состоит из головки и бесконечной ленты:

  1. Головка считывает и записывает;
  2. Бесконечная лента разбита на ячейки, каждая ячейка содержит символ из алфавита $A = \{ a_{0}, a_{1}, a_{2}, ..., a_{n} \}$, где $a_{0}$ - пробел или пустота.

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

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