Алгоритмическая разрешимость

Доказательство окончено.

Доказательство

ТЕОРЕМА 8.3

Существует универсальная функция для F ¹.

Определим функцию h (n, x) = f_n (x).

Покажем, что эта функция является вычислимой. Для этого сформулируем интуитивно понятный алгоритм вычисления значений функции h.

Пусть (n, x) - произвольная пара чисел. Выполним следующие действия:

1. По номеру n функции f_n найдем код D_n дерева, определения функции g_n.

2. По найденному коду построим само такое дерево D g _n.

3. По дереву D_n найдем дерево D f_n для функции f_n.

Для этого изменим разметку вершин в D_k, выполнив отождествление переменных. В результате получим дерево D, представляющее схему рекурсивного определения f_n.

4. По схеме рекурсивного определения f_n вычислим значение y = f_n (x).

5. Закончим вычисление, взяв в качестве результата значение h (n, x) = y.

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

Нетрудно убедиться, что " n (h (n, x) = f_n (x)).

Следовательно, h является универсальной функцией.

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

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

При этом для всякой задачи может иметь место один из следующих двух случаев:

1. Алгоритм решения задачи существует.

2. Разрешающего алгоритма нет.

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

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

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

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

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

Для доказательства разрешимости или неразрешимости конкретных задач удобно использовать понятие разрешимого множества.

Дата добавления: 2015-03-31