Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пример нестандартной машины Тьюринга
|
|
Пусть внешним алфавитом машины Тьюринга будет
А = { а 0, а 1, а 2},
множеством ее состояний -
Q ={ q 1, q 2, q 3, q 4, q 0},
а таблица переходов имеет вид:
Таблица 1 - Пример таблицы переходов нестандартной машины Тьюринга
| аi Q \ { q 0} | а 0 | а 1 | а 2 |
| q 1 | a 2 q 3 l | a 1 q 2 r | a 2 q 1 l |
| q 2 | a 0 q 2 s | a 2 q 1 s | a 1 q 2 s |
| q 3 | a 0 q 0 r | a 1 q 4 r | a 2 q 1 s |
| q 4 | a 1 q 3 s | a 0 q 4 r | a 2 q 4 r |
Рисунок 1 - Диаграмма (граф) переходовдля данной машины
Как работает эта машинa?
1-я (начальная) конфигурация:
Выполненная команда: a2q1l
2-я конфигурация:
Выполненная команда: a2q1l
3-я конфигурация:
Выполненная команда a2q3l
4-я конфигурация:
Выполненная команда a 0 q 0 r
5-я конфигурация:
Заключительное состояние
Так как в пятой конфигурации машина перешла в состояние q0, то слово а2а2а2является результатом и машина остановится.