рекурсии

From

Serge Petruschenko (2:5020/825.13)

To

Alex Kozhushko

Date

2002-12-03T18:15:02Z

Area

RU.ALGORITHMS

Привет, тов. Alex!

02 дек 02 12:25, ты накарябал на заборе для меня:

 >>  SP>> Кто-нибудь знает, бывают ли рекурсивные функции не являющиеся
 >>  SP>> примитивно-рекурсивными? Если можно, приведите пример плз.

 >>  AK> Бывают.
 >>  AK> Например, универсальная функция.
 SP>> А можно попдробнее, что это за функция такая?

 AK> Пусть E: N->(N^k->N) - нумерация k-местных рекурсивных функций,
 AK> U(m,n)=(E(m))(n) - универсальная функция

 AK> В качестве примера рекурсивной, но не примитивно-рекурсивной функции
 AK> сойдет функция
 AK> Аккермана: A(0,n)=n+1 A(m+1,0)=A(m,1) A(m+1,n+1)=A(m,A(m+1,n))

 AK> Или ее одноместный вариант A1(n)=A(n,n)
Спасибо, функцию Аккермана я уже нашел.

 AK> Доказательство того, что она - не примитивно-рекурсивная, строится,
 AK> насколько я помню, на том, что она растет быстрее любой
 AK> примитивно-рекурсивной.
И занимает 25 страниц, как нам сегодня сказал лектор.

ЗЫ Спасибо что откликнулся.

WBR Separator, самый добрый маньяк-убийца на свете
... Лучшая винда это X-Window-System
--- Приплюснутый голый дед 1.1.5-20021027 / Дебиан ГНУ/Линух 3.0
 * Origin: Навязывание религии в школах - ДАВИТЬ! (2:5020/825.13)