![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
a0 | a1 | a2 | |
q1 | а0Пq1 | a1Пq1 | a2Лq2 |
q2 | а1Пq2 | a2Нq0 | a0Нq0 |
Таким образом, машина Тьюринга может быть представлена в виде четверки:
(4.9)
Работа машины Тьюринга:
Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии
, считывает входной символ
и по таблице работы совершает операцию сдвига
, переходя в состояние
, при этом входное слово
заменяется на
:
Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние
недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.
ПРИМЕР
Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.
Внешний алфавит - . Внутренний алфавит -
, при этом состояние
.сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние
- стирание последней единицы. При этом следует заметить, что ситуация
в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например
. Начальное состояние
на начале последовательности единиц. Рабочая программа машины Тьюринга имеет вид:
![]() | ![]() | |
![]() | ![]() | ![]() |
![]() | ![]() | ![]() |
Проверим работоспособность машины Тьюринга:
1.
2.
3.
4.
5.
Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.
Дата публикования: 2014-11-03; Прочитано: 332 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!