Tesi di Church Turing

Nella teoria della calcolabilità la tesi di Church-Turing è un ipotesi che intuitivamente dice che se un problema si può calcolare, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo (cioè di calcolarlo). Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.

Quanto affermato dalla tesi di Church-Turing vale ovviamente anche per tutti i modelli di calcolo equivalenti alle Macchine di Turing, per cui ad esempio una formulazione equivalente della tesi è dire che funzioni ricorsive e funzioni calcolabili sono la stessa cosa.

La tesi di Church-Turing è ormai universalmente accettata, ma non può essere dimostrata.

Ciò che può essere calcolato da un essere umano può essere calcolato anche da una macchina

A cui si possono unire le seguenti affermazioni collegate alla prima:

Ciò che può essere calcolato da una macchina è calcolabile cicli di operazioni e/o con funzioni ricorsive o parzialmente ricorsive.

Ciò che puo' essere calcolato da un essere umano è calcolabile con cicli e/o funzioni ricorsive oparzialmente ricorsive.

E' importante sottolineare che la tesi di Church-Turing non è dimostrabile come un teorema matematico, è semplicemente un'ipotesi sui procedimenti usati dal cervello umano per risolvere i problemi.

Come ultima citazione (lo prometto) riporto la versione di Hardy che trovo abbastanza divertente:

In fondo tutti i matematici sono isomorfi (nel senso che compiono più o meno le stesse operazioni)

Da cui deriva la tesi Church-Turing versione isomorfismo:

Supponiamo che esista un metodo che un essere senziente possa seguire per risolvere un problema e che permetta di ottenere un risultato in ogni caso e in un tempo finito. Allora esiste un qualche programma che da esattamente le stesse risposte del metodo dell'essere senziente.

e non si ferma quì:

Inoltre il processo mentale ed il programma sono isomorfi, nel senso che a un qualche livello, vi è una corrispondenza tra i passi che vengono compiuti nella macchina e nel cervello.

Credo che a questo punto sia chiara l'importanza di questa tesi. Tanto per iniziare ci suggerisce che se riusciamo a risolvere un problema (noi esseri senzienti), esisterà un programma elaborato da una macchina, che lo potrebbe risolvere al posto nostro. Ma soprattuto fa sorgere il dubbio se sia possibile estendere il ragionamento non solo ai problemi matematici, ma anche a tutti gli altri e quindi se sia possibile realizzare una macchina pensante.

Il Teorema dell’Arresto
Esistono delle cose che una macchina di Turing non può fare? Dei problemi che non
può risolvere?
Ebbene: non esiste una macchina di Turing che è in grado di determinare se un’altra
generica macchina di Turing si fermerà mai o no.
Ragionando generalmente: una macchina per determinare se un’altra macchina si
ferma, deve in qualche modo “emularne” il comportamento, ma se ne emula il
comportamento allora se la macchina emulata non si dovesse arrestare neanche la
macchina emulatrice si potrebbe arrestare…

Si bhe ... ma io che sono un essere di pura pasta al sugo ti dico: Cosa vuol dire infinito?
Un programma che non termina mai ad esempio è infinito?

coscienza specchio intendi il riflesso sul mondo del nsotro stato interiore? ossia, realtà creata prima dentro e poi fuori?

infinito, per l'umano significa "infinitamente ciclico con possibilità di movimento a spirale"
Una macchina può fare quello che fà l'uomo, ma non se ne renderà mai conto, quindi non farà mai esattamente quello che fa l'uomo, quello che non riuscirà a fare è l'infinito.


..ah, la spirale è l'autocoscienza.. e una macchina non può salire la spirale.

coscienza collettiva, personale, insomma autocoscenza nei suoi diversi gradi di altezza (di spirale percorsa).

Per questo siamo infiniti.

Una macchina può fare quello che fà l'uomo, ma non se ne renderà mai conto, quindi non farà mai esattamente quello che fa l'uomo, quello che non riuscirà a fare è l'infinito.

Dunque: per ora non esiste meccanismo di calcolo automatizzabile (meccanico, elettronico o biologico) più potente di una macchina di turing. Tutti i meccanismi alternativi sono modelli equivalenti. Anche i pc quantistici o biologici e di questo sono certo.

...sei proprio sicuro che riusciamo a fare l'infinito?!