Il Funzionalismo di Hilary Putnam

In “On computable numbers, with an application to the Entscheidungsproblem”, saggio del 1937, scritto con l’intento di dare risposta al suddetto problema di decisione per i sistemi formali, formulato da David Hilbert, Turing approderà, con una logica e una lucidità sconcertarti per il periodo, all’idea di Macchina di Turing Universale, capace di imitare il comportamento di qualunque altra, indipendentemente dal tipo di algoritmo che è stata progettata per eseguire, gettando le basi teoriche tanto dell’informatica quanto dell’IA.

Una Macchina di Turing è un dispositivo dotato di un numero finito di configurazioni interne , ciascuna delle quali implica che la macchina si trovi in uno tra un numero finito di stati e che legga un nastro sul quale compaiono certi simboli.
Il nastro della macchina è suddiviso in celle; su ciascuna delle celle può essere stampato un simbolo, tratto da un alfabeto finito, stabilito in precedenza. La macchina di Turing possiede anche un “dispositivo di lettura” che legge il nastro una cella alla volta.
Infine possiede un meccanismo di stampa in grado di:
1)Cancellare il simbolo che compare nella cella letta.
2)Stampare in essa un altro simbolo, preso dall’alfabeto della macchina.
Qualsiasi macchina di Turing è descritta completamente da una tavola di transizione.
Si può assumere che una cella piena possa essere segnata con 1 e una vuota con 0.
Si può, ancora, assumere che una tale macchina funzioni sempre perfettamente.
Un importante elemento della Macchina di Turing è lo stato interno, che è la configurazione memorizzata dalla macchina in base agli ingressi (Input) presentatisi in base a ciò che ha potuto leggere sul nastro. Naturalmente anche gli stati interni sono di numero finito (q0, q1, q2…qm).
Dato il suo stato iniziale e quest’input, la macchina deve operare in modo completamente deterministico, cambiando il suo stato interno oppure conservando lo stesso stato.
Schematicamente le sue operazioni sono:
1)Lettura del simbolo.
2)Cancellazione del simbolo e scrittura di uno nuovo, in base alla lettura o allo stato interno.
3)Determinazione di un nuovo stato interno in base allo stato precedente o al simbolo letto.
4)Spostamento del nastro, o della testina di lettura, avanti o indietro, oppure assenza di spostamento in base allo stato interno o al simbolo letto.
Ogni Macchina di Turing è programmata per eseguire un tipo di calcolo specifico, dispone cioè di una serie di istruzioni che le permettono di eseguire il compito per il quale è stata programmata.
Ogni istruzione deve specificare quale operazione atomica deve essere eseguita, a partire da una determinata configurazione:
configurazione ⟶ operazione atomica.
In generale, poiché una configurazione è rappresentata da una coppia e un’operazione atomica da una terna, un’istruzione ha la forma di una quintupla ordinata. L’ insieme finito di quintuple è detto Tavola di quella Macchina di Turing.
Per avere una tavola di una determinata macchina è indispensabile rispettare la seguente condizione:
“Poiché il calcolo deve essere deterministico, a partire da una singola configurazione, non devono essere applicabili istruzioni diverse”.
La Macchina di Turing Universale è una macchina che legge, codificate su nastro, le istruzioni delle altre macchina di Turing e le simula, operando sul resto del nastro input, come fosse una macchina qualsiasi.
I moderni computer sono Macchine di Turing universali, la cui progettazione logica non è identica a quella data da Turing , il cui scopo era differente. Infatti la necessità di Turing era quella di rispondere alla richiesta di Hilbert, cioè se fosse o meno possibile formulare un procedimento algoritmico per la decisione di computabilità di un equazione diofantea. Per Turing l’Entscheidungsproblem non ha soluzione, per lo meno non una universale.
La validità di un algoritmo deve essere stabilito con mezzi esterni.
L’efficienza di questa macchina virtuale poteva essere misurata mediante il test di Turing, che confrontava il prodotto cognitivo di una macchina con il prodotto cognitivo del cervello. Il test consisteva nel far svolgere lo stesso problema ad una macchina e ad un uomo, e, se entrambi davano lo stesso risultato, allora la macchina superava il test. [...]