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

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

Работа машины Тьюринга

Машина Тьюринга имеет неограниченную вправо и влево ленту, разделённую на ячейки с определёнными символами. С помощью управляющего устройства, которое читает и записывает символы, устройство перемещаться вправо и влево по ленте , читая и записывая символы в ячейки заранее определённого ей алфавита.

Управляющее устройство работает согласно правилам , которые представляют определённый алгоритм. Каждое правило прописывается для машины до её запуска. Указания для машины Тьюринга обрабатываются с помощью символов на ленте, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, машина может записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Для остановки машины Тьюринга вводятся специальные символы.

Детерминированная и недетерминированная

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

Недетерминированной машина , является если существует 2 и более команд и состояний машины , поэтому решение может иметь несколько вариантов развития и результата.