PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



Appunti completi + dimostrazioni EDIT 2015 LS v3p.pdf


Preview of PDF document appunti-completi-dimostrazioni-edit-2015-ls-v3p.pdf

Page 1 2 3 45672

Text preview


3 Funzioni primitive ricorsive
3.1 Schema di composizione funzionale . . . . . . . . . . . . . .
3.2 Schema di ricorsione 1 . . . . . . . . . . . . . . . . . . . . .
3.3 Schema di ricorsione 2 . . . . . . . . . . . . . . . . . . . . .
3.4 Funzioni primitive ricorsive . . . . . . . . . . . . . . . . . .
3.4.1 Funzioni di base . . . . . . . . . . . . . . . . . . . .
3.5 Alcune funzioni primitive ricorsive . . . . . . . . . . . . . .
3.5.1 Funzione somma . . . . . . . . . . . . . . . . . . . .
3.5.2 Funzione prodotto . . . . . . . . . . . . . . . . . . .
3.5.3 Funzione fattoriale . . . . . . . . . . . . . . . . . . .
3.5.4 Esponenziazione xy . . . . . . . . . . . . . . . . . . .
3.5.5 Predecessore limitato ppxq . . . . . . . . . . . . . . .
3.5.6 Sottrazione limitata x ´ y . . . . . . . . . . . . . . .
3.5.7 Valore assoluto di una differenza |x ´ y| . . . . . . .
3.5.8 Funzione rilevatrice di zeri αpxq . . . . . . . . . . . .
3.6 Predicati primiti ricorsivi . . . . . . . . . . . . . . . . . . .
3.6.1 Uguaglianza x “ y . . . . . . . . . . . . . . . . . . .
3.6.2 Predicato x ď y . . . . . . . . . . . . . . . . . . . . .
3.6.3 Chiusura dei predicati PR rispetto alle operazioni di
3.6.4 Predicato x ă y . . . . . . . . . . . . . . . . . . . . .
3.6.5 Definizione per casi . . . . . . . . . . . . . . . . . . .
3.7 Operazioni iterate e quantificatori limitati . . . . . . . . . .
3.7.1 Quantificatori limitati . . . . . . . . . . . . . . . . .
3.8 Altri predicati primitivi ricorsivi . . . . . . . . . . . . . . .
3.8.1 x `e un divisore di y . . . . . . . . . . . . . . . . . . .
3.8.2 Primopxq . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Minimalizzazione . . . . . . . . . . . . . . . . . . . . . . . .
3.9.1 Minimalizzazione non limitata . . . . . . . . . . . .
3.10 Altre funzioni primitive ricorsive . . . . . . . . . . . . . . .
3.10.1 Funzione enumeratrice di primi . . . . . . . . . . . .
3.10.2 Parte intera del quoziente xy . . . . . . . . . . . . . .
3.10.3 Resto della divisione xy . . . . . . . . . . . . . . . . .
4 Funzione angoletto e numeri di G¨
odel
4.1 Funzione angoletto . . . . . . . . . . .
4.2 Numeri di G¨
odel . . . . . . . . . . . .
4.2.1 La funzione di proiezione pxqi .
4.2.2 La funzione lunghezza Ltpxq . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
, ^, _
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

17
17
18
18
18
19
20
20
20
20
20
21
21
21
21
22
22
22
22
22
22
23
24
24
24
24
24
25
25
25
25
26

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

27
27
28
28
28

5 Un programma universale
5.1 Codificare programmi usando numeri . . . . . . . . . . .
5.1.1 Codifica numerica di S -Istruzioni . . . . . . . .
5.1.2 Codifica numerica di un Programma . . . . . . .
5.1.3 Esercizio 2, p. 67 dal Davis - Trovare P tale che
5.2 Esistono funzioni che non sono parzialmente calcolabili .
5.3 Il problema della fermata . . . . . . . . . . . . . . . . .
5.4 Universalit`
a . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Il programma universale Un . . . . . . . . . . . .
5.4.2 Il predicato STP . . . . . . . . . . . . . . . . . .
5.4.3 Caratterizzazioni . . . . . . . . . . . . . . . . . .

. . . . . . .
. . . . . . .
. . . . . . .
#pPq=575.
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

29
29
29
30
30
31
31
32
32
34
35

6 Insiemi ricorsivamente enumerabili
6.1 Propriet`
a di chiusura . . . . . . . . . . . . . . . . . . . .
6.2 Il teorema di enumerazione . . . . . . . . . . . . . . . .
6.2.1 Esistono insiemi non ricorsivamente enumerabili
6.3 Altri teoremi . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

37
38
39
39
40

.
.
.
.

.
.
.
.

.
.
.
.

4

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.