Rekurencyjność liczb pierwszych

magdaam · Post autor: **magdaam** » 21 wrz 2012, o 20:32

Witam,
Muszę napisać dowód, że funkcja \(\displaystyle{ f(n)= n}\)-ta liczba pierwsza jest funkcją rekurencyjną.
Mógłby mi ktoś dać jakieś wskazówki jak tego dokonać?

Zordon · Post autor: **Zordon** » 21 wrz 2012, o 20:37

Co przyjmujesz za definicję rekurencyjności? Można to robić za pomocą maszyn Turinga, innych automatów albo jeszcze inaczej.

magdaam · Post autor: **magdaam** » 21 wrz 2012, o 21:24

Dowód ma ma bazować na definicji PREC i ma prowadzić bez żadnych luk z funkcji podstawowych \(\displaystyle{ (S,Z, I^{i}_{n}}\), wykorzystując operacje składania, rekursji prostej i minimalizacji, do definicji funkcji \(\displaystyle{ f}\).

oraz mam bazować na tym skrypcie -