Учебные материалы (Практические занятия, контрольные задания, конспект лекций) / Практические занятия / Практическое занятие 2

6

Практическое занятие №2. Рекурсивные функции и множества. Тезис Черча.

Цель занятия.

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

Краткие теоретические сведения.

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

А). Функция константа

Б) Функция непосредственного следования

В) Тождественная функция

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

• Операция подстановки. Эта операция заключается в том, что вместо каких-то переменных функции подставляют другие функции от тех же или иных переменных.

Пример. Пусть и . Тогда подставив вместо переменной х функцию g(у), получим новую функцию:

• Операция примитивной рекурсии. Эту операцию можно представить следующим образом

Пример 1. Пусть - известная вычислимая функция, т.е. известен алгоритм вычисления этой функции для произвольного х. Определим новую функцию f(x) следующим образом:

Это и есть определение функции с помощью операции примитивной рекурсии. Например, пусть

Это есть определение целочисленного умножения. Так f(3,3)=f(3,2)+3=f(3,1)+3+3=3+3+3=9.

Пример 2. и

Это определение позволяет находить значение . В самом деле, рассмотрим следующий пример вычисления 3² .

f(3,1+1)=h(3,f(3,1))=h(3,3)=h(2+1,3)=h(2,3)+3=h(1+1,3)+3=h(1,3)+3+3=3+3+3=9

Определение. Функция, определяемая из простейших с помощью операций подстановки и/или примитивной рекурсии, называется примитивно рекурсивной.

Имеется еще одна операция для построения рекурсивных функций. Правда, эта операция не всегда дает результат или, как говорят, не является полностью определенной (тотальной). Эта операция называется операцией минимизации (взятия минимального корня). Ее определение таково.

• 

Эту операции можно для простоты обозначить как _y f(x,y).

Пример 3. Пусть . Тогда _y f(3,y)=2.

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

Имеет место следующая знаменитая гипотеза, известная как Тезис А.Черча

Тезис Черча. Класс всех частично вычислимых функций над положительными целыми числами совпадает с классом всех частично рекурсивных функций.

Иными словами, каждая арифметическая функция, для которой имеется машина Тьюринга, является одновременно и рекурсивной, и наоборот – если функция является частично-рекурсивной, то она одновременно и вычислима.

Задание 0. Показать рекурсивность функции >.

Решение.

Задание 1. Показать частичную рекурсивность функции, называемой усеченной разностью, которая вычисляется следующим образом

x y =

Решение.

Задание 2. Показать примитивную рекурсивность функции max(x,y).

Решение.

Задание 3. Показать примитивную рекурсивность функции нахождения остатка от деления x на y. Назовем эту функцию rest(x,y).

Решение.

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

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

М1={ x | x = 2*N}

Множество составных целых положительных чисел можно задать так

М2 = { x | n≠1m≠1 (x=m*n)}

Здесь символ  означает “существует” и называется квантором существования. Наряду с квантором существования, имеется еще квантор всеобщности - . С помощью квантора всеобщности можно записать характеристическую формулу множества всех простых чисел М3:

М3 = { x | n≠1 m≠1 (x ≠m*n)}

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

M^co={ x | x  M}.

Множество M^co называется дополнением множества М.

Задание 4. Записать с помощью характеристических функций множество целых положительных чисел, дающих при делении на 7 в остатке 2.

Решение.

М4 = { x | n ( x=7*n+2 ) }

Задание 5. Записать с помощью характеристических функций множество целых положительных чисел, дающих при делении на 7 в остатке 2.

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

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

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

Пример 1. Множество разрешимых (т.е. имеющих корни) диофантовых уравнений.

Уравнение общего вида где все коэффициенты и переменные целочисленны, называется диофантовым. Советский математик Ю.Матиясевич доказал, что нет алгоритма для решения диофантова уравнения общего вида.

Пример 2. Множество доказуемых формул арифметики целых чисел.

Этот пример известен как теорема К.Геделя о неполноте арифметики целых чисел. Она означает принципиальную недоказуемость некоторых истинных утверждений арифметики. Долгое время считалось, что знаменитая теорема Ферма является примером недоказуемой истинной формулы, пока сравнительно недавно не было получено ее доказательство. Теорема Ферма утверждает, что не существуют такие целые положительные числа a,b,c,n>2, что aⁿ + bⁿ= cⁿ .

Теорема F. Множество MTF финитных самоНЕприменимых машин Тьюринга нерекурсивно.

Будем рассматривать машины Тьюринга с двумя типами конечных состояний, условно называемых “ДА”-состоянием и “НЕТ” –состоянием. Говорят, что машина принимает входное слово z, если обработка этого слова заканчивается в состоянии “ДА”. Если же обработка слова z заканчивается в состоянии “НЕТ”, то говорят, что машина отклоняет слово z. Машина может, вообще говоря, зациклиться, но такие машины теорема не рассматривает – речь идет о финитных машинах, т.е. о таких машинах, которые каждое вычисление заканчивают либо в состоянии “НЕТ”, либо в состоянии “ДА”. СамоНЕприменимые машины – это такие машины, которые не принимают свои собственные описания, т.е. при подаче на их вход набора правил этих же машин они заканчивают в состоянии “НЕТ”.Теперь докажем теорему.

Доказательство. Пусть имеется, вопреки утверждению, машина, вычисляющая характеристическую формулу множества MTF. Это значит, что M_MTF переходит в состояние “ДА” на входе x, где x – набор правил произвольной машины Тьюринга, если машина с данным набором правил не принимает этот набор правил. Обозначим эту машину M_MTF. Спрашивается, в каком состоянии M_MTF закончит вычисление, если на ее вход подать набор правил ее самой? Если она примет этот набор, то это означает, что машина M_MTF самоНЕприменима, т.е. не принимает подобные наборы – противоречие. Если же M_MTF не примет данный набор, то она должна его принять – снова противоречие.

Задание 7. Докажите, что если множество не является рекурсивным, то и его дополнение также нерекурсивно.

Задание 8. Попробуйте доказать следующую теорему.

Теорема A. Множество MTA финитных самоприменимых машин Тьюринга нерекурсивно.

Указание. Доказательство можно получить непосредственно из доказательства теоремы F. Нужно показать, что MTA есть дополнение множества MTF. Теперь, если допустить, что MTA рекурсивно, то рекурсивным должно быть и множество MTF , но этого нет.

Определение. Множество A называется рекурсивно перечислимым, если его характеристическая функция f(x) частично рекурсивна, причем

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

Задание 9. Доказать, что если множество A и его дополнение A^co рекурсивно перечислимы, то A – рекурсивное множество.

Задание 10. Пусть А и В рекурсивно перечислимы. Доказать, что таковым будет и множество A  B, A  B, A \ B.

Контрольные вопросы.

1. Дайте определение примитивно рекурсивной функции.

2. Что такое операция подстановки и рекурсии ?

3. Дайте определение операции минимизации.

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

5. Что такое рекурсивное множество ?

6. Сформулируйте и прокомментируйте тезис Черча.

7. Что такое характеристическая функция множества ?

8. Докажите теорему о нерекурсивности множества самоНЕприменимых машин Тьюринга.

9. Что такое рекурсивно перечислимое множество. Как связаны рекурсивность множества и его рекурсивная перечислимость?

Литература

1. Н.Катленд. Вычислимость. Введение в теорию рекурсивных функций. М., Мир, 1983.