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


Книга: Главная » Петер Р.N. Рекурсивные функции
 
djvu / html
 

200 РЕКУРСИВНЫЕ ФУНКЦИИ
1) Машина располагает конечным числом знаков
^о> Sv Sz, S&, S4,...,
причем 50 играет роль «пустого» знака, S^O и 52=1.
2) Машина может находиться в конечном числе конфигураций
причем <7i является «начальной конфигурацией».
3) Работа машины состоит из единичных актов следующего рода: если в установленном в «поле зрения» промежутке ленты стоит знак 5, и машина в данный момент находится в конфигурации <7/> то машина пишет вместо S, определенный знак 5/- , после чего она устанавливает ту же самую или соседнюю секцию и переходит в определенную конфигурацию <7/.
Так как число знаков 5, и конфигураций qj конечно, то возможно лишь конечное число единичных актов этого рода. В зависимости от того, устанавливает ли машина в «поле зрения» прежнюю секцию, или ближайшую к ней слева, или справа, такой единичный акт мы будем обозначать соответственно через
или qjSt 1 Sf Lq? , или qjSt \ St'
Равенство 5г=5^ означает, что машина в данный момент оставляет без изменения установленный в «поле зрения» знак.
После того как в «поле зрения» установлена какая-либо секция чкстой ленты и машина приведена в конфигурацию qv единичные акты работы машины осуществляются автоматически один за другим; вследствие этого на ленте возникает последовательность знаков, в которой 0 повторяется бесконечнее число раз; перед первым знаком 0 наносятся знаки 1 в количестве, равном <р (0); между га-м и (и+1)-м знаками 0 количество знаков 1 равно <р(«). Заметим, что га-й знак 0 в последовательности знаков на ленте является вместе с тем n-м знаком 0, написанным машиной; также и га-й знак 1 на ленте есть вместе с тем га-й знак 1, написанный машиной.
3. Рассмотрим в качестве первого примера машину, вычисляющую простейшую функцию <р (п) = 1 .
Эта машина должна написать последовательность знаков
10101010...
Для этого не нужны никакие вспомогательные вычисления; следовательно, весь запас знаков машины может состоять из
50 («пусто»), Si = 0, 5а = 1 .
Мы хотим, чтобы в начальной конфигурации машина вписала в установленную в «поле зрения» пустую секцию знак 1, потом установила следующую секцию справа и перешла в такую конфи-

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 201 202 203 204 205 206 207 208 209 210 220 230 240 250 260


Математика