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


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

150 X. Ямада
Таким образом, следующая выходная единица появляется в момент 64 (=43), а ленты выглядят в этот момент следующим образом:
37

1 1 ... 1
t 17

1 1 ... 1
t 5
*~ ~*
1 1 1 1 1
t
Следующие шаги являются зеркальным отражением вышепри веденных шагов относительно движения:
35. <7з1 HI» ***> LRL б/32 О
36. ?з2 Ю1, *!*, LRL <7з2 О
37. <7з2 ЮО, ***, L** (/зз О
38. (/зз ЮО, ***» ^** <7зз О
39. <7зз 010, 1**, LL* <7з4 О
40. ?34 010, 1**, LL* ?34 О
41. ?34 000, 100,
Затем весь процесс повторится от q^ до <7з4- Это конец построения С-машины для точных кубов.
Нужно отметить, что запись на Гз не растет во времени. Это верно и в общем случае полинома п-и степени, только записи на п — 1 ленте удлиняются. Другим моментом, который мы должны здесь отметить, является то, что, если дана определяющая функция f, задача вычислений сводится к последовательному вычислению f(l)-f(0), f(2)-f(l), f(3)-f(2) и т. д. Другими ело-вами, если мы определяем приращение F функции / как
то перед машиной стоит задача вычислять F(x) заново для каждого *=1, 2, 3 и т. д. Это просто следует из того факта, что поскольку вычислено f(x), то и f(*-f 1) во многом вычислено, и чтобы получить /(я+ 1), требуется единственное дополнительное вычисление — вычисление разности / (х + 1) ^— }(х).

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 151 152 153 154 155 156 157 158 159 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


Математика