Re: рекурсии

From

Alex Kozhushko ()

To

Serge Petruschenko

Date

2002-12-02T12:25:21Z

Area

RU.ALGORITHMS

From: "Alex Kozhushko" <alxrie@sibmail.ru>

Добрый день, Сергей!

"Serge Petruschenko" <Serge.Petruschenko@p13.f825.n5020.z2.fidonet.org>
wrote in message news:1038654197@p13.f825.n5020.z2.ftn...

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

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

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

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

Или ее одноместный вариант A1(n)=A(n,n)

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

С уважением,
Алексей



--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)