Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

410
Блюм
Вычеркнем первое вхождение ф^(я) в столбец /г, такое, что ) помечена и обладает тем свойством, что все ФЛ(АП), тt(u, Vt Q («) равной нулю. В противном случае переходим к (6).
С uu - заштрихованная область Рис. 1.
(6) Если фь(/г) вычеркнута, полагаем
0, если 1§ если
Из этого определения следует, что если ф/ определена всюду, то ф?(и, и, о определена для всех и и v.
2. Доказательство леммы 1. В вычислении ф^о, о,о число описанных выше вхождений в строку и, которые вычеркиваются, должно быть конечным, так как строка содержит самое большее одно вычеркнутое вхождение. Пусть столбец и располагается непосредственно справа от самого правого вычеркнутого описанного выше вхождения в строку и. Тогда из рисунка ясно, что Ф«о, о, ъ(п) = Ф*(и, v, n(n) для всех п. Что и требовалось доказать.
3. Доказательство леммы 2. Пусть i — некоторый индекс для f; доказывая от противного, предположим, что Фг(я) -^ •^Ф/(я — 1) для бесконечно многих п = п\, п2, Яз, ... . Тогда, очевидно, в вычислении ф*(о,о, о(и) фг(^й) была вычеркнута для некоторого k, и поэтому ф^о.о.оС^^фИ^)» откуда следует, что ^Ял)=?ф(лй). Противоречие. Что и требовалось доказать.
4. Доказательство леммы 3. Выберем некоторое рекурсивное взаимно однозначное отображение натуральных чисел на множество всех m-ок (т — 1, 2, 3 . . .) натуральных чисел. Пусть

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 411 412 413 414 415 416 417 418 419 420 430


Математика