b> x
f (x, y) =
НЕ Визначи в протилежних випадка
(маючих на увазі використовуват smn-теорему, ми будемо розглядаті Функції g x, для якіх g x (y) @ f (x, у). Функцію f мі Вибравши таким чином, что c ГЋ Dom (g x ) Г› х ГЋ W x Г›c ГЋ Ran (g x ).) У силу тези Черча функція f обчіслювана, так что smn-теорема Дає тотальні обчислюваного функцію k, таку, что f (х, у) @ ф k (x) (y ). З визначення f ми Бачимо, что
x ГЋ W x ГћW k (x) = E k (x) = N
так что c ГЋ W k (x) и c ГЋ E k (x) , и
x ГЏ W x ГћW k (x) = E k (x) = Г†
так что c ГЏ W k (x) и c ГЏ E k (x) . Тім самим ми звелено проблему В«x ГЋ W x В» до кожної з проблем В«c ГЋ W x В» и В«c ГЋ ; E x В«.
Завершуючі Доведення пункту (а) більш докладно, ми Бачимо, что ЯКЩО g- типова функція проблеми В«c ГЋ W x В» , то
1, ЯКЩО x ГЋ W x
g (k (x)) =
0, ЯКЩО x ГЏ W x
Ця функція НЕ є обчислюваного (теорема 1.1), так что функція g теж НЕ может буті обчислюваного. Отже, проблема В«c ГЋ W x В» нерозв'язна. p> доповідні доведення пункту (Ь) проводитися аналогічно. Гї
Мі закінчімо цею параграф одним Дуже загально результатом про нерозв'язність, з Якого негайно віплівають теореми 1.4 и 1.6. При цьом ми знову скорістаємося для зведення проблеми В«х ГЋ W x В»
s-m-n-теоремою.
1.7. Теорема (теорема Райса). Нехай В ГЌ b 1 и B В№ Г†, b 1 . Тоді проблема В«ф x ГЋ BВ» нерозв'язна .
Доведення. Співвідношення для розв'язніх множини (теорема 2-4.7) показують, что проблема В«ф x ГЋ BВ» розв'язна тоді и Тільки тоді, коли розв'язна проблема В«ф x ГЋ b 1 B В». Тому без ВТРАТИ загальності Ми можемо вважаті, что ніде НЕ Визначи функція f Г† НЕ захи B (ЯКЩО це не так, то Твердження можна довести для b 1 B).
Віберемо Деяк функцію g ГЋ B. Розглянемо функцію f (x, у), что задається так:
g (y), ЯКЩО x ГЋ W x ,
f (x, y) @
НЕ Визначи, ЯКЩО x ГЏ W x .
Корістаючісь smn-теореми, ми одержуємо тотально обчислюваного функцію k (x), таку, что f (x, у) @ ф k (x) (y),). Таким чином, мі Бачимо, что
x ГЋ W x Гћ ф k (x) = G, тоб ф k (x) ГЋ B
x ГЏ W x Гћ ф k (x) = F Г† , тоб ф k (x) ГЏ B
Це значити, что с помощью обчіслюваної Функції k ми звелено проблему В«х ГЋ W x В» до проблеми
В«ф х ГЋ В В». Тепер вже Стандартним чином можна покластись, что проблема В«ф х ГЋ ВВ» нерозв'язна.
Теорема 1.4, Наприклад, негайно віпліває з теореми Райса, ЯКЩО взяти В = {0}, а теорема 1.6 (а) - ЯКЩО взяти В = {g ГЋ b 1 : c ГЋ ; Dom (g)}. Аналогічно можна скористати теореми Райса и у Наступний вправо.
1.8. Вправи.
1. Покажіть, что наступні проблеми нерозв'язні. p> (a) В«х ГЋ Е х В« . (Указівка. Скорістайтеся діагональнім методом чг зведіть до цієї проблеми проблему
В«x ГЋ W x В» за помощью s - m-n - теореми.)
(b) В«W x = W y В«. (Указівка. Зведіть до цієї проблеми проблему В«функція ф x тотальна В».)
(c) В«ф x (х) = 0В».
(d) В«ф x (y) = 0В».
(e) В«х ГЋ Е у В«. br/>
(f) В«Функція ф x тотальна и ПостійнаВ». br/>
(g) В«W x = Г† В» .
(h) В«Множини Е x НескінченнаВ». p> (i) В«ф х ...
