1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 17
Текст из файла (страница 17)
Интуитивный смысл теоремы о неподвижной точке заключается в том, чтодля любого такого преобразователя найдется хотя бы одна процедура æa , котораяне изменяется под его действием, т. е. æf (a) = æa . Другими словами, у любого такогопреобразователя найдется неподвижная точка-процедура.æ0æ1...æa...- преобра-зовательf- æf (0)- æf (1)...-æf (a) = æa...Пример.
В программировании известна популярная задача-головоломка о написании программ, воспроизводящих свой собственный текст (такие программы называют словом «quine»). Например, текст такой программы на языке Паскаль выглядитследующим образом:PROGRAM FIXEDPOINT;TYPESTR=STRING[255];VAR70Глава IV. Теория вычислимостиC:ARRAY[0..15] OF STR;I:INTEGER;BEGINC[ 0]:=’’’’;C[ 1]:=’ C[’;C[ 2]:=’]:=’;C[ 3]:=’;’;C[ 4]:=’PROGRAM FIXEDPOINT;’;C[ 5]:=’TYPE’;C[ 6]:=’ STR=STRING[255];’;C[ 7]:=’VAR’;C[ 8]:=’ C:ARRAY[0..15] OF STR;’;C[ 9]:=’ I:INTEGER;’;C[10]:=’BEGIN’;C[11]:=’ FOR I:=4 TO 10 DO WRITELN(C[I]);’;C[12]:=’ WRITELN(C[1],0:2,C[2],C[0],C[0],C[0],C[0],C[3]);’;C[13]:=’ FOR I:=1 TO 15 DO WRITELN(C[1],I:2,C[2],C[0],C[I],C[0],C[3]);’;C[14]:=’ FOR I:=11 TO 15 DO WRITELN(C[I]);’;C[15]:=’END.’;FOR I:=4 TO 10 DO WRITELN(C[I]);WRITELN(C[1],0:2,C[2],C[0],C[0],C[0],C[0],C[3]);FOR I:=1 TO 15 DO WRITELN(C[1],I:2,C[2],C[0],C[I],C[0],C[3]);FOR I:=11 TO 15 DO WRITELN(C[I]);END.Оказывается, существование подобных программ близко связано с теоремой онеподвижной точке.
В определенном смысле, если для языка программированиясправедлива теорема о параметризации, то можно написать программу на данномязыке, которая выводит свой собственный код.Докажем существование подобной программы для языка машин Шёнфилда, т. е.необходимо показать, что существует программа P с кодом e, которая после запуска всегда останавливается и выдает (в нулевом регистре) свой собственный код e.Для этого рассмотрим вычислимую функцию g(x, y) = x и применим к ней теорему о параметризации — получим некоторую вычислимую функцию f (x) такую, чтоg(x, y) = æf (x) (y).
Далее применим теорему о неподвижной точке к функции f (x) —получим число a ∈ ω такое, что æa = æf (a) . Из доказательства теоремы о неподвижной точке видно, что a = s(n, n) для некоторой s-m-n-функции s, а из доказательстватеоремы о параметризации вытекает, что любая s-m-n-функция всегда в качестве своих значений выдает коды некоторых программ. Отсюда заключаем, что найденное aявляется кодом программы, т.
е. предикат Prog(a) истиннен, и программа с кодом aвычисляет функциюæa (y) = æf (a) (y) = g(a, y) = a,т. е. выдает свой собственный код a.Теорема о неподвижной точке имеет очень важное следствие, которое утверждает,что никакое нетривиальное (т. е. присущее некоторым, но не всем функциям) свойство частично вычислимых функций не может быть эффективно распознаваемымпо их клиниевским номерам. Для доказательства данного утверждения нам понадобится следующее определение, которое является переформулировкой определениярекурсивного отношения в терминах вычислимых функций.§ 19. Нумерации и алгоритмические проблемы71Определение.
Множество A ⊆ ω n называется вычислимым, если его характеристическая функция XA (x1 , . . . , xn ) является вычислимой.Теорема 46 (теорема Райса). Пусть K — произвольное семейство одноместныхчастично вычислимых функций, такое, что K6=∅ и K не совпадает с семействомвсех одноместных частично вычислимых функций. Тогда множество {x∈ω|æx ∈K}всех клиниевских номеров функций, принадлежащих семейству K, невычислимо.Доказательство. Допустим, напротив, множество A = {x ∈ ω | æx ∈ K} вычислимо,т. е. вычислимой является его характеристическая функция(1, если x ∈ A,XA (x) =0, если x ∈/ A.Так как K 6= ∅ и K 6= {f | f — 1-местная ч.в.ф.}, то найдутся a, b ∈ ω такие, чтоæa ∈ K и æb ∈/ K.
Определим функцию(b, если x ∈ A,f (x) =a, если x ∈/ A.Поскольку f (x) = b· XA (x)+a· sg(XA (x)), то f (x) вычислима. По теореме о неподвижной точке существует n ∈ ω такое, что æf (n) = æn . Тогда имеет место следующаяцепочка эквивалентностей (вторая эквивалентность следует из выбора a и b, третьяэквивалентность следует из определения функции f (x)):æn ∈ K ⇐⇒ æf (n) ∈ K ⇐⇒ f (n) = a ⇐⇒ n ∈/ A ⇐⇒ æn ∈/ K.Противоречие. Следовательно, наше предположение о вычислимости множества {x ∈ω | æx ∈ K} неверно.Пример.
Пусть f (x) — произвольная одноместная ч.в.ф. Рассмотрим одноэлементное семейство функций K = {f }. Оно удовлетворяет условиям теоремы Райса, следовательно, множество A = {e ∈ ω | æe = f } не вычислимо. Заметим, что множество A— это в точности множество всех клиниевских номеров функции f . Таким образом,из теоремы Райса следует, что множество всех клиниевских номеров фиксированнойч.в.ф. не вычислимо.
В частности, любая ч.в.ф. имеет бесконечно много клиниевскихномеров (поскольку, очевидно, любое конечное множество вычислимо).§ 19.Нумерации и алгоритмические проблемыОбъектами классической теории вычислимости являются функции вида f : A → ω,где A ⊆ ω n . Для таких объектов мы ввели понятие вычислимости и получили целый ряд важных результатов. Однако алгоритмические проблемы, возникающие валгебре, математической логике и других разделах математики, формулируются дляабстрактных совокупностей объектов, традиционно используемых в этих разделах.Чтобы говорить о вычислимости алгебраических структур, разрешимости теорий иконструктивизируемости топологических пространств, необходимо ввести понятиевычислимости для подобных объектов. Эта необходимость приводит нас к понятиюнумерации, в основе которого лежит очень естественная идея: нужно занумеровать(если это возможно) все объекты из рассматриваемой совокупности, отождествивкаждый объект с натуральным числом, и в дальнейшем говорить не о самих объектах, а об их номерах, для которых уже развита теория вычислимости.72Глава IV.
Теория вычислимостиОпределение. Пусть S — не более чем счетное множество. Любое сюръективноенаотображение ν : ω −→ S называется нумерацией множества S.Определение. Пусть ν — нумерация. Отношение ην = {hx, yi ∈ ω 2 | ν(x) = ν(y)}называется нумерационной эквивалентностью нумерации ν.наОпределение (типы нумераций). Нумерация ν : ω −→ S множества S называется:а) однозначной, если ην = {hx, xi | x ∈ ω}, т.
е. ν — биекция;б) разрешимой, если ην вычислимо;в) позитивной, если существует вычислимая функция, область значений которойесть множество кодов пар из ην ;г) негативной, если существует вычислимая функция, область значений которойесть множество кодов пар из ω 2 \ ην , или ω 2 = ην (т. е. S одноэлементно).Замечание. Нумерация ν позитивна тогда и только тогда, когда множество ην вычислимо перечислимо. Нумерация ν негативна тогда и только тогда, когда множествоω 2 \ ην вычислимо перечислимо (определение вычислимо перечислимого множествасм. в следующем параграфе).Пример.
1) Отображение æ : ω → {f | f — одноместная ч.в.ф.}, определенное поправилу æ(n) = æn , является нумерацией множества всех одноместных частичновычислимых функций. Эта нумерация не является однозначной, поскольку любаяч.в.ф. имеет бесконечно много клиниевских номеров. Более того, данная нумерацияне является ни разрешимой, ни позитивной, ни негативной. Нумерацию æ называютклиниевской.2) Отображение ν : ω → ω 2 , определенное по правилу ν(n) = h(n)0 , (n)1 i, являетсянумерацией множества всех пар натуральных чисел. Данная нумерация не являетсяоднозначной, но является разрешимой.3) Если A = {a0 , . .
. , an−1 } — конечное n-элементное множество, где n > 1, тоотображение ν(x) = arest(x,n) , где rest(x, n) — остаток от деления x на n, являетсянумерацией множества A. Данная нумерация не является однозначной, но являетсяразрешимой.4) Пусть Pfin (ω) — множество всех конечных подмножеств натуральных чисел.Определим нумерацию γ : ω → Pfin (ω) следующим образом. Если n = 0, то полагаемγ(0) = ∅.
Если же n > 1, то для него существует единственное двоичное представление, т. е. найдутся такие xk > . . . > x0 , что n = 2xk + . . . + 2x0 . Тогда полагаемγ(n) = {x0 , . . . , xk }. Нумерация γ является однозначной.наОпределение. Пусть ν : ω −→ S — нумерация множества S.
Любое подмножествоS0 ⊆ S называется алгоритмической проблемой относительно нумерации ν. Эта проблема называется разрешимой относительно ν, если множество {x ∈ ω | ν(x) ∈ S0 }вычислимо.Пример. 1) Из теоремы Райса следует, что все нетривиальные алгоритмическиепроблемы на множестве {f | f — одноместная ч.в.ф.} неразрешимы относительноклиниевской нумерации.§ 19.
Нумерации и алгоритмические проблемы732) Проблема {hx, yi | x 6 y} на множестве ω 2 разрешима относительно нумерацииν(n) = h(n)0 , (n)1 i, т. е. по номеру n пары натуральных чисел hx, yi можно эффективно проверить, выполняется ли условие x 6 y или нет. Эта проверка осуществляется¦с помощью вычислимой функции X (n) = sg((n)0 −(n)1 ).3) Любая алгоритмическая проблема на конечном множестве A = {a0 , . . . , an−1 }разрешима относительно нумерации ν(x) = arest(x,n) . Действительно, если A0 = {ak0 ,. . . , aks } непустое подмножество A, то множество {x ∈ ω | ν(x) ∈ A0 } совпадает сsSмножеством {n· t + ki | t ∈ ω}, которое, очевидно, вычислимо.i=04) Пусть S0 = {X ⊆ ω | X — одноэлементное} ⊆ Pfin (ω). Проблема S0 разрешима относительно нумерации γ. Нетрудно видеть, что натуральное n являетсяγ-номером одноэлементного множества тогда и только тогда, когда n является степенью двойки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
