Графическое представление команд машины Тьюринга.

Построим МТ, распознающую язык{aⁿbcⁿ}. Представлять МТ будем подобно конечному автомату с помощью графа переходов, в котором каждой команде <(q,x(®)p,y,D)> соответствует ребро, направленное из вершины, помеченной состоянием q в вершину, помеченную состоянием р. Само ребро помечено входным символом х, выходным символом у и направлением движения головки D (рис.5.2). Это и есть графическое представление команды машины Тьюринга.

Пример реализации машины Тьюринга.

Наращиваемую память в современных ЭВМ можно считать аналогом бесконечной в одну сторону рабочей ленты машины Тьюринга. Причём достаточно только пяти типов команд чтобы реализовать операции машины Тьюринга: 1)сдвиг{влево,вправо}–Сдвиг головки на 1 позицию на ленте влево или вправо; 2)переход,р– Безусловный переход к команде с номером р. 3) если,s,р– Условный переход к команде с номером р, если в обозреваемой ячейке находится символ s;4)печать, s– Печать символа sв обозреваемую ячейку; 5)стоп– Остановка.

Например, начало программы машины Тьюринга, которая находит НОД, имеет вид:

00: если, а, 02;{если в начальном состоянии прочитан символа, то на команду 02}

01: переход, 05;{если нет, то на проверку другого символа}

02: печать, а;

03: сдвиг, влево;

04: переход,00;{возврат в начальное состояние}

05: если, b, 07; {если в начальном состоянии прочитан символ b,

то на команду 07}

06:переход, 10; {если нет, то на проверку другого символа}

07:печать,b;

08:сдвиг,влево;

09:....

Машина Поста.

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из : 1)бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак); 2)головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: i K j,, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд: 1)V j - поставить метку, перейти к j-й строке программы; 2)X j - стереть метку, перейти к j-й строке программы;3)<- j - сдвинуться влево, перейти к j-й строке программы; 4) -> j - сдвинуться вправо, перейти к j-й строке программы; 5)? j₁; j₂ - если в ячейке нет метки, то перейти к j₁-й строке программы, иначе перейти к j₂-й строке программы; 6)! – конец программы (стоп).

У команды «стоп» отсылки нет.

Варианты окончания выполнения программы на машине Поста: 1)Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма;2)Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми);3)Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга.Машина Поста имеет лишь два различных символа (есть метка, нет метки). Т.к любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.

Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2 ? 1;3
3 <- 4
4 V 5
5 !

Алгоритм Маркова.

Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг полым языком (т.е. исполнителем на котором можно реализовать любую вычислимую функцию), что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал. Нормальным алгоритмом Маркова (НАМ) называется непустой конечный упорядоченный набор формул подстановки: α₁ → β₁, α₂ → β₂,…, α_k → β_k.( k ≥ 1 ). В этих формулах могут использоваться два вида стрелок: обычная стрелка (→), обычная формула, и формула со стрелкой «с хвостиком» – заключительная формулой.

Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Это можно изобразить так: .

Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления. Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.

Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М.

Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N.

Например, в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb.

Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.

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

Способы композиции нормальных алгоритмов: 1)Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В. Результат суперпозиции С может быть представлен в виде С(р) = В(А(р));

2) Объединение алгоритмов. Объединением алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(р) и В(р); 3)Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если С(р) = е, где е - пустая строка; 4)Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова р соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Рекурсивные функции.

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

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

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

Совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций, называется совокупность рекурсивных функций.

Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определимых в некоторой формальной системе. Исходя из совершенно других предпосылок, Черч в 1936 г. вывел тот же класс числовых функций, что и Гёдель. Черчем была сформулирована гипотеза. Числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна. Эта гипотеза известна под именем тезиса Черча. Понятие вычислимой функции точно не определяется, поэтому тезис Черча доказать нельзя. Клини ввел понятие частично рекурсивной функции и высказал гипотезу: что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Гипотеза Клини также недоказуема, как и гипотеза Черча. Однако математические исследования последних 30 лет выявили полную целесообразность считать понятие частично рекурсивной функции научным эквивалентом интуитивного понятия вычислимой частичной функции.

[1]