Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Описание работы машины Тьюринга
|
|
Описание можно представить в виде: q n a m → a s (L или R или S) q k ; q1 – начальное состояние машины, q0 – конечное состояние (останов МТ), a0- символ пробела (пустая клетка).
Набор таких правил (программу) для МТ обычно представляют в виде таблицы, например:
| a0 | a1 | a2 | |
| q1 | a2 L q3 | a1 R q2 | a2 L q1 |
| q2 | a0 S q2 | a2 S q1 | a1 S q2 |
| q3 | a0 R q0 | a1 R q4 | a2 S q1 |
| q4 | a1 S q3 | a0 R q4 | a2 R q4 |
Эта машина может находиться в 5-ти состояниях – q0, q1, q2, q3, q4, а её алфавит состоит из трёх символов а0, a1 и a2. Заметим, что хотя бы одна ячейка таблицы должна содержать символ q0 – иначе МТ никогда не остановится.
Покажем, как работает эта МТ, если на входе у неё задана последовательность символов a0, a2, a2, a0, причём МТ в начальный момент обозревает второй символ справа – a2 и находится в состоянии q1.
1 шаг (исходная позиция)
| а0 | а2 | а2 | а0 |
↑ q1
2 шаг
| а0 | а2 | а2 | а0 |
↑
q1
3 шаг
| а0 | а2 | а2 | а0 |
↑
q1
4 шаг
| a0 | a2 | а2 | а2 | а0 |
↑
q3
5 шаг
| a0 | a2 | а2 | а2 | а0 |
↑ q0 (stop).
Экспериментальный пример работы машины Тьюринга
Пусть той же МТ предъявлена на входепоследовательность символов a0, a1, a1, a2, a2, a0 и МТ обозревает второй справа символ a2 и находится в состоянии q1.
1 шаг (исходная позиция)
| a0 | a1 | a1 | а2 | a2 | a0 |
↑ q1
2 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
↑ q1
3 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
↑
q1
4 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
↑ q2
5 шаг
| a0 | a1 | a1 | а1 | a2 | a0 |
↑ q2
6 шаг
| a0 | a1 | a1 | a2 | a2 | a0 |
↑ q1
На 6 шаге полностью повторилась конфигурация 2 шага, т.е.
произошло «зацикливание» работы МТ. Вывод: для такого исходного набора данных МТ никогда не остановится.
Устройство и работа машины Тьюринга по заданной программе удовлетворяют всем требованиям, предъявляемым к работе по заданному алгоритму.
Единственное замечание – возможность «зацикливания» конкретной МТ.
Тезис Чёрча – Тьюринга
Сходство работы МТ и выполнения
некоторого алгоритма позволило сформулировать знаменитый тезис Чёрча – Тьюринга, суть которого можно выразить следующим образом: «Для любого алгоритма можно построить машину Тьюринга, которая его реализует». Этот тезис нельзя доказать, поскольку нет формального, строгого определения алгоритма. Но его можно опровергнуть, если удастся привести пример алгоритма, для которого нельзя задать реализующую его МТ. До настоящего времени таких примеров построить не удалось. Наряду с машиной Тьюринга существует аналогичное «устройство» - машина Поста. Эти машины эквивалентны в том смысле, что алгоритм, который реализуем на МТ, может быть реализован и на машине Поста. Более того, в соответствии с тезисом Чёрча-Тьюринга, работа любого компьютера может быть воспроизведена на соответствующей МТ.
|
|