15. Тезис Черча.

Тезис Черча. Класс всех частично вычислимых функций над положительными целыми числами совпадает с классом всех частично рекурсивных функций. Иными словами, каждая арифметическая функция, для которой имеется машина Тьюринга, является одновременно и рекурсивной, и наоборот – если функция является частично-рекурсивной, то она одновременно и вычислима. С помощью тезиса Черча можно устанавливать вычислимость новых функций, используя уже построенные вычислимые функции. Поэтому, если f_x - вычислимая функция с номером x , то h(x)= f_x (x)+1 частично-вычислимая функция.

16. Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.

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

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

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

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

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

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

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

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

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

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

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

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