1. Teo9 Esistenza di funzioni non parzialmente calcolabili *
2. Def20 Tesi di Church-Turing
3. Def21 Predicato HALT
4. Teo10 Il predicato HALT non è calcolabile *
5. Def22 Congettura di Goldbach
6. Def23 Funzione universale *
7. Teo11 Universalità
8. Def24 Programma universale U(n)
9. Def25 Predicato STP
10. Def26 Funzione di Ackermann-Peter
11. Def27 Funzione caratteristica
12. Prop2 B incluso in N alla n è classe PRC <=> lo è anche B'
13. Teo12 Chiusura di A e B classi PRC
14. Def28 Insieme ricorsivo e ricorsivamente enumerabile *
15. Def29 Decidibilità
16. Teo13 B incluso in N è ricorsivo => ricorsivamente enumerabile
17. Teo14 B incluso in N è ricorsivo <=> B e Bnegato sono ricorsivamente enumerabili *
18. Teo15 B e C sono ricorsivamente enumerabili => B ^ C r.e.
19. Teo16 B e C sono ricorsivamente enumerabili => B v C r.e.
20. Def30 Insieme Wn
21. Teo17 Teorema di enumerazione *
22. Def31 Insieme diagonale K e sua funzione caratteristica *
23. Prop3 K è r.e. ma non ricorsivo *
24. Prop4 Se B incluso in N è r.e. esiste R predicato binario ricorsivo primitivo
25. Teo18 Se B è r.e. esiste f ricorsiva primitiva
26. Teo19 f unaria e p.calcolabile e B definito con f sua funzione caratterisitca => B è r.e.
27. Teo20 Teorema di equivalenza
28. Def1 Linguaggio S e suoi elementi
28.1. variabili
28.1.1. input
28.1.1.1. X1,...,Xn insieme potenzialmente infinito
28.1.2. output
28.1.2.1. Y, unica
28.1.3. locali
28.1.3.1. Z1,...,Zn insieme infinito
28.2. etichette
28.2.1. tra [ ] con lettere dell'alfabeto
28.3. istruzioni
28.3.1. lavorano su numeri naturali
28.3.1.1. incremento
28.3.1.2. decremento
28.3.1.2.1. (se V=0 non fa nulla)
28.3.1.3. salto
28.3.1.3.1. IF 𝑉 ≠0 𝐺𝑂𝑇𝑂 𝐿 Se il valore di 𝑉 ≠ 0, esegue l’istruzione etichettata 𝐿, altrimenti procede con la successiva
28.4. funzioni
28.4.1. sono del tipo 𝑓: ℕ 𝑘 → ℕ
28.5. macro
28.5.1. prendono un'istruzione e la sostituiscono con un blocco scritto in linguaggio S
28.5.1.1. salto condizionato
28.5.1.1.1. GOTO A
28.5.1.2. azzeramento
28.5.1.2.1. V<--0
28.5.1.3. copia
28.5.1.3.1. V<--V'
28.5.1.4. assegnazione
28.5.1.4.1. V<--n con n appartenente a N
28.5.1.5. salto generale
28.5.1.5.1. 𝑰𝑭 𝑸(𝑽𝟏,…,𝑽𝒌) 𝑮𝑶𝑻𝑶 L con Q predicato
28.5.1.6. per f funzione calcolabile
28.5.1.6.1. 𝑽←𝒇(𝑽𝟏,…, 𝑽𝒏)
29. Def2 Funzione parziale
29.1. Una funzione 𝑓:𝐷 ⊆ ℕ𝑘 si definisce parziale
30. Def3 Funzione totale
30.1. f si dice totale se 𝐷 = ℕ𝑘 (il dominio è tutto ℕ𝑘).
31. Def4 Predicato
31.1. proprietà verificabile tramite valori di verità (Vero o Falso) definita tramite una funzione totale su tutto ℕ alla k.
31.1.1. sono funzioni totali (non possono essere definite solo per una parte del dominio) che definiscono i valori di verità 1 (se il predicato è vero) e 0 (se falso).
32. Def5 Funzione parzialmente calcolabile e calcolabile
32.1. f è parzialmente calcolabile se esiste un S programma che la calcola, cioè restituisce il valore 𝑓(𝑥1,…,𝑥𝑘) per tutti gli input in cui è definita e non termina per gli altri.
32.2. 𝑓 si dirà calcolabile se è totale e parzialmente calcolabile.
33. Def6 Sintassi formale linguaggio S
33.1. Asserzioni (o statements)
33.1.1. pigra 𝑉 ← 𝑉
33.1.2. incremento
33.1.3. decremento
33.1.4. salto
33.2. Istruzione
33.2.1. è un asserzione oppure un asserzione etichettata
33.3. Programma
33.3.1. è una lista (ennupla) ordinata di istruzioni
33.3.1.1. se la lista è vuota abbiamo un S programma che descrive funzione costantemente uguale a zero f(0,...,0)
33.4. Lunghezza di P
33.4.1. è il numero delle sue istruzioni
33.5. Stato
33.5.1. è un insieme di uguaglianze della forma 𝑉 = 𝑛
33.5.2. nell'insieme descritto c'è 1 uguaglianza per ogni variabile V che occorre nel programma
33.5.2.1. V deve avere un solo valore per ogni stato del programma
33.6. Istantanea
33.6.1. coppia (𝑖,𝜎) con i compreso tra i ed n+1 con 𝑛 che è la lunghezza di 𝒫 e 𝜎 è uno stato di 𝒫.
33.6.2. Istantanea Terminale
33.6.2.1. se 𝑖 = 𝑛 + 1 ovvero caso in cui il programma termina
33.6.3. Istantanea Successiva
33.6.3.1. coppia (𝑗, 𝜏)
33.6.3.1.1. iesima asserzione è pigra
33.6.3.1.2. iesima asserzione è di incremento
33.6.3.1.3. iesima asserzione è di decremento
33.6.3.1.4. iesima asserzione è di salto
34. Def7 Calcolo per un programma P. Stato e istantanea iniziale.
34.1. Si dice calcolo per un programma 𝒫 una successione di istantanee 𝑆1,...,Sk dove per ogni 𝑖 ≥ 1, Si+1 è l’istantanea successiva di 𝑆
34.1.1. se la successione di istantanee è infinita il calcolo è non terminante
34.1.2. se la successione di istantanee è finita e l'ultimo termine della successione è un'istantanea terminale il calcolo è terminante
34.2. Stato iniziale
34.2.1. è una kupla (r1,...,rk) ∈ ℕ alla k, che rappresenta lo stato {X1=r1,...,Xk=rk, 𝑌 = 0} unito { 𝑉 = 0 tale che 𝑉 occorre in 𝒫 e non è in 𝑋1,…,𝑋𝑘 } ossia tutte le altre variabili sono poste a 0
34.3. Istantanea iniziale
34.3.1. coppia (1,𝜎) con 𝜎 stato iniziale.
35. Def8 Funzione calcolabile da un S programma
35.1. Per ogni 𝑘 e ogni input (𝑥1,…,𝑥 𝑘) ∈ ℕ alla k
35.1.1. Ψ 𝒫 alla (𝑘) (x1,…, 𝑥k)
35.1.1.1. y se 𝒫 ha un calcolo terminante che inizia con l'istantanea iniziale corrispondente a (𝑥1,…,𝑥𝑘) e l'istantanea terminale contiene 𝑌 = y
35.1.1.2. ↑, altrimenti
36. Def9 Composizione funzionale *
36.1. Siano 𝑓,g1,…,gk funzioni di 𝑛 variabili
36.1.1. sia ℎ funzione k-aria tale che ∀ x1,…,xn , 𝑓(x1,…,xn) = h( g1(x1,…,xn), g2(x2,…, xn), …,gk( x1,…,xn ) )
36.1.1.1. allora 𝑓 si ottiene per composizione da ℎ,g1,…,gk.
36.2. Se ℎ, 𝑔1,…,𝑔𝑘 sono non totali, 𝑓 sarà definita per tutti e soli i valori di x1,...,xk per cui le funzioni g1...gk sono definte e per cui h di g1,...,gk è definita
37. Teo1 Composizione di funzioni parzialmente calcolabili
37.1. la composizione di funzioni parzialmente calcolabili è parzialmente calcolabile.
37.1.1. **Dim.** supponiamo che 𝑓 si ottenga dalle gi e h per composizione e che le gi e ℎ siano parzialmente calcolabili. Allora 𝑓 è calcolato dal seguente S programma
37.1.1.1. S programma https://prnt.sc/HZjOxEfR7TSL
38. Def10 Ricorsione primitiva *
38.1. è una operazione che si applica alle sole funzioni totali
38.1.1. se 𝑓 è una funzione unaria totale diremo che 𝑓 si ottiene per ricorsione primitiva da k e g binaria totale se e soltanto se
38.1.1.1. 𝑓(0) = 𝑘 con 𝑘 ∈ ℕ
38.1.1.2. ∀ t≥0, 𝑓(t+1) = 𝑔( t, 𝑓 (t) )
38.1.2. caso generale. se 𝑓 è una funzione di n+1 variabili totale diremo che 𝑓 si ottiene per ricorsione primitiva da h e g totale se e soltanto se
38.1.2.1. http://prntscr.com/9ZgZSe6Q-O2J
39. Teo2 Funzione ottenuta per Ricorsione primitiva di fue funzioni n-arie
39.1. se 𝑓 è una funzione di n+1 variabili che si ottiene per ricorsione primitiva da h n-aria e 𝑔 di (n+2)-aria calcolabili, allora 𝑓 è calcolabile.
39.1.1. **Dim.** con il seguente S programma che calcola 𝑓 come funzione (𝑛 +1)-aria:
39.1.1.1. http://prntscr.com/p0zR0eIlUk0p
40. Def11 Classe PRC *
40.1. è un insieme di funzioni **totali ** che
40.1.1. 1. Contiene le funzioni iniziali
40.1.1.1. funzione nulla
40.1.1.1.1. 𝑛(𝑥) = 0
40.1.1.2. funzione di incremento
40.1.1.2.1. 𝑠(𝑥) = 𝑥 +1
40.1.1.3. funzione di proiezione
40.1.1.3.1. funzione di 𝑛 variabili che restituisce la 𝑖-esima
40.1.2. 2. È chiuso rispetto alla composizione e alla ricorsione primitiva
40.1.2.1. ovvero se vale http://prntscr.com/cSQbrLIfVYWR