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


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

210 _ РЕКУРСИВНЫЕ ФУНКЦИИ . _
Таким образом, то единственное число, которое должно быть приписано новой стадии, определяется как примитивно-рекурсивная функция от и:
Г ехр, ( = Pi N

и' = v, (и) =
(и) = Pi Jres(exp, (u),,V) *(ехр, (и), ехр,(«)) " («Pi (f).exp, (u)) + JVexp, (u).
Совершенно аналогично, число, придаваемое новой стадии в случае (3), равно
Гехр.(ц) Т _ n»(exp1(a).expi(«))+JVexp1(u)« res (exp,(u),AOp3t(exp, (u),exp,(«)) p L ••.
10. Вначале вся лента, включая и установленную секцию, чиста, и машина находится в конфигурации qr Эта начальная стадия характеризуется числом
Назовем эту стадию нулевой и будем считать, что машина затем автоматически переходит в 1-ю, 2-ю,... стадии. Число, характеризующее п-ю стадию [собственно, (л+1)-ю, поскольку имеется нулевая стадия], можно определить 'как примитивно-рекурсивную функцию
v(0)=7,
\ 0* («)), если 8t (cxp2 (v (n)), exp3.(v (n))) =0, v2 (v (п)), если 82 (ехр2 (v («)), ехр3 (v («))) =0, v3 (v (д)), если 83 (ехр2 (v (л)), ехр3 (v (n))) =0, О в остальных случаях (не имеющих для нас значения).
V (/1+1) =
II. Нас интересуют только те стадии, в которых машина пишет 0 или 1 (разумеется, в пустой секции), другими словами, те стадии, в которых вместо установленного знака S0 пишется знак St или S2. В п-й стадии индекс установленного знака есть exp2(v(n)), а индекс конфигурации ехр3 (v (n)). Индекс нового знака, который пишется вместо установленного, равен о (ехра (v (n)), exp3(v(n))). Положим
0, если ехр2 (v (п)) =0 и а (ехр2 (v (n)), exp3 (v (n))) =1,
1, если ехр2 (v (п)) =0 и а (ехр2 (v (n))\" exp3 (v (n))) =2, 2 в остальных случаях.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 211 212 213 214 215 216 217 218 219 220 230 240 250 260


Математика