Алгоритмические машины
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
та машины происходит в нашем воображении. Следовательно, машины Тьюринга вовсе не машины в обычном смысле, а скорее тексты на некотором языке, что вполне соответствует нашему интуитивному представлению об алгоритме.
Возникает вопрос, является ли алгоритмом работа любой машины Тьюринга? В их поведении есть много общего: все, что они умеют, сводится к достаточно простым операциям поиска текущей команды, преобразования, входного символа в выходной, изменения внутреннего состояния и нахождения следующего входного символа. Эти операции носят настолько регулярный, механический характер, что их вполне можно описать в виде единственной программы для подходящей машины универсальной машины Тьюринга.
Идея универсальной машины заключается в имитации работы любой конкретной машины Тьюринга. С этой целью в памяти универсальной машины должны храниться программа работы и образ имитируемой машины, включающий информацию как о содержимом ее памяти с указанием на текущий входной символ, так и о текущем состоянии.
На первый взгляд, это кажется невозможным, ведь множество всех имитируемых машин бесконечно. Но тексты на любых языках можно зашифровать (закодировать) с помощью единственного, например цифрового алфавита. Сделать это, очевидно, нужно так, чтобы можно было достаточно просто различать образ машины от ее программы, символы от состояний и т.п. В этом случае программа работы универсальной машины Тьюринга сводится к выполнению системы несложных действий.
В образе конкретной машины ищутся коды первого символа и начального состояния. По ним в зашифрованном тексте программы находится нужная команда, несущая информацию о тех изменениях, которые нужно произвести в образе машины. После их совершения коды нового состояния и следующего символа позволяют отыскать следующую команду и т.д. Этот процесс, называемый интерпретацией, продолжается до тех пор, пока не будет достигнуто конечное состояние. В этом случае в памяти универсальной машины окажется код выходного слова имитируемой машины Тьюринга.
В воображаемом устройстве универсальной машины использованы важные идеи, нашедшие позднее воплощение в особенностях конструкции и работы настоящих ЭВМ. В первую очередь, это работа по программе, представляющей собой символическую запись алгоритма на языке, понятном для исполнения не очень сложным устройством. Во-вторых, это наличие запоминающего устройства для хранения как исходной, промежуточной и конечной информации, так и самой программы. Память реальных ЭВМ всегда конечна, но это ограничение становится несущественным в современных ЭВМ, обладающих весьма большой памятью. Наконец, это возможность имитации работы любых специализированных устройств обработки информации на одной универсальной конструкции.
6. Нормальные алгоритмы Маркова
Кратко остановимся на третьем подходе к уточнению (конкретизации) понятия алгоритма. По смыслу оно близко к идеям Тьюринга, однако, в нем не используются представления о каких-либо машинах. Алгоритм задается системой подстановок, которые указывают, какие замены символов необходимо производить и в каком порядке эти подстановки должны следовать. Такой подход был предложен А.А.Марковым. В начале 50-х годов прошлого столетия было введено понятие нормального алгоритма (сам Марков называл их алгорифмами).
Вновь рассмотрим некоторый алфавит A, содержащий конечное число знаков (букв). Введем ряд определений:
Слово это любая конечная последовательность знаков алфавита.
Число символов в слове называется его длиной.
Слово, длина которого равна нулю, называется пустым.
Слово s называется подсловом слова q, если q можно представить в виде q= rst, где r и t любые слова в том же алфавите (в том числе и пустые).
Теперь можно определить понятие алгоритма (не являющееся строгим):
Алгоритмом в алфавите A называется эффективно вычислимая функция, областью определения которой служит какое-либо подмножество множества всех слов в алфавите A и значениями которой также являются слова в алфавите A.
В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите A построено исходное слово P, которое содержит подслово Pr (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Pk в том же алфавите.
Подстановкой называется замена первого по порядку подслова Pr исходного слова P на слово Pk. Обозначается подстановка Pr>Pk.
Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в P, то первая из них применяется к P, в результате чего оно переходит в другое слово P1. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Pn, либо при получении Pn была применена последняя подстановка.
Библиографический список
- Авдеев Р.Ф. Философия информационной цивилизации [Текст] / Р.Ф. Авдеев. М.: ВЛАДОС, 2008.
- Булгаков И.С. Счетные машины [Текст] / И.С. Булгаков. М.: Машгиз, 2010.
- Винер Н. Человек управляющий [Текст] / Н. Винер. СПб.: Питер, 2009. 288 с.
- Гутер Р.С. От абака до компьютера [Текст] / Р.С. Гутер, Ю.Л. Полунов. М.: Знание, 2009.
- Ершов Ю.Л. Математическая логика [Текст] / Ю.Л. Ершов, Е.А. Палютин. М.: Наука, 2008.