| |
L'analisi di Alan Turing del concetto di procedura effettiva
Il tentativo di Turing di formalizzare la classe di tutte le procedure effettive
risale al 1936 e portò alla nozione di Macchina di Turing. La sua importanza sta
nel fatto che si tratta della prima anlisi che descriva come ha luogo la computazione;
inoltre tale analisi portò ad una astrazione convincente ed ampiamente accettata
del concetto di procedura effettiva.
È degno di nota che questa analisi di Turing avvenne prima delle invenzioni
dei moderni computer.
Diamo adesso un estratto della analisi di Turing. Si osservi che con il termine
calcolatore Turing si riferisce ad un uomo che sta risolvendo un problema
computazionale in maniera meccanica, e non ad una macchina.
[...] Il procedimento del calcolo è normalmente realizzato scrivendo dei simboli
su carta. [...] Supporò che la computazione avvenga su di un foglio unidimensionale,
ovvero su di un nastro suddiviso in caselle. Supporò inoltre che il numero di
simboli che possono essere scritti sia finito. [...] Le conseguenze di questa restrizione
sul numero di simboli non sono rilevanti. È sempre possibile usare una sequenza
di simboli al posto di un singolo simbolo.
[...] Il comportamento del calcolatore in ogni istante è determinato dai simboli
che egli sta osservando e dal suo stato mentale in quel dato istante. Possiamo supporre
che ci sia un limite B al numero di simboli o celle che il calcolatore riesce ad osservare
in un dato momento. Se vuole osservare qualcosa in più, dovrà effettuare
più osservazioni successive. Supporremo anche che il numero di stati mentali di
cui è necessario tenere conto sia finito. [...] Ancora una volta, tale restrizione
non ha conseguenze rilevanti, poiché l'uso di stati mentali più complessi
può essere evitato annotando più simboli sul nastro.
Immaginiamo di scomporre le operazioni realizzate dal calcolatore in operazioni di
base cosí elementari da risultare difficile una loro ulteriore scomposizione.
Ciascuna di tali operazioni consisterà di un qualche cambiamento del sistema
fisico costituito dal calcolatore e dal suo nastro. Conosciamo lo stato del sistema se
conosciamo la sequenza dei simboli sul nastro, quali di essi sono osservati dal calcolatore,
e lo stato mentale del calcolatore. Possiamo supporre che in ogni operazione di base
non venga alterato più di un simbolo.
[...] A parte questa possibilità di modificare simboli, le operazioni di base
devono includere il cambiamento della distribuzione delle caselle osservate. [...]
Penso sia raggionevole supporre che (le nuove celle) possano essere solo celle la
cui distanza dalla più vicina delle celle precedentemente osservate non
ecceda una certa quantità prefissata L.
[...] Le operazioni di base devono perciò includere:
- Cambiamento del simbolo di una delle caselle osservate;
- Cambiamento di una delle caselle osservate con un'altra casella nello spazio di
L celle di distanza da una di quelle precedentemente osservate.
Potrebbe succedere che qualcuno di questi cambiamenti comporti necessariamente il
cambiamento dello stato mentale. Più in generale, le operazioni di base
dovranno quindi essere le seguenti:
- Un possibile cambiamento (a.) di un simbolo, insieme con un possibile
cambiamento di stato mentale;
- Un possibile cambiamento (b.) di una delle caselle osservate, insieme con un
possibile cambiamento di stato mentale.
Quale operazione venga in effetti eseguita è determinato dallo stato
mentale del calcolatore e dai simboli osservati.
[...] Possiamo adesso costruire una macchina che svolga il lavoro del calcolatore.
Ad ogni stato mentale del calcolatore corrisponde una configurazione della macchina.
La macchina osserverà le B celle corrispondenti alle B celle osservate dal
calcolatore. Ad ogni mossa, la macchina potrà cambiare un simbolo su una
delle celle osservate, o potrà spostare l'attenzione da una delle B celle
osservate ad un'altra distante non più di L celle da una qualunque di
quelle precedntemente osservate. [...]
Successivamente a questa analisi, Turing e Church indipententemente formularono
la cosiddetta Tesi di Church-Turing:
Ogni funzione intuitivamente computabile è computabile con
una Macchina di Turing.
Tale tesi non si presta ad una dimostrazione matematica, poiché identifica
una nozione intuitiva (quella di procedura effettiva), con un concetto matematico
(quello di macchina di Turing). Tuttavia esistono varie ragioni per ritenerla
valida, la più importante delle quali è il fatto che tutti gli altri
modelli computazionali che sono stati proposti come formalizzazione del concetto di
procedura effettiva si sono rivelati essere equivalenti alle Macchine di Turing.
Fra di essi citiamo:
- La classe delle funzioni ricorsive;
- Il lambda calcolo;
- Algoritmi di Markov.
Nonostante le differenze nel formalismo, i vari modelli computazionali hanno
delle caratteristiche comuni, quali:
- Esiste solo una quantità finita di "costrutti" che possono essere combinati
per fornire una descrizione finita di ogni procedura effettiva.
- La computazione procede in maniera discreta, passo-dopo-passo.
- La computazione avviene in maniera deterministica, ovvero senza fare ricorso a
metodi casuali.
- Sebbene non vi sia un limite a priori sulla quantità di memoria o
di tempo a disposizione, ogni computazione finita non deve basarsi su di una
quantità infinita di tempo e/o spazio.
- Ogni passo nella computazione coinvolge solo una quantità finita di
dati.
|