Пример работы машины Тьюринга

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.

Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q2 (команды которого совпадают с командами q1 предыдущей программы).

1.5. Современная теория алгоритмов

Начальной точкой отсчета современной теории алгоритмов можно считать теорему о неполноте символических логик, доказанную немецким математиком Куртом Геделем в 1931 г. В этой работе было показано, что некоторые математические проблемы не могут быть решены алгоритмами определенного класса.

Общность результата Геделя связана с вопросом о том, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном понимании этого термина. Эта работа дала толчок к поиску и анализу различных формализаций понятия алгоритм.

Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930-х гг. Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс рекурсивно-вычислимых функций Черча были первыми формальными описаниями алгоритма, опирающимися на строго определенные модели вычислений. Сформулированные гипотезы Поста и Черча-Тьюринга постулировали эквивалентность предложенных ими моделей вычислений, как формальных систем, и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство существования алгоритмически неразрешимых проблем.

В 1950-х гг. существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и основанный на теории формальных грамматик алгоритмический формализм Маркова – так называемые нормальные алгоритмы Маркова. Формальные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой.

Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели в 1960-1970-х гг. к практически значимым исследованиям алгоритмов и вычислительных задач. На этой основе впоследствии выделилось несколько разделов теории алгоритмов.

Классическая теория алгоритмов: формулировка задач в терминах формальных языков; понятие задачи разрешения; описание сложных классов задач. Авторы теории: Эдмондс, Бен-Ор, Янов, Котов и др.

Теория асимптотического анализа алгоритмов: понятие сложности и трудоемкости алгоритма; критерии оценки алгоритмов; методы получения асимптотических оценок, в частности, для рекурсивных алгоритмов. В развитие этой теории существенный вклад внесли Кнут, Ахо, Хопкрофт, Ульман, Карп, Мошков, Кудрявцев и др.

Теория практического анализа вычислительных алгоритмов: получение явных функций трудоемкости; интервальный анализ функций; практически значимые критерии оценки качества алгоритмов; методики выбора рациональных алгоритмов. Основополагающей работой в этом направлении является фундаментальный труд Д.Кнута «Искусство программирования для ЭВМ».

Методы создания эффективных алгоритмов включают в себя множество алгоритмов, среди которых динамическое программирование, метод ветвей и границ, метод декомпозиции, специальные структуры данных и пр.

Обобщая исследования в различных разделах теории алгоритмов, можно выделить следующие основные задачи и направления развития, характерные для современной теории алгоритмов:

1. формализация понятия «алгоритм» и исследование формальных алгоритмических систем (моделей вычислений);

2. доказательство алгоритмической неразрешимости задач;

3. формальное доказательство правильности и эквивалентности алгоритмов;

4. классификация задач, определение и исследование сложности классов;

5. получение методов разработки эффективных алгоритмов;

6. исследование и анализ рекурсивных алгоритмов;

7. получение явных функций трудоемкости алгоритмов;

8. разработка классификаций алгоритмов;

9. исследование емкостной (по ресурсу памяти) сложности задач и алгоритмов;

10. разработка критериев сравнительной оценки ресурсной эффективности алгоритмов и методов их сравнительного анализа.

Поиск по сайту: