Esprimere le funzioni usando il dizionario aritmetico

Question

Ho visto nella classe "Logic to Cs", prendo - un teorema che afferma: "Ogni funzione ricorsiva (calcolabile) $ f $ può essere espresso utilizzandoIl dizionario aritmetico { $ c_0, c_1, f _ + (,), f_x (,), r_ \ le (,) $ } con la struttura { $ d=mathbb {n}, c_0= 0, c_1= 1, f _ + (A, B)= A + B, F_X (A, B)= AB, R_ \ Le (A,B)= A \ Le B $ } "

Ma non abbiamo dimostrato questo teorema perché una parte degli studenti non ha preso il corso "Modelli Computational" (l'ho preso però)

Dove posso trovare una prova per questo teorema?Grazie in anticipo!

Answer 1

Non sono sicuro che questo sia esattamente quello che stai cercando, ma potresti trovare quello che vuoi in teorema 3.2.1 della teoria del computabilità di S. Barry Cooper:

.

Tutte le funzioni ricorsive sono rappresentabili in PA.

cioè per qualsiasi funzione ricorsiva $ f $ , esiste un predicato binario $ f $ in il linguaggio dell'aritmetica tale che per qualsiasi numero naturale $ x $ e $ y $ abbiamo $$ f (x)= y ~ \ RightArrow ~ \ VDash_ {PA} f (x, y) $$ e $$ f (x) \ neq y ~ \ reapyarrow ~ \ vdash_ {pa} \ lnot f (x, y) $$ dove $ \ vdash_ {pa} $ significa "pa dimostra".

Questo teorema è centrale per il famoso teorema di Gödel in incompletezza , quindi potresti anche voler dare un'occhiata a ch. 8 del libro menzionato in cui è discusso, e questa nozione di "rappresentabilità" è estesa alla "semi-rappresentabilità", per includere il c.e. Set anche.