La tesi di Church-Turing si riferisce al concetto di metodo efficiente, sistematico o meccanico in logica, matematica e informatica. È formulata come descrizione del concetto intuitivo di computabilità e, in relazione a funzioni ricorsive generali, è più spesso chiamata tesi di Church. Si riferisce anche alla teoria delle funzioni computer-calcolabili. La tesi è apparsa negli anni '30, quando i computer stessi non esistevano ancora. In seguito prese il nome dal matematico americano Alonso Church e dal suo collega britannico Alan Turing.
Efficienza del metodo per raggiungere il risultato
Il primo dispositivo che somigliava a un computer moderno è stato il Bombie, una macchina creata dal matematico inglese Alan Turing. È stato utilizzato per decifrare i messaggi tedeschi durante la seconda guerra mondiale. Ma per la sua tesi e formalizzazione del concetto di algoritmo, ha utilizzato macchine astratte, in seguito chiamate macchine di Turing. Presentazioni di tesiinteresse sia per i matematici che per i programmatori, poiché questa idea ha ispirato i creatori dei primi computer.
Nella teoria della computabilità, la tesi di Church-Turing è anche conosciuta come la congettura sulla natura delle funzioni calcolabili. Afferma che per qualsiasi funzione calcolabile algoritmicamente sui numeri naturali, esiste una macchina di Turing in grado di calcolarla. O, in altre parole, esiste un algoritmo adatto a questo. Un noto esempio dell'efficacia di questo metodo è il test della tabella di verità per testare la tautologia.
Un modo per ottenere qualsiasi risultato desiderato è chiamato "efficace", "sistematico" o "meccanico" se:
- Il metodo è specificato in termini di un numero finito di istruzioni esatte, ogni istruzione è espressa utilizzando un numero finito di caratteri.
- Funzionerà senza errori, produrrà il risultato desiderato in un certo numero di passaggi.
- Il metodo può essere eseguito da un essere umano senza l'aiuto di qualsiasi attrezzatura diversa da carta e matita
- Non richiede comprensione, intuizione o ingegno da parte della persona che esegue l'azione
In precedenza in matematica, il termine informale "effettivamente calcolabile" era usato per riferirsi a funzioni che possono essere calcolate con carta e matita. Ma la nozione stessa di computabilità algoritmica era più intuitiva di qualsiasi cosa concreta. Ora era caratterizzato da una funzione con argomento naturale, per la quale esiste un algoritmo di calcolo. Uno dei successi di Alan Turing è statorappresentazione di un predicato formalmente esatto, con l'aiuto del quale sarebbe possibile sostituire quello informale, se si utilizzasse la condizione di efficienza del metodo. La chiesa ha fatto la stessa scoperta.
Concetti di base delle funzioni ricorsive
Il cambio di predicati di Turing, a prima vista, sembrava diverso da quello proposto dal suo collega. Ma di conseguenza si sono rivelati equivalenti, nel senso che ciascuno di essi seleziona lo stesso insieme di funzioni matematiche. La tesi di Church-Turing è l'affermazione che questo insieme contiene ogni funzione i cui valori possono essere ottenuti con un metodo che soddisfa le condizioni di efficienza. C'era un' altra differenza tra le due scoperte. Fu che Church considerò solo esempi di numeri interi positivi, mentre Turing descrisse il suo lavoro come la copertura di funzioni calcolabili con una variabile integrale o reale.
Funzioni ricorsive comuni
La formulazione originale della Chiesa afferma che il calcolo può essere eseguito utilizzando il calcolo λ. Ciò equivale all'utilizzo di funzioni ricorsive generiche. La tesi di Church-Turing copre più tipi di calcolo di quanto originariamente pensato. Ad esempio, relativi ad automi cellulari, combinatori, macchine di registrazione e sistemi di sostituzione. Nel 1933, i matematici Kurt Gödel e Jacques Herbrand hanno creato una definizione formale di una classe chiamata funzioni ricorsive generali. Utilizza funzioni in cui è possibile più di un argomento.
Creazione di un metodoλ-calcolo
Nel 1936, Alonso Church creò un metodo di determinazione chiamato λ-calcolo. Era associato ai numeri naturali. All'interno del calcolo λ, lo scienziato ha determinato la loro codifica. Di conseguenza, sono chiamati numeri della Chiesa. Una funzione basata su numeri naturali è stata chiamata λ-calcolabile. C'era un' altra definizione. La funzione della tesi di Church è chiamata λ-calcolabile in due condizioni. La prima suonava così: se era calcolata su elementi della Chiesa, e la seconda condizione era la possibilità di essere rappresentato da un membro del λ-calcolo.
Anche nel 1936, prima di studiare il lavoro del collega, Turing creò un modello teorico per le macchine astratte che ora portano il suo nome. Potrebbero eseguire calcoli manipolando i caratteri sul nastro. Questo vale anche per altre attività matematiche che si trovano nell'informatica teorica, come il calcolo probabilistico quantistico. La funzione della tesi di Church è stata motivata solo in seguito utilizzando una macchina di Turing. Inizialmente, si basavano su λ-calculus.
Calcolabilità delle funzioni
Quando i numeri naturali sono opportunamente codificati come sequenze di caratteri, una funzione sui numeri naturali si dice calcolabile con Turing se la macchina astratta trova l'algoritmo richiesto e stampa questa funzione su nastro. Un tale dispositivo, che non esisteva negli anni '30, in futuro sarebbe stato considerato un computer. La macchina astratta di Turing e la tesi di Church annunciarono un'era di sviluppodispositivi informatici. È stato dimostrato che le classi di funzioni formalmente definite da entrambi gli scienziati coincidono. Pertanto, di conseguenza, entrambe le affermazioni sono state combinate in una. Anche le funzioni computazionali e la tesi di Church hanno avuto una forte influenza sul concetto di computabilità. Sono anche diventati uno strumento importante per la logica matematica e la teoria della dimostrazione.
Giustificazione e problemi del metodo
Ci sono opinioni contrastanti sulla tesi. Numerose prove furono raccolte per l'"ipotesi di lavoro" proposta da Church e Turing nel 1936. Ma tutti i metodi o le operazioni conosciuti per scoprire nuove funzioni effettivamente calcolabili da quelle date erano collegati a metodi di costruzione di macchine, che allora non esistevano. Per dimostrare la tesi di Church-Turing, si parte dal fatto che ogni modello realistico di calcolo è equivalente.
A causa della varietà di analisi diverse, questa è generalmente considerata una prova particolarmente forte. Tutti i tentativi di definire più precisamente la nozione intuitiva di una funzione effettivamente calcolabile si sono rivelati equivalenti. Ogni analisi che è stata proposta ha dimostrato di individuare la stessa classe di funzioni, vale a dire quelle che sono calcolabili dalle macchine di Turing. Ma alcuni modelli computazionali si sono rivelati più efficienti in termini di utilizzo di tempo e memoria per diverse attività. Successivamente si è notato che i concetti base delle funzioni ricorsive e le tesi di Church sono piuttosto ipotetiche.
Tesi M
È importante distinguere tra la tesi di Turing e l'affermazione che tutto ciò che può essere calcolato da un dispositivo informatico può essere calcolato dalla sua macchina. La seconda opzione ha una sua definizione. Gandhi chiama la seconda frase "Tesi M". Dice così: "Tutto ciò che può essere calcolato da un dispositivo può essere calcolato da una macchina di Turing". Nel senso stretto della tesi, è una proposizione empirica il cui valore di verità è sconosciuto. La tesi di Turing e la "Tesi M" sono talvolta confuse. La seconda versione è sostanzialmente errata. Sono state descritte varie macchine condizionali in grado di calcolare funzioni che non sono calcolabili con Turing. È importante notare che la prima tesi non implica la seconda, ma è coerente con la sua falsità.
Implicazione inversa della tesi
Nella teoria della computabilità, la tesi di Church è usata come descrizione della nozione di computabilità da una classe di funzioni ricorsive generali. L'americano Stephen Kleene ha dato una formulazione più generale. Chiamò parzialmente ricorsive tutte le funzioni parziali calcolabili da algoritmi.
L'implicazione inversa è comunemente indicata come la tesi inversa della Chiesa. Sta nel fatto che ogni funzione ricorsiva di interi positivi viene valutata in modo efficiente. In senso stretto, una tesi denota semplicemente una tale possibilità. E in un senso più ampio, astrae dalla domanda se questa macchina condizionale possa esistere in essa.
Computer quantistici
I concetti di funzioni calcolabili e la tesi di Church sono diventate un'importante scoperta per la matematica, la teoria delle macchine e molte altre scienze. Ma la tecnologia è cambiata molto e continua a migliorare. Si presume che i computer quantistici possano eseguire molte attività comuni in meno tempo rispetto a quelli moderni. Ma restano domande, come il problema dell'arresto. Un computer quantistico non può rispondere. E, secondo la tesi di Church-Turing, nessun altro dispositivo informatico.
