Принцип работы машины Тьюринга 

все просто! Ввод, вывод и память в машине тюринга представляют собой ленту, разделенную на ячейки. в каждой ячейке или символ или она пустая. ПРОЦЕССОР МАШИНЫ СПОСОБЕН ЗА ОДИН РАЗ РАССМОТРЕТЬ ТОЛЬКО ОДНУ ИЗ ЯЧЕЕК. ОН МОЖЕТ СТЕРЕТЬ СИМВОЛ В ЭТОЙ ЯЧЕЙКЕ, ЗАПИСАТЬ ДРУГОЙ, ПЕРЕМОТАТЬ ЛЕНТУ ВПЕРЕД-НАЗАД НА НЕСКОЛЬКО ЯЧЕЕК.