Доказательство: предположим противное, т.е. что такое продолжение S существует. ФÌS. Итак, функция S вычислима, всюду определена и удовлетворяет равенству S(n,x)=Ф(n,x), если только правая часть определена. Функции S(х,x) и S(х,х)+1 вычислимы о всюду определены. В силу универсальности функции Ф имеем: $n0, Ф(n0,x)=S(x,x)+1. Полагая n0=х получим S(n0,n0)=Ф(n0,n0)=S(n0,n0)+1. Все части определены. Полученное противоречие доказывает невозможность желаемого продолжения.
Область определения универсальной вычислимой функции перечислимое множество.
Доказательство: организуем процесс параллельного вычисления значения функции f для всех натуральных чисел х. Если вычисление значения f(x0) заканчивается на некотором такте t0 работы соответствующей машины, то мы сразу (и только в этом случае) объявляем, что х0 входит в перечисляемое нами множество. Понятно, что:
1. Мы построили процесс эффективного порождения некоторого множества, и значит оно перечислимо.
2. Это множество – область определения данной вычислимой функции f.
Итак, область определения всякой вычислимой функции перечислима.
Нормальные алгорифмы перерабатывают слова в каком-либо алфавите А. Каждый такой алгорифм задается своей программой. Каждая программа есть упорядоченный набор команд. Каждая команда имеет вид: wi’®eiwi’’, где wi’ и wi’’ – слова в алфавите А, ei может быть либо «.» либо пустым символом. Работа нормального алгорифма над словом w строится так: на первом шаге сначала ищутся вхождения в данное w слова w1’ – левой части первой команды. Если такие вхождения имеются, то самое левое из них заменяется на w1’’, причем если e1=«.», то работа алгорифма на этом прекращается, и только что полученное слова считается результатом этой работы. Если же e1=L, то преобразованное слово становится исходным для применения второго шага. Если же в слово w слово w1’ не входит, то аналогично поступают со второй командой. В случае неприменимости второй команды переходят к третьей, и т.д. Такие преобразования происходят до тех пор, пока это возможно. Работа алгорифма останавливается не только после применения команды, для которой ei=«.» (такие команды называют заключительными), но и в ситуации, когда ни одна из команд неприменима. В обоих ситуациях последнее полученное слово считается результатом работы алгорифма над данным w. Если же процесс преобразований продолжается бесконечно, то считают, что алгорифм не дает результата для данного w (т.е. вычисляемая им функция на слове w не определена).
Примеры:
"wÎW{a,b}
1. f(w)=aw
{®.a
2. g(w)=wa
ì*a®a*
þ*b®b*
ü*®.a
î ®*
3. A={a,b} h(w)= a, если число «а» в w равно числу «b», и b в противном случае.
ìab®
ïba®
ïaa®a
íbb®b
ïb®.b
ïa®.a
î ®.a
Нормальный алгорифм, вычисляющий функцию f(n)=2n.
*11®11*1
*1®a1
1a®a1
a®.
®*
Пусть АÌN. Множество А называют разрешимым (рекурсивным), если его характеристическая функция cА(n), определяемая так: cА(n)={1 при nÎА, 0 в противном случае}, вычислима. Иными словами А разрешимо, если существует алгоритм, определяющий по произвольному натуральному числу, входит оно в А, или нет.
Примеры:
1. N
2. Множество всех четных чисел
3. Множество всех простых чисел
Теорема о замкнутости класса разрешимых множеств:
Если А,ВÌN разрешимы, то разрешимы и множества: АÈВ, АÇВ,`А=N-А, А´В={(a,b)½aÎA, bÎB}.
Множество АÌN называется перечислимым (рекурсивно перечислимым), если оно есть множество значений некоторой вычислимой функции. Иными словами, множество перечислимо, если все его элементы и только они порождаются некоторым алгоритмическим процессом.
Примеры:
1. N. f(n)=n.
2. Множество всех четных чисел. f(n)=2n.
3. Множество всех простых чисел.
Теорема о замкнутости класса перечислимых множеств:
Если А и В перечислимы, то перечислимы и множества АÈВ, АÇВ, А´В, ПрОхА (АÌN2).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.