i Miei autori preferiti (David Deutsch, Roger Penrose, e Douglas Hofstadter) tutti di approfondire Tesi di Church-Turing di calcolo, Teoria e, cosa più importante, la sua forte interpretazione: Il Principio di Turing. In questo post per prima cosa spiegherò la tesi di Church-Turing in termini laici.
Quando stavo lavorando alla mia laurea in informatica, ho studiato le macchine di Turing e la tesi di Church-Turing nella mia lezione introduttiva alla Teoria computazionale. Allora ho pensato che fosse una grande perdita di tempo. Volevo solo programmare i computer e non mi importava di meno di questo ragazzo di Turing morto da tempo (né di questo ragazzo di Chiesa) né delle sue stupide macchine teoriche.
Ora che capisco le ramificazioni filosofiche della Tesi di Church-Turing, vorrei aver prestato attenzione in classe! Perché la Tesi di Church-Turing, se vera, ha alcune profonde ramificazioni filosofiche e potrebbe anche dirci qualcosa sulla natura profonda e speciale della realtà.
Automi finiti
Tutti i testi e le classi sulla Teoria del Calcolo iniziano con qualcosa chiamato “Automi finiti.”L’idea di base dietro di loro è abbastanza facile. Basta immaginare una semplice ‘macchina’ che è in grado di fare scelte e muoversi tra gli stati. Ecco un esempio di uno molto semplice che rappresenta la” logica ” di un tornello a gettoni.
In parole povere, questo significa che se si tenta di spingere attraverso un tornello che si è bloccato, non è possibile se non hai prima messo in una moneta. Se avete messo in una moneta, ma non hanno spinto attraverso ancora, monete aggiuntive basta lasciarlo in uno stato sbloccato. Se avete messo in una moneta, allora si può spingere attraverso. Poi si blocca di nuovo per la prossima persona.
Era probabilmente più facile da capire dal diagramma che dalla descrizione.
Gli automi finiti sono in grado di eseguire una logica molto più complicata di questa. Ma questo dovrebbe darti un’idea di base di come funzionano gli automi finiti.
Una cosa da notare è che un automa finito, come quello sopra, è puramente teorico perché esiste solo come un mucchio di bolle e linee su un pezzo di carta. Non è che ci sia una piccola “macchina automa finita” all’interno del tornello che prende queste decisioni. O forse dovrei invece dire che il tornello stesso è la macchina automa finita.
Se volessimo davvero, potremmo probabilmente costruire una macchina nella vita reale che sarebbe un Automa Finito.Non c’è nulla che impedisca a qualcuno di costruirlo come una vera macchina nella vita reale e poi installarlo nel tornello. Questo non è il modo più economico per farlo.
Quindi qualsiasi “programma” che crei come disegno di un automa finito può essere trasformato in un “calcolo” di vita reale che funziona davvero. L’importanza della differenza tra una macchina computazionale che può effettivamente esistere (come un Automa Finito) e una che è solo ipotetica e viola le leggi della fisica diventa importante in un momento.
Macchine più potenti
Man mano che una classe di teoria computazionale progredisce, gli studenti vengono introdotti a “macchine” sempre più complesse che sono più potenti degli automi Finiti. Come mostra la figura a destra, il prossimo più potente è il Pushdown Automata (PDA). Un PDA è in realtà solo un DFA con l’aggiunta di una sorta di “memoria”. Questa memoria consente a un PDA di creare ed eseguire calcoli (o programmi) che un DFA non può.
Il punto chiave è solo che ci sono alcuni tipi di programmi che possono essere scritti per un PDA che non può essere scritto su un Automa Finito Deterministico (DFA). In altre parole, i PDA sono “più potenti “dei DFA perché possono esprimere classi di” programmi “che i DFA non possono.
Quindi esiste una relazione tra DFA e PDA in termini di” potenza computazionale.”Vale a dire è possibile dimostrare che qualsiasi programma scritto su un DFA può anche essere scritto su un PDA, ma che il contrario non è vero.
La prova è nella prova
La prova che un PDA può eseguire tutto ciò che un DFA può è fatto da venire con uno schema con cui la logica di un DFA può essere mappato a un PDA. Poiché un PDA è solo un DFA con memoria, questo non è difficile da fare — basta non usare la “funzione di memoria”.
Ma per quanto riguarda il contrario? Possiamo dimostrare che è impossibile prendere determinati tipi di” programmi ” scritti per un PDA e tradurli in un DFA? Vale a dire, c’è una prova che gli automi Pushdown non possono essere mappati su un Automa Finito? O stiamo solo supponendo che un Automa Finito sia meno potente di un automa Pushdown perché al momento non conosciamo un modo per mappare un PDA a una FDA? Forse c’è un modo per mappare i PDA agli FDA e forse nessuno ha ancora scoperto come farlo? Non è almeno una possibilità?
Come risulta, è possibile dimostrare che un PDA può eseguire determinati tipi di programmi che un DFA non può. Il modo in cui lo faresti è che troveresti un calcolo (cioè un programma) che puoi dimostrare che un DFA non può calcolare e quindi dimostrare che un PDA può calcolarlo.
Potenza computazionale di una macchina
Questo fatto — che ci sono macchine logiche più potenti (PDA) e meno potenti (DFA) — è interessante di per sé.
Ma porta a una domanda filosofica: esiste una “macchina informatica più potente?”
Se ci fosse una “macchina più potente”, come potremmo sapere che una specifica macchina proposta è ” la più potente?”O ci sono solo diversi tipi di macchine informatiche disponibili e devi scegliere quello giusto per il lavoro?
Macchine Turing
Quindi quale macchina è più potente di un PDA?
Come vuole la storia, nello stesso periodo sono stati proposti due tipi molto diversi di “macchine” che erano entrambi dimostrabilmente più potenti dei PDA.
Uno era la macchina di Turing di Alan Turing. L’altra non era tanto una macchina quanto un intelligente insieme di notazioni sviluppate da Alonzo Church che servivano allo stesso scopo dello sviluppo di una macchina. Di queste due “macchine” la macchina di Turing è concettualmente più facile da insegnare, quindi di solito è la macchina che viene insegnata in un corso di Teoria computazionale.
Le macchine Turing sono piccole macchine teoriche divertenti che hanno una testina di lettura/scrittura e un (ipotetico) nastro di carta da cui può leggere o scrivere. In base a ciò che legge la macchina di Turing, mette la macchina di Turing in uno stato di azione che esegue una sorta di combinazione di compiti che consistono nello spostamento della testina di lettura/scrittura in avanti o indietro, nella lettura da una nuova posizione sul nastro o nella scrittura di una nuova posizione sul nastro. Una macchina di Turing assomiglia a questo:
Macchine di Turing e Moderni Computer
Una cosa di interesse è che una Macchina di Turing è, nonostante la superficie delle apparenze, in realtà molto simile a un moderno computer. In un computer moderno l’unità di elaborazione centrale (CPU) è equivalente alla testa di lettura/scrittura di una macchina di Turing. Il chip di memoria (RAM o ROM)è molto simile alle celle del lungo nastro di carta che il tornio può leggere o scrivere. Quindi i computer moderni sembrano essere approssimativamente equivalenti a una macchina di Turing.
Un computer moderno ha un vantaggio rispetto alla macchina di Turing. Un computer moderno non deve spostarsi da una cella della sua “memoria” in ordine sequenziale come fa una macchina di Turing.
Il fatto che una macchina di Turing possa spostare solo una cella alla volta sembra una limitazione significativa, vero? Abbiamo appena visto come alcune macchine sono logicamente “più potenti” di altre: un PDA può eseguire attività computazionali che una FDA non può. Quindi forse ci sono macchine che sono più potenti delle macchine di Turing che possono eseguire attività che le macchine di Turing non possono? E forse il computer moderno — a causa della loro capacità di saltare intorno alla memoria piuttosto che dover passare da una cella all’altra in sequenza-può eseguire alcuni programmi che una macchina di Turing non può?
In effetti i computer moderni hanno in realtà meno potenza espressiva di una Macchina di Turing in virtù del fatto che le macchine di Turing sono state concepite come aventi un nastro di carta infinitamente lungo (cioè memoria infinita) dove come un computer reale avrà sempre memoria finita. Tuttavia, in generale questo fa pochissima differenza in quali tipi di calcoli si possono eseguire poiché gli esseri umani non sono generalmente tutti interessati a calcoli infinitamente lunghi che danno risultati infinitamente lunghi. Ecco perché dico che i computer moderni e le macchine di Turing sono “approssimativamente” equivalenti. Infatti, finché si assume qualsiasi dimensione arbitraria ma finita della memoria, sono esattamente equivalenti in termini di quali tipi di programmi possono essere eseguiti.
La tesi di Turing della Chiesa: Macchina di Turing = Potenza logica massima
Ma che dire della povera Chiesa di Alonzo? La sua povera piccola “macchina” dimenticato perché le macchine Turing sono più facili da insegnare. La sua macchina è forse in grado di esprimere alcuni calcoli /programmi che una macchina di Turing non può, o viceversa?
Non sarebbe una coincidenza stellare se accadesse che Alan Turing e Alonzo Church creassero due tipi completamente diversi di macchine di calcolo teorico ed è successo che erano esattamente identici in termini di quali tipi di calcoli potevano eseguire?
Quindi immaginate la sorpresa di tutti quando Alan Turing fu in grado di produrre una prova che qualsiasi programma scritto per una macchina di Turing poteva anche essere scritto per una macchina di Chiesa e anche una prova che qualsiasi programma scritto per una macchina di Chiesa poteva anche essere scritto per una macchina di Turing.
In effetti, ci sono una serie di tipi proposti di macchine computazionali teoriche. Ad esempio, i teorici hanno provato a consentire a una macchina di Turing di avere più nastri con cui leggere/scrivere. Hanno persino provato a consentire a una macchina di Turing un “foglio” 2-dimensionale con cui leggere e scrivere. I teorici hanno provato tutti i tipi di miglioramenti alle macchine di Turing (e alle macchine della Chiesa).
E finora è stato possibile produrre una prova per ognuno di essi che sono equivalenti a una semplice macchina di Turing.
Sembra una coincidenza selvaggia, vero? E sarebbe una coincidenza selvaggia a meno che non ci sia un limite superiore a quali tipi di calcolo possono essere eseguiti.
Se esiste un tale limite superiore, non sarebbe affatto un caso che la Macchina di Turing e la Macchina di Church e tutte le altre macchine computazionali proposte abbiano la stessa potenza computazionale, poiché in realtà il motivo per cui sono tutte equivalenti è perché abbiamo raggiunto il limite superiore della potenza computazionale.
Ma possiamo dimostrare che non esiste una macchina computazionale là fuori — una che non abbiamo ancora scoperto — che abbia la capacità di eseguire calcoli che una macchina di Turing non può?
Come, esattamente, potremmo produrre una tale prova? Il fatto è che non possiamo dimostrare che non c’è niente di più potente di una macchina di Turing. Quindi, chissà, forse c’è.
Ma il fatto è che non possiamo trovare (o inventare) tali macchine.
Così, dopo un notevole sforzo cercando e fallendo, per trovare un modo per migliorare la potenza delle macchine di Turing, finalmente la tesi Chiesa-Turing è stato accettato anche se non è stato dimostrato di essere vero. La tesi di Church-Turing dice essenzialmente qualcosa del genere:
non È possibile venire con qualsiasi tipo di macchina computazionale in grado di eseguire un programma logico che una normale Macchina di Turing non può.
O, in altre parole:
Macchine di Turing e i loro equivalenti più potenti possibili tipi di calcolo, macchine e non ci sono più potenti di quelli là fuori che noi non conosciamo.
Dopo anni e anni di ricerca su questa tesi, questa Tesi è ancora sostanzialmente valida. Vedremo più avanti che c’è stata una qualche modifica alla Tesi con l’introduzione dei computer quantistici teorici. Ma, fondamentalmente, la Tesi vale ancora oggi. Nessuno ha mai trovato un modo per sovraperformare le macchine di Turing quando si tratta di espressività logica. Macchine Turing sono ancora il campione in carica.
Quindi ora capisci la tesi di Church-Turing. Tuttavia, la tesi di Chiesa-Turing non è davvero del tutto equivalente al principio di Turing. Quindi in un post futuro svilupperò qual è la differenza e quali sono le sue ramificazioni filosofiche.
Note
Il principio di Turing. Così chiamato da Roger Penrose, che non ci crede (almeno non nella forma attuale). È stato sviluppato nel principio di Turing-Deutsch da David Deutsch, che ci crede, almeno nella sua forma.) (Vedi articolo in Wikipedia per maggiori dettagli)