Quante sono le funzioni calcolabili?

- Quante sono le funzioni aritmetiche (Nn → N)?
- Quante sono le funzioni calcolabili?
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #1
öö ô
ô
öö ô
ô
ô
öö ô
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #2
öö
öö
öö
1
2
3
4
5
6
Le basi teoriche dell’IA: Teoria della computabilità - 3
ô
ô
ôô
ô
ô
1
2
3
4
5
6
Trasparenza #3
öö ô
ô
öö ô
ô
ô
öö ô
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #4
Definizione - A si dice equipotente a B (A ≈ B) sse esiste ϕ biiettiva ϕ: A → B
Definizione - Se A e B sono equipotenti si dice che hanno stessa cardinalità o lo stesso numero
cardinale (in simboli Card(A) = Card(B))
Definizione - Se A è equipotente a un sottoinsieme di B (se cioè esiste ϕ iniettiva ϕ: A → B) si
dice che la cardinalità di A è minore o uguale a quella di B (in simboli Card(A) ≤ Card(B)).
Se A è finito: Card(A) = n (dove n è il numero di elementi di A)
Chiamiamo infinito qualunque insieme che si può porre in corrispondenza biunivoca con una sua
parte propria; finito altrimenti
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #5
Insiemi numerabili
Definizione - A si dice numerabile sse può essere posto in corrispondenza biunivoca con N
ossia: sse esiste ϕ biiettiva ϕ: N → A (oppure sse esiste ψ biiettiva ψ: A → N)
Quindi: se A è numerabile, i suoi elementi possono essere disposti in una successione infinita
senza ripetizioni (e viceversa).
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #6
Sono numerabili ad esempio:
- l’insieme dei numeri naturali pari
- l’insieme dei numeri dispari
- l’insieme delle potenze di 2
- l’insieme dei numeri primi (tutti sottoinsiemi propri di N)
Infatti:
0, 2, 4, 6, 8, 10, 12, 14, 16,......
1, 3, 5, 7, 9, 11, 13, 15, 17,......
1, 2, 4, 8, 16, 32, 64, 128, 256,......
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,......
Anche l’insieme Z dei numeri interi relativi è numerabile:
0, +1, –1, +2, –2, +3, –3, +4, –4,......
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #7
Sia A0, A1, A2,..., An,... una successione infinita di insiemi numerabili
La loro unione è a sua volta numerabile:
A0
a 00 ,
a01 ,
a 02 ,
a 03 ,
a04 ,
…
A1
a 10 ,
a11 ,
a 12 ,
a 13 ,
a14 ,
…
A2
a 20 ,
a21 ,
a 22 ,
a 23 ,
a24 ,
…
A3
a 30 ,
a31 ,
a 32 ,
a 33 ,
a34 ,
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #8
Sia A0, A1, A2,..., An,... una successione infinita di insiemi numerabili
La loro unione è a sua volta numerabile:
A0
a 00 ,
a01 ,
a 02 ,
a 03 ,
a04 ,
…
A1
a 10 ,
a11 ,
a 12 ,
a 13 ,
a14 ,
…
A2
a 20 ,
a21 ,
a 22 ,
a 23 ,
a24 ,
…
A3
a 30 ,
a31 ,
a 32 ,
a 33 ,
a34 ,
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #9
Analogamente, il prodotto cartesiano di due insiemi numerabili è un insieme numerabile
Si dimostra anche che:
l’insieme di tutte le n-ple di elementi di un insieme numerabile A è numerabile
Infatti:
2
A è numerabile
3
2
A = A × A è numerabile
…
k+1
k
A
= A × A è numerabile
…
i
L’unione di tutti gli A è numerabile
(perché è una successione infinita di insiemi numerabili)
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #10
Linguaggio L:
- alfabeto A (finito o numerabile)
- insieme E di espressioni (stringhe finite di elementi dell’alfabeto)
L’insieme E delle espressioni di un linguaggio è finito o numerabile
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #11
Insiemi più che numerabili
- L’insieme G costituito da tutte le successioni di 0 e 1 è più che numerabile
per assurdo:
ϕ(0)
ϕ(1)
ϕ(2)
ϕ(3)
ϕ(4)
ϕ(5)
….
0
1
0
1
1
1
…
1
0
1
1
1
1
…
Le basi teoriche dell’IA: Teoria della computabilità - 3
1
1
1
0
1
0
…
0
0
1
0
0
0
…
0
1
1
1
1
0
…
1
1
0
0
0
1
…
…
…
…
…
…
…
…
Trasparenza #12
Insiemi più che numerabili
- L’insieme G costituito da tutte le successioni di 0 e 1 è più che numerabile
per assurdo:
ϕ(0)
ϕ(1)
ϕ(2)
ϕ(3)
ϕ(4)
ϕ(5)
….
0
1
0
1
1
1
…
1
0
1
1
1
1
…
Le basi teoriche dell’IA: Teoria della computabilità - 3
1
1
1
0
1
0
…
0
0
1
0
0
0
…
0
1
1
1
1
0
…
1
1
0
0
0
1
…
…
…
…
…
…
…
…
Trasparenza #13
Insiemi più che numerabili
- L’insieme G costituito da tutte le successioni di 0 e 1 è più che numerabile
per assurdo:
ϕ(0)
ϕ(1)
ϕ(2)
ϕ(3)
ϕ(4)
ϕ(5)
….
0
1
0
1
1
1
…
1
0
1
1
1
1
…
1
1
1
0
1
0
…
0
0
1
0
0
0
…
0
1
1
1
1
0
…
1
1
0
0
0
1
…
…
…
…
…
…
…
…
1 1 0 1 0 0 …..
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #14
- L’insieme R dei numeri reali è più che numerabile
per assurdo:
ϕ(0)
ϕ(1)
ϕ(2)
ϕ(3)
ϕ(4)
ϕ(5)
….
0,
0,
0,
0,
0,
0,
5
9
0
1
1
7
…
3
2
5
1
7
7
…
8
3
8
6
5
4
…
6
3
3
3
0
0
…
3
1
1
9
5
0
…
1
4
0
4
0
1
…
…
…
…
…
…
…
…
- se ≠ 5 ⇒ 5
- altrimenti 8
8 5 5 5 8 5 ….
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #15
- L’insieme P(N) dei sottoinsiemi di N è più che numerabile
Si definisce una funzione biiettiva ϕ: P(N) → G:
A = {3, 5, 9, 12}
B = {0, 2, 4, 6, 8,...}
C = {1, 2, 4, 8, 16,...}
ϕ(A) = 0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,0,....
ϕ(B) = 1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,....
ϕ(C) = 0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,...
n
- L’insieme Φ delle funzioni di tipo N → N è più che numerabile
(appartengono a Φ le funzioni caratteristiche di tutti i sottoinsiemi di N)
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #16
Insiemi numerabili
Insiemi più che numerabili
Insieme N dei numeri naturali
Insieme R dei numeri reali
Insieme I dei numeri irrazionali
Insiemi P e D dei numeri pari e dispari
Insieme dei punti di una retta
Insieme Q dei numeri quadrati
Insieme dei numeri primi
Insieme dei punti di un segmento
Insieme delle potenze di 2
Insieme dei punti di un quadrato
Insieme Z dei numeri interi
Insieme dei punti di un cubo
Insieme delle frazioni
Insieme P(N) potenza di N
Insieme Q dei numeri razionali
Insieme delle proprietà di N
Insieme delle relazioni in N
Insieme S delle successioni di 0 e 1
costituite da 0 da un certo punto in poi
Insieme F delle n-ple di numeri naturali Insieme G delle successioni di 0 e 1
Insieme delle espressioni di un
Insieme Φ delle funzioni di tipo
linguaggio
N→N
Insieme prodotto cartesiano di due
Insieme delle funzioni continue di
insiemi numerabili
tipo R → R
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #17
“Incalcolabilità” della calcolabilità
L’insieme di tutti gli algoritmi è numerabile (v. sopra)
n
Quindi: l’insieme delle funzioni aritmetiche (di tipo N → N) che sono calcolabili per mezzo
di un algoritmo è numerabile
n
L’insieme di tutte le funzioni di tipo N → N è più che numerabile (v. sopra)
Quindi:
n
Esistono infinite funzioni aritmetiche (di tipo N → N)
che non sono calcolabili per mezzo di un algoritmo
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #18
Perché le funzioni parziali?
l’insieme delle funzioni aritmetiche a un argomento (di tipo N → N) totali che sono
calcolabili per mezzo di un algoritmo è numerabile
quindi:
l’insieme ∆ degli algoritmi che calcolano funzioni aritmetiche a un argomento
(di tipo N → N) totali è numerabile
quindi:
esiste una funzione biettiva ϕ: N → ∆
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #19
ma:
ϕ non è computabile
ϕ(1) = Alg1
ϕ(2) = Alg2
ϕ(3) = Alg3
…
Sia la funzione ϕi (a un argomento) calcolata da Algi
Quindi ϕ enumera (con ripetizioni) tutte di tipo N → N totali:
ϕ(1) → ϕ1
ϕ(2) → ϕ2
ϕ(3) → ϕ3
…
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #20
per assurdo: assumiamo che ϕ sia computabile
ne segue che la funzione:
f(x) = ϕx(x) + 1
è computabile:
inizio
prendi in input x
a partire da x
ottieni Algx
dai x in input ad Algx ed
esegui
il calcolo – metti in y
l’output che ottieni
aggiungi 1 a y
produci in output y
fine
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #21
ma f è diversa da ogni ϕi:
0
1
2
3
4 .....
ϕ0 ϕ0(0) ϕ0(1) ϕ0(2) ϕ0(3) ϕ0(4) .....
ϕ1 ϕ1(0) ϕ1(1) ϕ1(2) ϕ1(3) ϕ1(4) .....
ϕ2 ϕ2(0) ϕ2(1) ϕ2(2) ϕ2(3) ϕ2(4) .....
ϕ3 ϕ3(0) ϕ3(1) ϕ3(2) ϕ3(3) ϕ3(4) .....
....
....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
Infatti se, secondo l’ipotesi d’assurdo, supponessimo che, per qualche k, f = ϕk, si avrebbe:
f (k) = ϕk(k) = ϕk(k) + 1
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #22
l’insieme delle funzioni aritmetiche a un argomento (di tipo N → N) parziali che sono
calcolabili per mezzo di un algoritmo è numerabile
quindi:
esiste una funzione biettiva ϕ: N → ∆
nel caso di funzioni parziali però ϕ può essere computabile
infatti:
f (k) = ϕk(k) = ϕk(k) + 1
non è una contraddizione se ϕk(k) = ⊥
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #23
inizio
prendi in input x
a partire da x
ottieni Algx
dai x in input ad Alg x ed
esegui
il calcolo – metti in y
l’output che ottieni
aggiungi 1 a y
produci in output y
fine
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #24
inizio
prendi in input x
prendi in input x
a partire da x
ottieni Algx
a partire da x
ottieni Alg x
dai x in input ad Alg x ed
esegui
il calcolo – metti in y
l’output che ottieni
dai x in input ad Algx ed
esegui
il calcolo – metti in y
l’output che ottieni
aggiungi 1 a y
aggiungi 1 a y
produci in output y
produci in output y
fine
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #25
inizio
prendi in input x
prendi in input x
prendi in input x
a partire da x
ottieni Algx
a partire da x
ottieni Alg x
a partire da x
ottieni Algx
dai x in input ad Alg x ed
esegui
il calcolo – metti in y
l’output che ottieni
dai x in input ad Algx ed
esegui
il calcolo – metti in y
l’output che ottieni
dai x in input ad Alg x ed
esegui
il calcolo – metti in y
l’output che ottieni
aggiungi 1 a y
aggiungi 1 a y
aggiungi 1 a y
produci in output y
produci in output y
produci in output y
fine
Le basi teoriche dell’IA: Teoria della computabilità - 3
Trasparenza #26