[computabilità] Numerabilità delle funzioni calcolabili.
Sono incappato nel seguente risultato.
Le funzioni computabili sono di numero numerabile
ricordo che
ho trovato questa pseudo dimostrazione :
si basa sul fatto che l'insieme delle $f$ aritmetiche è più che numerabile.
Sia $FC={$funzioni calcolabili$}$ e $Alg={$algoritmi che computano le funzioni calcolabili.$}$
poiché $AA a in F EE$ più di un $b in Alg$
ne segue che $|FC|<=|Alg|$. Su questo non ci sono dubbi.
Quindi praticamente il problema che $FC$ è numerabile si può ridurre a dimostrare che $Alg$ è numerabile.
Ora il testo dice che $a in Alg$ è formato da una sequenza di istruzioni generato da stringhe $L$, insieme di tali stringhe è finito oppure numerabile. quindi $Alg$ è al più numerabile e quindi $FC$ è al più numerabile. Ciò mostra che esistono funzioni aritmetiche che non sono calcolabili essendo $FC$ al più numerabile.
non capisco la conclusione posta in grassetto. Come si può dedurre che dal fatto che un algoritmo di perse è finito allora $Alg$ è al più numerabile?
grazie
Le funzioni computabili sono di numero numerabile
ricordo che
ho trovato questa pseudo dimostrazione :
si basa sul fatto che l'insieme delle $f$ aritmetiche è più che numerabile.
Sia $FC={$funzioni calcolabili$}$ e $Alg={$algoritmi che computano le funzioni calcolabili.$}$
poiché $AA a in F EE$ più di un $b in Alg$
ne segue che $|FC|<=|Alg|$. Su questo non ci sono dubbi.
Quindi praticamente il problema che $FC$ è numerabile si può ridurre a dimostrare che $Alg$ è numerabile.
Ora il testo dice che $a in Alg$ è formato da una sequenza di istruzioni generato da stringhe $L$, insieme di tali stringhe è finito oppure numerabile. quindi $Alg$ è al più numerabile e quindi $FC$ è al più numerabile. Ciò mostra che esistono funzioni aritmetiche che non sono calcolabili essendo $FC$ al più numerabile.
non capisco la conclusione posta in grassetto. Come si può dedurre che dal fatto che un algoritmo di perse è finito allora $Alg$ è al più numerabile?
grazie
Risposte
Ti dice che un algoritmo qualsiasi può essere codificato come una stringa (finita) in un qualche linguaggio (finito) $Sigma$. Ciò vuol dire che la cardinalità dell'insieme di tutti gli algoritmi è al più pari a quella di $Sigma^star$ che si può dimostrare essere numerabile (per $Sigma$ finito).
Una dimostrazione più rigorosa procederebbe fissando un linguaggio in cui scrivere questi algoritmi e mostrando che è possibile associare iniettivamente (in realtà anche con una bijezione) ad ogni algoritmo un numero naturale. Questo passaggio è una tecnica standard detta aritmetizzazione. È un passo necessario nella dimostrazione, tra le altre cose, dell'indecidibilità del problema dell'arresto, come anche del I teorema di Goedel.
Una dimostrazione più rigorosa procederebbe fissando un linguaggio in cui scrivere questi algoritmi e mostrando che è possibile associare iniettivamente (in realtà anche con una bijezione) ad ogni algoritmo un numero naturale. Questo passaggio è una tecnica standard detta aritmetizzazione. È un passo necessario nella dimostrazione, tra le altre cose, dell'indecidibilità del problema dell'arresto, come anche del I teorema di Goedel.
Salve Deckard e grazie per la risposta.
Il teorema di Goedel a cui ti riferisci è quello di incompletezza? mentre l'altro è della fermata, giusto?
Il teorema di Goedel a cui ti riferisci è quello di incompletezza? mentre l'altro è della fermata, giusto?
"Kashaman":
Salve Deckard e grazie per la risposta.
Il teorema di Goedel a cui ti riferisci è quello di incompletezza? mentre l'altro è della fermata, giusto?
Sì (il primo). L'altro è il teorema dell'arresto, "della fermata" suona un po' male e non l'ho mai sentito tradotto in questo modo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo