Вопрос 12. Машина Тьюринга. Способы задания машины Т. Конфигурация. Тезис Тьюринга.
Определение: МТ — это алгоритмическая модель представляющая собой некоторое идеализированное устройство. Существует наиболее распространенные 3 типа универсальных моделей: 1) детерминированные устройства: МТ , машина Поста (процедурное программирование); 2) рекурсивные функции, 3) формальные системы.
МТ состоит из 3-х частей: 1) Управляющее устройство которое может находиться в одном из состояний qi принадлежащему конечному множеству состояний Q={q1, q2, …, qn}; 2) лента I — разбитая на ячейки в каждой из которых мажет быть записан один из знаков некоторого алфавита V={a0, a1,…, am}, причем лента бесконечна в обе стороны; 3) устройство доступа к ленте которое в каждый дискретный момент времени обозревает одну ячейку и может считывать или записывать туда любой из знаков алфавита V, а также перемещать ленту влево или вправо.
Замечание: предполагается, что существует знак e (не путать с пустой строкой), которым заполнена лента с начала до конца, и только в конечном количестве ячеек находятся знаки алфавита V.
МТ функционирует следующим образом: 1) считывается некоторый знак aj находящийся в текущей ячейке ленты. В зависимости от считываемого знака aj и текущего состояния устройства управления qi в ячейку ленты записывается некоторый знак aj| . 2) В зависимости от считанного знака aj и текущего состояния qi устанавливается новое текущее состояние qi| . 3) В зависимости от текущего считанного знака aj и текущего состояния qi лента перемещается в некоторое направление dk ? D = {L,R,E} . 4) С приходом следующего дискретного момента времени (следующий такт), последовательность функционирования повторяется.
Формальное определение МТ — называется формальная система состоящая из следующих объектов (или множеств) T=<V,Q,P,I>, где V — внешний алфавит обязательно включающий e, Q- внутренний алгоритм, Q={qz, q1, q2, …, qn} (qz — обозначает заключительное состояние). P — программа МТ является дискретной функцией отображающей декартовое произведение Q ? V ? Q ? V ? D, где D -множество направлений перемещения ленты, I — начальная конфигурация МТ, это строка начинается с qi , после которого начинается подстрока внутреннего алфавита. I = qi ? ; qi ? Q ; ? ? V*.
3 способа задания МТ: 1) табличный — достаточно задать 1 таблицу ; 2) в виде ориентированного графа (вершины соответствуют состояниям Q, дуги командам программы состояний из 6-ти знаков qiaj ? qi| aj| dk ); 3) задание МТ в виде строки знаков.
Выводы: Так как язык не пустой существует хотя бы одна МТ. Количество МТ счетно. Решима проблема распознавания правильных описаний МТ.
Конфигурацией МТ называется строка следующего вида K=A1qiA2, где qi -принадлежит множеству внутренних состояний МТ, а A1 и A2 — строки алфавите V*. Можно выделить стандартную начальную и заключительную конфигурации : I = q0?2 (слева от устройства доступа находится пустая строка) ; z = qz? (справа от устройства доступа находится результирующая строка).
Функционирование МТ заключается в смене ее конфигурации в каждый дискретный момент времени. Последовательность конфигураций в которой находится МТ называется работой машины Т.
Тезис Тьюринга: Любой алгоритм может быть реализован МТ. Если некоторую процедуру нельзя реализовать МТ, то эта процедура не алгоритм.