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


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

190 _ РЕКУРСИВНЫЕ ФУНКЦИИ __
6. Можно показать и иным способом, нежели это было сделано в п. 4, что не все обще-рекурсивные функции могут быть приведены к виду
ft» №»•"»«,, «) = 0].
Мы снова прибегнем к помощи использованной в п. 4 одноместной обще-, но не примитивно-рекурсивной функции
Однако на этот раз мы докажем большее — что существует двуместная обще-рекурсивная функция, которую нельзя представить в виде
где т — примитивно-рекурсивная функция, а <|>(/и) — такая функция, которая не всякое натуральное значение принимает при сколь угодно больших значениях аргументов. Так как функция ф (т) = т каждое свое значение принимает лишь в одной-единственной точке, то функцию, которую мы построим, нельзя будет, в частности, привести и к виду
ИтГФх, Я2) /И) = 0].
Нужная нам двуместная функция строится следующим образом:
5(0^=0.
Предположим,^что <са можно привести*к виду
<Ра К» аг) = Ф (ft. I' (°i> °2> «) = °Dt .
где т удовлетворяет требованию (F), а примитивно-рекурсивная функция <]>(?) ни для какого t^>k не принимает значения а; здесь k и а — некоторые фиксированные числа. В таком случае равенство
6(я)=0, эквивалентное равенству
t = V-ml*(n,a,m) = 0] удовлетворяет уравнению

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 191 192 193 194 195 196 197 198 199 200 210 220 230 240 250 260


Математика