Доказательство окончено. АЛГОРИТМИЧЕСКАЯ РАЗРЕШИМОСТЬ

АЛГОРИТМИЧЕСКАЯ РАЗРЕШИМОСТЬ

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

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

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

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

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

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

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

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

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

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

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

РАЗРЕШИМЫЕ МНОЖЕСТВА

Пусть A - некоторое подмножество множества N^k. Характеристической функцией множества A называется функция c(x₁, ... , x_k), определяемая соотношением:

c(x₁, ... , x_k) = .

ОПРЕДЕЛЕНИЕ

Множество A называется разрешимым множеством, если его характеристическая функция является вычислимой.

Очевидно, что разрешимость множества A означает существование алгоритма, который для произвольного элемента aÎN^k за конечное число шагов работы дает ответ на вопрос о принадлежности a множеству A.

Пример. Множество {n|n - четное число} является рекурсивным множеством, поскольку имеет рекурсивную характеристическую функцию f(x) = (mod(x, 2)).

Здесь mod(x, 2) -функция остатка от деления x на 2.

Упражнение. Пусть A и B разрешимые подмножества множества N^k. Показать, что множества A È B, A Ç B и N^k \ A также являются разрешимыми.

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

Увеличим числовые представления всех возможных решений задачи на 1. Это позволяет выделить 0 из множества решений задачи в качестве специального значения.

Произвольной задаче T поставим в соответствие множество

D_T= {(a, b) | ((b ¹ 0) & (решение задачи T для начальных данных a равно b)) Ú ((b = 0) & (решение задачи T для начальных данных a не существует))}.

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

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

1.Пусть для T имеется разрешающий алгоритм A. Тогда для проверки принадлежности пары (a, b) множеству D_T достаточно применить A к начальному данному a и сравнить полученное решение c со значением b-1.

2.Пусть D_TÍ N². Тогда нахождение решения T для начального данного a состоит в проверке того, что (a, 0) ÏD_T. Если проверяемое условие имеет место, то решение задачи T существует и может быть найдено последовательной проверкой выполнения условия (a, i) Î D_T для i = 1, 2, . . . , выполняемой до тех пор пока не будет найдена пара (a, b) Î D_T , озгачающая, что решение T на начальных данных a равно b-1.

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

ПРОБЛЕМА ОСТАНОВКИ

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

Сформулированная задача называется проблемой остановки. Переформулируем эту проблему в терминах разрешимости множеств.

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

Начальные данные для программы Pбудем представлять натуральными числами. Тогда можно считать, что программа с текстом P вычисляет одноместную числовую функцию
f: N ® N, совпадающую с некоторой функцией f_i(x) из последовательности (3), содержащей все одноместные вычислимые числовые функции.

Определим множество:

R₁ = {(m, n) | значение f_m(n) определено}.

Нетрудно видеть, что если существует алгоритм, который по произвольной программе P и некоторому начальному данному d для этой программы определяет, заканчивается ли вычисление программы P на d или нет, то множество R₁ является разрешимым.

Покажем, что множество R₁ не является разрешимым. Из этого будет следовать неразрешимость проблемы остановки.

ТЕОРЕМА 8.4

Множество R₁ неразрешимое.

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

Предположим противное. Пусть характеристическая функция множества R₁: (x₁, x₂)= является вычислимой.

Поскольку - вычислимая, то вычислима и функция

g(x) = (x, x).

Определим вспомогательную функцию:

d(x) = .

Функция d называется диагональной. Для каждого значения своего аргумента, равного x, она определена тогда и только тогда, когда значение f_x(x) не определено.

То есть d отлична от любой функции последовательности (3) всех одноместных частично-рекурсивных функций.

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

Следовательно, d должна совпадать с одной из функций в последовательности всех одноместных частично-рекурсивных функций (3).

Полученное противоречие означает, что предположение о разрешимости множества R₁ является неверным.

Следовательно, R₁ - это неразрешимое множество.