Лекция 5. Рекурсивные множества и тезис Тьюринга. Идея эффективной процедуры.

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

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

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

Определение 5.1.Функцияназываетсяре­курсивной,если существует эффективная процедура для ее вычислений.

Определение 5.2.Множествоназываетсярекурсивным,если существует эффективная процедура для выяснения того, принадлежит или не принадле­жит произвольный элемент к этому множеству.

Определение 5.3.Множествоназываетсярекурсивно перечислимым,если существует эффективная процедура для последовательного порождения (пере­числения) его элементов.

Пример.Множество квадратов целых чисел рекур­сивно перечислимо. Для получения элементов этого множества достаточно последовательно брать числа 1, 2, 3, ... и возводить их в квадрат. Более того, это множество является также рекурсивным. Проверка принадлежности любого числа к данному множеству сводится к разложению этого числа на простые мно­жители, что и позволяет выяснить, является ли оно квадратом.

Теорема 5.1.Если R и S — рекурсивно перечислимые множества, то рекурсивно перечислимы множества RS и RS.

Теорема 5.2.Множество положительных целых чисел S рекурсивно тогда и только тогда, когда S и рекурсивно перечислимы.

Теорема 5.3.Существует рекурсивно перечисли­мое, но не рекурсивное множество положительных- це­лых чисел.

Доказательство. Из теоремы 5.2 следует, что этот факт эквивалентен существованию рекур­сивно перечислимого множества натуральных чисел, дополнение к которому не является рекурсивно пере­числимым.

Пусть S₁,S₂, ... — эффективное перечисление всех рекурсивно перечислимых множеств, а(x, у}— номер пары(х, у)какого-нибудь эффективного перечисления всех пар натуральных чисел. Тогда на(x, у}-м этапе вычисляетсях-й элемент множестваS_y. Если этот элемент совпадает су,то включим его во множествоU.Таким образом,упринадлежит мно­жествуUтогда и только тогда, когдаупринадлежитS_y. Ясно, чтоUявляется рекурсивно перечислимым множеством. Так как множествосостоит из всех такиху,чтоуне принадлежитS_y,тоотличается от любого рекурсивно перечислимого множества хотя бы одним целым числом. Поэтомуне является ре­курсивно перечислимым, аU —рекурсивным множе­ством, что и требовалось доказать.

Эта теорема фактически включает в себя в неяв­ном виде теорему Гёделя.

Рассмотрение машин Тьюринга нельзя закончить без упоминания об универсальных машинах Тьюринга, т. е. таких машин Тьюринга, которые способны моде­лировать работу любоймашины Тьюринга. Каж­дой машине ТьюрингаZсопоставим числоn, гдеZ_n— первое вхождениеZв эффективном перечисленииZ₁, Z₂, Z₃, ... машин Тьюринга.

Теорема 5.4.Существует универсальная машина Тьюринга U такая, что

Fz_n(x)=F_U(n, х)

для всех машин Тьюринга Z_n и всех целых чиселх.

Доказательство.Пустьпих —произвольные натуральные числа. По числупможно эффективно построить машину ТьюрингаZ_nи на ней эффективно вычислить функциюFz_n(x).Таким образом, функцияF_Uэффективно вычислима, а тогда, согласно тезису Тьюринга, существует искомая машина ТьюрингаU, что и требовалось доказать.