Нормальные алгорифмы Маркова
Машина Тьюринга
Алан Тьюринг[4] предложил математическую абстрактную систему, которая может показать, разрешима алгоритмически задача или нет.
В конструкции машины Тьюринга имеется:
1) бесконечная лента, разбитая на ячейки,
2) каретка (считывающе-запоминающее устройство), которая:
2)1) обозревает одну ячейку,
2)2) считывает символ из ячейки ленты,
2)3) записывает на место считанного символа новый,
2)4) перемещается вдоль ленты.
В процессе работы машины Тьюринга выполняются следующие команды:
1. считывается условие обозреваемой ячейки,
2. считывается символ,
3. каретка находится в состоянии, соответствующем символу,
4. записывается вместо считываемого символа новый,
5. изменяется, если необходимо, состояние,
6. каретка передвигается.
Эмиль Леон Пост тоже предложил подобные конструкции. Тезис Поста: «Любой алгоритм представим в форме машины Поста».
Андрей Андреевич Марков[5] создал нормальные алгорифмы, которые описывались как система подстановочных операций.
Определение алгорифма состоит из:
алфавита алгорифма, к словам в котором алгорифм будет применяться,
схемы алгорифма.
Схемой нормального алгорифма называется конечный упорядоченный набор формул.
Пусть заданы:
- алфавит А= 
,
- P и Q – слова в алфавите А,
- выражение P Q – простая формула подстановки слов в алфавите А,
- выражение P Q – заключительная формула подстановки,
- конечный список формул подстановки.
P1 () Q1 Алгорифм, определенный таким образом,
P2 () Q2 называется нормальным алгорифмом в
P3 () Q3 алфавите А.
………………………
Pm () Qm
………………………
Pr () Qr
МНР – машина с неограниченным числом регистров. С помощью нее исследуют нынешние устройства.
X. АЛГОРИТМ И ЕГО СВОЙСТВА
Алгоритм – способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат, однозначно определяемый исходными данными.
АЛГОРИТМ–ALGORITHM
конечный набор предписаний, определяющий решение задачи посредством конечного количества операций.
Пример: полная формулировка последовательности арифметических операций, с помощью которых производят вычисление синуса с заданной точностью.
СТ ИСО 2382/1-84
Свойства алгоритма: дискретность, элементарность шагов, определенность (результативность), конечность, массовость.
Способы представления алгоритмов:
1. на естественном языке(словесное представление);
2. на псевдокоде, например, на школьном алгоритмическом языке;
3. в виде структурограммы Насси-Шнейдермана;
4. в виде схемы (блок-схемы, графической схемы алгоритмов (ГСА) в соответствии с ГОСТ 19.701-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения»);
5. на языке программирования (в виде программы).
Исполнитель алгоритмов – это объект или субъект, исполняющий алгоритмы. Исполнитель-объект исполняет алгоритмы формально. Он характеризуется системой команд, средой, в которой исполняет алгоритмы, и отказами. Отказы: исполнитель сообщает «не понял», если получил команду не входящую в его систему команд; исполнитель сообщает «не могу», если получил команду, которую он не может исполнить по какой-либо причине.
В XVI – XVII вв. основным методом доказательства в математике был алгебраический подход (т.е. представление математических алгоритмов в виде текста).
Лейбниц обратил внимание на то, что в разных областях математики используется небольшой набор символов для доказательства теорем. Отсюда ученый выдвинул предположение: нельзя ли сделать универсальный набор. Попытка сделать машину оказалась неуспешной.
В конце XIX в. задача сформировалась по-другому: построить алгоритм проверки правильности теоремы при заданной аксиоме. Построить такие алгоритмы не удалось. Тогда было выдвинуто предположение: возможно ли вообще построить алгоритм для решения какого-либо класса задач. Если невозможно, то математики ищут то, чего нет. Возникло понятие «алгоритмически неразрешимой» задачи. Чтобы прекратить поиски решения задачи, которая возможно алгоритмически неразрешима, нужно математически строго доказать факт отсутствия соответствующего алгоритма. Это возможно в том случае, если существует строгое определение алгоритма. Попытки разработать определение алгоритма привели к появлению в 20 – 30 гг. теории алгоритмов.
Для построения формального алгоритма необходимо свести разнообразие объектов и действий к представлению текста.
Любой алфавит можно заменить любым другим алфавитом.
25 ноября