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


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

90 А Я. Ричи
у, 2) == ТМ (2) Л
[ID (я,
Л ID (у, х,а21221азХ2, 22, *1Й21221я31221)Л Л Quint ((и,, 2Ь 02» 22» 0»
[Quint ((аь гь fl2» ^2» 2)» 2) Л Л ID (л:, Ar^^la, 12-21л:2, 2^ ^,a3122i 4| 221) Л AID (у, ^1й31221а21221л:2, 22, д:,а31221)], Yield2 (л:, f/, г) = ТМ(2)Л (3*i. «ь ^i) [Quint ((а!, 2Ь а2. ^2» 0» ^) Л Л Ш(л:, jcifl11221, 2Ь ^0,1221) Л Л ID (у, х1а21221111221, 22,
Yield3(A:, ^, 2)^ ТМ(2) Л (Эх,, а^ а3» ^i)<
[Quint ((а,,^, о2, 22, 2), г) Д Л ID(x, л:1а31221а11221, 2If Jc1a31221fl11221) Л Л ID (у, Х1а31221а21221, 22l X1a31221)],
Yield4(A:, г/, 2)sTM(2)A(3^i» fli» аз» 21)<Х(Э22)<У
[Quint ((fllf 2lf 11, г2, 2), 2) Л Л ID(x, jcifl31221a11221, 2lf х1а31221а,1221) Л Л ID (г/, ^а31221, 22> ^!Й31221)], Yield (х, у, 2) = [Yieldle(x, у, z) V Yield1&(x, yt z) V VYieldlc(A:, у, z) V Yield2(A:, у, г) V VYield3(*, г/, г) V Yield4(A:, у, г)].
Поскольку отношение Yield принадлежит , следующее определение показывает, что функция Yield двух переменных также принадлежит ^2. Смысл этой функции достаточно ясен: Yield (;:, z) есть гёделев номер мгновенного описания, которое непосредственно следует за мгновенным описанием с номером х на машине Тьюринга с номером 2,
Yield (*, 2) = min y^x • 2 [Yield (А:, у, z)].
Вычисление на машине Тьюринга заканчивается тогда, когда достигается мгновенное описание с заключительным состоянием /. Так что мы определяем Fin (А:) как множество чисел xt кото-

 

1 10 20 30 40 50 60 70 80 90 91 92 93 94 95 96 97 98 99 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 420 430


Математика