Лекции - Теория алгоритмов

Подождите немного. Документ загружается.

(продолжение)

► Что при этом произойдет? Возможно, вообще

нет числа

с условием

g(x

,...,x

,y)=0

. Тогда

не произойдет остановки машины с выдачей

Однако отсутствие

возможно по другой

причине. Предположим, например, что

g(x

,...,x

,5)=0,

, а значение

g(x

,...,x

,2)

не определено. Пытаясь вычислить

g(x

,...,x

,2)

машина будет работать

бесконечно и никогда не перейдет к

вычислению

g(x

,...,x

,3).

Поэтому число

y=5

не будет обнаружено.

Оператор минимизации M

► Определение.

Пусть

- функция от

n+1

переменной. Будем

говорить, что функция

от

переменных получена

из функции

с помощью оператора минимизации,

если равенство f

,...,x

)=y

верно тогда и только

тогда, когда

g(x

,...,x

, y) =0,

а значения

g(x

,...,x

,0), ... , g(x

,...,x

,y-1)

определены и не равны нулю.

Если функция

получается из функции

с помощью

оператора минимизации, то записываем

f=M(g).

Ясно, что инструкции для вычисления функции

и проверки выполнения процедуры минимизации

образуют алгоритм для вычисления значений функции

Поэтому функция

вычислима.

Пример применения оператора

минимизации

► Пример. Найти функцию f, полученную из функции o(x)

применением оператора минимизации.

► Решение. Если функция f получена из функции g с помощью

оператора минимизации, то число ее переменных меньше числа

переменных функции g на единицу. В данном случае g - это

функция o(x) от одной переменной. Поэтому функция f имеет 0

переменных. Для нахождения значения функции f нужно

проверить условия

o(0)=0, o(1)=0, ... , o(y)=0

и выбрать в этих равенствах наименьшее y. Поскольку o(x)=0 для

всех x, то наименьшее число y - это y=0. По определению

оператора минимизации полученное y=0 и есть значение функции f.

Поэтому функция f - это нульарная функция o

со значением 0,

т.е. помеченный элемент 0.

Определение частично

рекурсивной функции

Сформулируем теперь одно из основных определений

теории алгоритмов - определение частично

рекурсивной функции.

► Функция f называется частично рекурсивной

функцией, если она может быть получена из

следующих простейших функций:

1) функции следования s(x)=x+1,

2) нулевой функции o

, ... , x

)=0,

3) функции проектирования I

, ... ,x

)=x

с помощью конечного числа применений операторов

суперпозиции, примитивной рекурсии и минимизации.

Эквивалентное определение

► Как и при определении примитивной рекурсивности, можно выразить определение

частично рекурсивной функции в виде трех правил.

1. Простейшие функции

функция следования s(x)=x+1,

нулевая функция o

, ... , x

)=0,

функция проектирования I

, ... ,x

)=x

► частично рекурсивны.

2. Если функция f получена из частично рекурсивных функций с помощью

операторов суперпозиции, примитивной рекурсии или минимизации, то функция f

частично рекурсивна.

3. То, что функция f частично рекурсивна, устанавливается несколькими

применениями правил 1) и 2).

► Всякой частично рекурсивной функции можно приписать n- наименьший номер

шага, на котором она может быть получена.

Замечание о строгости

определения

В отличие от определения примитивной рекурсивности, где имелись два оператора,

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

Ясно, что всякая примитивно рекурсивная функция является частично

рекурсивной функцией. Оператор минимизации может вырабатывать не всюду

определенные функции, а примитивно рекурсивные функции всюду определены.

Поэтому существуют частично рекурсивные функции, которые не являются

примитивно рекурсивными функциями.

Ранее мы сформулировали понятие вычислимой рекурсивной функции и отметили, что

это нестрогое, интуитивное понятие. Однако для приведенного выше понятия

частично рекурсивной функции справедливо следующее утверждение.

► Понятие частично рекурсивной функции является строгим математическим

понятием.

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

Словосочетание «функция f частично рекурсивна» будем заменять на более краткое

словосочетание «f рекурсивна».

Вычислимость частично

рекурсивной функции

►Теорема.

Всякая частично рекурсивная функция f

является вычислимой функцией.

►Доказательство осуществляется

индукцией по шагу m, на котором

получена функция f.

Тезис Черча

Обозначим множество всех вычислимых функций через A, а

множество всех частично рекурсивных функций через B.

Так как всякая частично рекурсивная функция является

вычислимой функцией, то BA, что отражает следующий рисунок.

Тезис Черча

(продолжение)

В первой половине 20 в. На

многочисленном количестве примеров,

было установлено, что вычислимая

функция является частично

рекурсивной. Это наводит на мысль,

что разность A\B - пустое множество.

Тогда A = B.

В 1936 г. американский математик

Алонзо Черч выдвинул следующее

положение:

► Тезис Черча. Каждая вычислимая

функция частично рекурсивна.

Тезис Черча

(продолжение)

Сможем ли мы доказать тезис Черча? Нет, т.к. у нас нет точного

определения вычислимой функции. Тезис Черча - это просто

строгое определение алгоритма. Это положение является

соглашением, возникшим в результате длительного исследования

интуитивного понятия алгоритма. Показана рекурсивность

огромного количества вычислимых функций. Никто не сумел

построить вычислимую функцию, рекурсивность которой нельзя

было бы доказать, или хотя бы указать правдоподобный метод

построения такой функции.

Тезис Черча является естественнонаучным фактом, который

подтверждается опытом, накопленным математикой за весь период ее

развития. Тезис Черча является достаточным средством, чтобы придать

необходимую точность формулировкам алгоритмических проблем и

делает возможным доказательство их неразрешимости.