Общая теория алгоритмов

Необходимость нумерации произвольных объектов вызвана, прежде всего, необходимостью анализа различных задач, которые должны обрабатывать
алгоритмы в качестве исходной информации.
Следовательно, для
того, чтобы рассматривать алгоритмы над алгоритмами, необходимо представлять
алгоритм (в данной главе — машину Тьюринга) в виде натуральных чисел.

Геделевская нумерация объектов
Считается, что введена система Геделевской нумерации для всех объектов A, принадлежащих некоторому множеству M, если выполняются следующие два требования:
существует натуральное число ng(A), которое однозначно определяется по A;
для всех n, принадлежащих множеству натуральных чисел N, выполняется одно из двух условий:
либо не существует объекта A, принадлежащего множеству M, такого, что n = ng(A);
либо существует единственный объект A, принадлежащий M, такой, что n =ng(A) и этот объект однозначно восстанавливается по n.

Геделевский номер машины Тьюринга

любая машина Тьюринга задается набором команд
каждой команде ставится в соответствие одно число
всему набору команд — одно длинное число, полученное последовательной записью соответствующих каждой команде чисел.
Для однозначного определения такого длинного числа будем формировать его из отдельных чисел в возрастающей последовательности. Очевидно, что оба требования определения Геделевской нумерации выполняются при предложенном способе кодирования машин Тьюринга в виде натурального числа.
По тезису Тьюринга каждый алгоритм может быть реализован машиной Тьюринга. Возможность нумерации машин Тьюринга означает, что любой вычислимой функции можно поставить в соответствие ее номер.
Возникает вопрос: все ли функции вычислимы? Другими словами, необходимо выяснить существование функций, не вычислимых никакими алгоритмами.
Геделевский номер машины Тьюринга

Все ли функции вычислимы?

Все ли функции вычислимы?

Проблема остановки машины Тьюринга
Проблема остановки алгоритма заключается в определении для произвольного алгоритма и произвольных исходных данных, поступающих на вход этому алгоритму, принципа обработки указанным алгоритмом предложенных исходных данных:
остановится алгоритм через некоторое конечное число шагов с полученным в процессе работы результатом;
не остановится никогда.
Теорема 5.1. Проблема остановки неразрешима.
Доказательство. Допустим, что проблема разрешима. Это значит, что существует алгоритм решения данной проблемы, т.е. существует машина Тьюринга, решающая эту проблему. Эта машина Тьюринга должна получать на вход алгоритм и исходные данные для него и выдавать на выход "да" или "нет" в зависимости от того, остановится или зациклится алгоритм на этих данных. Такая машина Тьюринга должна действовать следующим образом:
Легко построить машину Тьюринга, которая копирует исходные данные:

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

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

Алгоритмически неразрешимые проблемы

Алгоритмически неразрешимые проблемы
Теорема 5.2 (Теорема Райса). Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.

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

Понятие Марковской подстановки
Алгоритм M исходное слово P в алфавите A перерабатывает в слово Q: M: P ⇒ Q
Марковская подстановка - операция над упорядоченной парой слов (P,Q). В заданном слове R находят первое вхождение слова Р (если оно есть) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (P,Q) к слову R. Если же нет вхождения P в слово R, то считается, что марковская подстановка (P,Q) не применима к слову R.

Нормальный алгоритм Маркова:

Примеры алгоритмов Маркова
Примеры. А={a,b}. Схема алгоритма
а->ε.
b->b.
Заменяет в слове первое вхождение буквы ‘a’ на пустую цепочку. Если в слове только ‘b’, то оставляет его без изменения.
Заменить последнее вхождение буквы ‘a’ на пустую цепочку.
А={a,b}, B={#,&}
#a->a#
#b->b#
#->&
a&->ε.
b&->&b
&->ε.
ε->#

Вычислимость функций по Маркову
Функция f, заданная на множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение B алфавита A и такой нормальный алгоритм в В, что каждое слово P в алфавите А, принадлежащее области определения функции, перерабатывается алгоритмом в f(P).
Примеры нормально вычислимых функций: x+1, x/3, 2x, (2x+3y)/4.

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

Эквивалентность алгоритмических моделей
Глава 5, стр.121

Эквивалентность алгоритмических моделей
Будем использовать машины Тьюринга в качестве основной модели и докажем эквивалентность всех трех определений алгоритма на основе доказательства четырех теорем:
для любой машины Тьюринга можно построить эквивалентную частично–рекурсивную функцию;
для любой частично–рекурсивной функции можно построить эквивалентную машину Тьюринга;
для любой машины Тьюринга можно построить эквивалентный алгоритм Маркова;
для любого алгоритма Маркова можно построить эквивалентную машину Тьюринга.
Следствием из этих теорем является эквивалентность алгоритмов Маркова и частично–рекурсивных функций.

Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций
Теорема 5.3. Всякая частично–рекурсивная функция вычислима по Тьюрингу.
Доказательство. В соответствии с рекурсивным определением частично–рекурсивной функции для доказательства теоремы достаточно доказать следующие четыре утверждения:
простейшие функции вычислимы по Тьюрингу;
с помощью оператора суперпозиции из вычислимых по Тьюрингу функций получаем вычислимые функции;
с помощью оператора минимизации из вычислимых по Тьюрингу функций получаем вычислимые функции;
с помощью оператора примитивной рекурсии из вычислимых по Тьюрингу функций получаем вычислимые функции.
Вычислимость простейших функций очевидна, так как легко построить соответствующие машины Тьюринга. Теорема о вычислимости суперпозиции была доказана выше (см. теорему 2.6). Рассмотрим оператор минимизации

Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Доказательство (продолжение)
Рассмотрим теперь поведение машины Тьюринга T по тактам и введем функции, являющиеся (кроме уже известных элементов четверки ) еще и функцией номера такта t:
Все эти функции можно определить рекурсивно.
Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Доказательство (продолжение)
Приведенные рекурсивные схемы соответствуют так называемой параллельной рекурсии.
Пусть в начальный момент на ленте записана цепочка x. В конечный момент
результатом является некоторая цепочка y, которая представляет собой функцию от исходных данных: y = f(x).
Рассмотрим эту функцию. В начальный момент при условии правильной работы машины Тьюринга имеем
Функция зеркального отображения числа является примитивно–рекурсивной в силу следующего определения.
Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Доказательство (продолжение)
По определению правильной вычислимости перед началом работы машина Тьюринга находится в начальном состоянии (q = 0), на ленте имеется исходная цепочка x, головка обозревает первый символ цепочки x
Тогда значение y = f(x) определяется при условии правильной вычислимости по формуле:
Машина Тьюринга переходит в заключительное состояние и завершает работу на таком шаге tend, когда ее текущее состояние окажется заключительным:
Тогда y = f(x) — суперпозиция частично–рекурсивных и примитивно–рекурсивных функций, следовательно, сама является частично–рекурсивной функцией .
Теорема об эквивалентности Машин Тьюринга и
частично–рекурсивных функций

Теорема об эквивалентности машин Тьюринга и
алгоритмов Маркова

Теорема об эквивалентности машин Тьюринга и
алгоритмов Маркова

Теорема об эквивалентности машин Тьюринга и
алгоритмов Маркова

Теорема об эквивалентности машин Тьюринга и
алгоритмов Маркова