Диагональная конструкция

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

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

Воспользуемся "диагональной конструкцией" точно так же доказывается несчетность множества всех бесконечных десятичных дробей. Пусть U произвольная вычислимая всюду определенная функция двух аргументов. Рассмотрим диагональную функцию u(n) = U(n,n). Очевидно, на аргументе n функция u совпадает с функцией U_n, а функция d(n) = u(n) + 1 отличается от U_n. Таким образом, вычислимая всюду определенная функция d(n) отличается от всех сечений U_n, и потому функция U не является универсальной.

Почему это рассуждение не проходит для класса всех вычислимых функций (в том числе частичных)? Дело в том, что значение d(n) = U(n,n) + 1 теперь не обязано отличаться от значения U_n(n) = U(n,n), так как оба они могут быть не определены.

Тем не менее, часть рассуждения остается в силе.

Теорема 9. Существует вычислимая функция d (с натуральными аргументами и значениями), от которой никакая вычислимая функция f не может всюду отличаться: для любой вычислимой функции f найдется такое число n, что f(n) = d(n) (последнее равенство понимается в том смысле, что либо оба значения f(n) и d(n) не определены, либо оба определены и равны).

По существу все уже сказано: такова диагональная функция d(n) = U(n,n) (здесь U вычислимая функция двух аргументов, универсальная для класса вычислимых функций одного аргумента). Любая вычислимая функция f есть U_n при некотором n и потому f(n) = U_n(n) = U(n,n) = d(n).

Теорема 10. Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.

Такова, например, функция d'(n) = d(n) + 1, где d функция из предыдущей теоремы. В самом деле, любое ее всюду определенное продолжение всюду отличается от d (в тех местах, где функция d определена, функция d' на единицу больше d и потому любое продолжение функции d' отличается от d; там, где d не определена, любая всюду определенная функция отличается от d).

19. Докажите, что и сама функция d из доказательства предыдущей теоремы не имеет вычислимого всюду определенного продолжения.

3 Типы алгоритмических моделей. Операторы суперпозиции и рекурсии.

Некоторые дополнительные требования приводят к неформальному определению алгоритма:

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

2. Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

3. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

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

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

· алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий;

· алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

· алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.

Алгоритмический объект (АО) - данные, для преобразования которых используется алгоритм. Для формального определения АО фиксируют конечный алфавит символов (цифр, букв и т.п.) и определяют правила построения АО (синтаксические правила).

Процесс преобразования алгоритмических объектов в ходе выполнения алгоритма осуществляется дискретно, т.е. пошагово. Последовательность шагов детерминирована, т.е. после каждого шага указывается точно, что и как следует выполнять на следующем шаге.

Процесс преобразования АО, включающий в себя заданную последовательность шагов, называют алгоритмическим процессом (АП).

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

Выделяют три основных типа алгоритмических моделей:

1) рекурсивные функции — связывает понятие алгоритма с элементарными вычислительными операциями на множестве целых положительных чисел;

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

3) нормальный алгоритм Маркова — связывает понятие алгоритма с элементарными преобразованиями слов произвольного алфавита, замещая части или всего слова другим словом.

Дата добавления: 2015-10-24