Машина на Тюринг
Машина на Тюринг (MT) е абстрактна изчислителна машина за изпълнение на програми, предложена от английския математик Алън Матисън Тюринг през 1936 г. Описано по-долу детерминирана машина на Тюринг. Има обобщения от него - вж. вероятностна машина на Тюринг (и също недетерминирана машина на Тюринг).
Съдържание
[редактиране] Състав на MT
MT се състои от устройство за управление (каретка или глава за четене и запис) и лента, разделени на секции (клетки) и безкрайни в двете посоки. Всяка клетка на лентата може да съдържа всеки знак от последната азбука, включително интервал. В една стъпка каретата може да прочете и напише азбучния знак на мястото, където стои, и да премести една позиция наляво или надясно или да остане на мястото си. Устройството за управление може да бъде в едно от многото състояния. Броят на възможните състояния на управляващото устройство е краен и точно определен. Устройството за управление работи съгласно правилата за скок (командни редове), които представляват алгоритъма (програмата). Специфична програма за MT се определя чрез изброяване на елементите от набора от букви на азбуката, набора от състояния и набор от правила, по които MT работи. Има точно едно правило за всяка възможна конфигурация. Няма правила само за крайното състояние, след като колата спре. MT операцията се определя от програма, състояща се от краен брой командни редове.
[редактиране] Типове команди:
- изместване надясно
- лява смяна
- останете на място
- писане на азбучен знак в клетка
- отидете в състояние от набор
н - броят на състоянията на устройството за управление без окончателно;
Q = 0, q1, q2, ..., qn> - набор от състояния на устройство за управление с крайно състояние (q0);
к - броят на знаците в азбуката;
s1 - номер на състоянието, в което е управляващото устройство преди изпълнението на командата;
s2 - номер на състоянието, в което управляващото устройство преминава след изпълнението на командата;
R - изместване надясно;
М - оставане на място.