Filosofia dell'informazione/Computazione

La nascita dei computer moderni

I primi calcolatori non avevano programmi già salvati in memoria: per eseguire operazioni diverse era necessario modificare manualmente i collegamenti. Il primo a pensare a un calcolatore con istruzioni codificate salvate all'interno della memoria fu Alan Turing; nel 1935, in un articolo intitolato On Computable Numbers, with an Application to the Entscheidungsproblem. Proprio da questo articolo nasceva l'idea della macchina di Turing universale, una macchina dalla memoria infinita capace di contenere sia dati che istruzioni, dotata di uno scanner in grado di muoversi nella memoria, simbolo dopo simbolo, leggendone o scrivendone altri; in questa macchina il semplice inserimento di programmi diversi poteva condurre a risultati diversi.

Il contenuto dell'articolo di Turing

L'articolo di Turing dava avvio alla moderna scienza della computazione, dal momento che al suo interno egli affermava che ci fossero problemi matematici che la sua macchina non era in grado di risolvere, come l’Entscheidungsproblem, il problema della decisione.

Le modifiche alla macchina di Turing, la realizzazione e la commercializzazione

A partire da quel momento sia negli Stati Uniti che nel Regno Unito, grazie rispettivamente a John von Neumann e Max Newman, cominciarono a nascere progetti per trasformare l’idea di Turing in realtà. Il primo risultato in tal senso si ebbe il 21 giugno 1948 nei laboratori dell'Università di Manchester: nasceva il Manchester Baby; tre anni dopo il Ferranti Mark I, la versione commerciale del Baby, veniva messa in vendita: tra queste, nove furono distribuite in Europa. Il secondo a raggiungere il risultato fu l’UNIVAC negli USA; un prototipo simile a quello di Manchester dell’Università di Cambridge fu l’EDVAC, commercializzato con il nome di LEO lo stesso anno. Il primo calcolatore commerciale che riusciva a immagazzinare sia i dati che i programmi fu l’IBM 701, messo in commercio nel 1953.

Cos'è una macchina di Turing

Come detto precedentemente, una macchina di Turing è una macchina dalla memoria infinita capace di contenere sia dati che istruzioni, dotata di uno scanner in grado di muoversi nella memoria, simbolo dopo simbolo, leggendo o scrivendo altri simboli: i simboli sono inseriti in quadrati a loro volta inglobati in un nastro; sono letti uno alla volta e possono essere scelti da qualunque alfabeto (si può scegliere di usare, per esempio, "1" e "0").

Esempio del modo in cui avviene una scansione in una macchina di Turing.

Il nastro su cui sono immagazzinati i dati serve sia da dispositivo di input sia di output e contiene anche il programma da eseguire; all'inizio il nastro deve essere scritto con un numero finito di simboli (anche se il seguito può essere vuoto) e la loro elaborazione può continuare all'infinito. Le macchine che hanno le caratteristiche di una macchina di Turing ma che hanno un nastro limitato vengono dette automi a stati finiti.

Le operazioni di base di una macchina di Turing

Ogni macchina di Turing, tramite il lettore, esegue le stesse operazioni di base, che sono logicamente semplici. Esse sono:

• Cancellazione: la capacità di cancellare ciò che è scritto sul nastro;
• Scrittura: la capacità di scrivere un simbolo, dopo averne eventualmente cancellato il contenuto;
• Spostamento: la capacità di spostarsi all'analisi del quadrato immediatamente a destra o a sinistra di quello esaminato.

Le operazioni più complesse sono una concatenazione di queste semplici operazioni, con l'aggiunta dello "Stop" e del "Cambio stato", ovvero la capacità di un dispositivo interno allo scanner di modificare la sua posizione da una zona etichettata a un'altra. Questo meccanismo funziona come memoria e permette di ricordare simboli visti nelle caselle precedenti.

Dal momento che la macchina di Turing è un congegno astratto, nessun computer moderno è in grado di calcolare qualcosa che la macchina di Turing non possa calcolare proprio perché quest'ultima ha capacità "potenzialmente" infinite.

Esempio di un programma su una macchina di Turing

Nell'articolo di Turing è possibile trovare un esempio del funzionamento della macchina che brevemente viene descritto di seguito.

Il programma scriverà su un nastro bianco in modo alternato una sequenza di 0 e 1 lasciando uno spazio vuoto ogni volta che viene completato un processo di scrittura; affinché ciò avvenga si fa uso di 4 stati di memoria (da 1 a 4), le cui operazioni possono essere descritte nel modo seguente:

1. Se il quadrato è bianco, scrittura di 0 e spostamento a destra, poi istruzione 2;
2. Se il quadrato è bianco, spostamento a destra poi istruzione 3;
3. Se il quadrato è bianco, scrittura di 1 e spostamento a destra, poi istruzione 4;
4. Se il quadrato è bianco, spostamento a destra, poi istruzione 1.

Non viene spiegato da Turing in che modo la macchina capisca di dover cambiare istruzione, dal momento che questa era un'astrazione e non era necessario.

Computazione umana

Quando Turing scrisse l'articolo con cui nacque la sua macchina, il calcolatore non era una macchina ma un essere umano, un assistente matematico che calcolava a mente. Molti calcolatori umani vennero usati nel mondo governativo, commerciale o della ricerca: essi facevano i calcoli che al giorno d'oggi vengono fatti dai computer. Con il termine computing machine (letteralmente: macchina calcolante) si andò via via indicando ciò che meccanizzava il lavoro dei calcolatori umani: erano, in effetti, degli ometti che facevano i calcoli più velocemente, paragonabili alle moderne calcolatrici. A partire dagli anni Quaranta del Novecento, i fisici e gli ingegneri cominciarono ad avere la necessità di calcolatori più veloci, grandi e automatici; nei primi anni Cinquanta, invece, la parola inglese computer cominciò una fase in cui il suo significato traslò dall'indicare il semplice "calcolatore umano" a ciò che intendiamo oggi per computer; nella fase transizionale si era soliti far precedere la parola dagli aggettivi "elettronico" o "digitale".

La nascita del Computer moderno

Come sanno tutti coloro che possono utilizzare un personal computer, il modo in cui la macchina esegue il compito desiderato è aprire il programma appropriato memorizzato nella memoria del computer.

I primi computer elettronici su larga scala, ad esempio, il British Colossus (1943) e l'americano ENIAC (1945), non memorizzavano i programmi in memoria. Per configurare questi computer per una nuova attività, era necessario modificare alcuni dei collegamenti della macchina, reindirizzare i cavi a mano e impostare gli interruttori. Il principio base del computer moderno, ossia, l'idea di controllare le operazioni della macchina per mezzo di un programma di istruzioni codificate e memorizzate nella memoria del computer fu pensato da Alan Turing nel 1935.

La sua astratta "macchina di calcolo universale", presto nota semplicemente come la Universal Turing machine (UTM), consiste in una memoria senza limiti, in cui sono memorizzati sia i dati che le istruzioni, e uno scanner che si muove avanti e indietro nella memoria, simbolo per simbolo, leggendo ciò che trova e scrivendo ulteriori simboli.

Inserendo diversi programmi nella memoria, la macchina è fatta per eseguire calcoli diversi. L'idea di Turing di una macchina di calcolo universale a programma memorizzato è stata promulgata negli Stati Uniti da John von Neumann e nel Regno Unito da Max Newman, i due matematici che erano in gran parte responsabili della collocazione della macchina universale di Turing nelle mani di ingegneri elettronici.

Nel 1945, diversi gruppi in entrambi i paesi avevano intrapreso la creazione di una macchina di Turing universale nell'hardware. La corsa per ottenere il primo computer elettronico memorizzato è stata vinta dalla Manchester University. Nel 1951, i computer con programmi memorizzati elettronici avevano ha iniziato ad arrivare sul mercato.

Il primo modello in vendita fu il Ferranti Mark I. Nove delle macchine Ferranti furono vendute, in Gran Bretagna, Canada, Olanda e Italia, il primo fu installato presso l'Università di Manchester nel febbraio del 1951.

Anche il computer LEO fece il suo debutto nel 1951; LEO era una versione commerciale del prototipo della macchina EDSAC, che all'Università di Cambridge nel 1949 era diventato il secondo computer elettronico memorizzato per funzionare. Nel 1953 arrivò l'IBM 701, il primo computer elettronico di programma memorizzato prodotto in serie della società di von Neumann.

In seguito Turing introdusse le sue macchine di astratte in un famoso articolo intitolato "Sui numeri computabili, con un'applicazione per il problema "Entscheidung" (pubblicato nel 1936). Turing si riferiva alle sue macchine astratte semplicemente come "macchine informatiche" - la società americana Aldozo, che li ha soprannominati "macchine di Turing". Inoltre, Turing ha tracciato aree della matematica che si trovano al di fuori della portata dell'UTM

Ha dimostrato che non tutti i problemi matematici con precisione affermata possono essere risolti da una macchina di Turing. Uno di questi è l'Entscheidungsproblem - "problema decisionale".

Questa scoperta ha causato il caos con l'opinione matematica e filosofica ricevuta. Il lavoro di Turing - insieme al lavoro contemporaneo di Church (1936a, 1936b) - ha avviato l'importante ramo della logica matematica che indaga e codifica i problemi "troppo difficili" per essere risolti dalla macchina di Turing.

Cos'è una macchina di Turing?

Una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, è un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e scrivere dei simboli. La macchina di Turing consiste in una memoria senza limiti e uno scanner che si muove avanti e indietro nella memoria, simbolo per simbolo, leggendo ciò che trova e scrivendo ulteriori simboli.

La memoria consiste in un nastro diviso in quadrati. Ciascuna casella può essere vuota o può contenere un singolo simbolo, "0" o "1", ad esempio, o qualche altro simbolo preso da un alfabeto infinito. Lo scanner è in grado di esaminare solo un quadrato di nastro alla volta (il "quadrato scansionato"). Il nastro è il supporto di memorizzazione generico della macchina, che funge da veicolo per l'input e l'output e come memoria di lavoro per memorizzare i risultati dei passaggi intermedi del calcolo.

Il nastro può contenere anche un programma di istruzioni. L'input che è inscritto sul nastro prima dell'inizio del calcolo deve essere composto da un numero finito di simboli. Tuttavia, il nastro stesso ha una lunghezza illimitata - dal momento che l'obiettivo di Turing era quello di mostrare che ci sono compiti che queste macchine non sono in grado di eseguire, anche con memoria di lavoro illimitata e tempo illimitato.

Le operazioni base di una macchina di Turing

Ogni macchina di Turing ha lo stesso piccolo repertorio di operazioni di base (o "atomiche"). Questi sono logicamente semplici. Lo scanner contiene meccanismi che consentono di cancellare il simbolo sul quadrato scansionato e di spostare la posizione di un quadrato a sinistra oppure a destra. La complessità dell'operazione si ottiene concatenando un gran numero di questi semplici calcoli.

Un dispositivo all'interno dello scanner è in grado di adottare un numero di posizioni diverse. Questo dispositivo può essere concettualizzato come composto da un quadrante con un numero infinito di posizioni, etichettato "a", "b", "c", ecc. Il dispositivo funziona come una semplice memoria. Come disse Turing, alterando il suo stato "la macchina può effettivamente ricordare alcuni dei simboli che ha" visto "(scansionato) in precedenza" (1936: 231). Ad esempio, un quadrante con due posizioni può essere utilizzato per mantenere una registrazione di quale cifra binaria, 0 o 1, è presente sul quadrato che lo scanner ha appena lasciato. Se un quadrato potrebbe anche essere vuoto, è necessario un quadrante con tre posizioni.

I computer disponibili in commercio sono cablati per eseguire operazioni di base notevolmente più sofisticate rispetto a quelle di una macchina di Turing: aggiungere, moltiplicare, decrementare, store-ataddress, branch e così via. L'elenco preciso delle operazioni di base varia da produttore a produttore. È un fatto notevole che nessuno di questi computer è in grado di calcolare l'UTM. Nonostante l'austera semplicità delle macchine di Turing che a loro volta sono ( macchine astratte) capace di calcoli che nessun computer reale potrebbe eseguire.

Calcolo Umano

Il termine "macchina calcolatrice" era usato per riferirsi a macchine calcolatrici che meccanizzavano elementi del lavoro del computer umano. Questi erano in effetti omuncoli, calcolavano più rapidamente di un computer umano non assistito, ma non facevano nulla che in teoria non potesse essere fatto da un impiegato umano che lavorasse in modo efficace.

Le prime macchine di calcolo erano in qualche modo simili alle calcolatrici manuali non programmabili di oggi: non erano automatiche e ogni fase - ogni aggiunta, divisione e così via - veniva avviata manualmente dall'operatore umano. Per un calcolo complesso, potrebbero essere necessarie diverse dozzine di computer umani, ciascuno dotato di una macchina informatica da tavolo. Negli anni '40, tuttavia, la scala di alcuni calcoli richiesti dai fisici e dagli ingegneri era diventata così grande che il lavoro non poteva essere fatto facilmente in un tempo ragionevole nemmeno da una stanza piena di computer umani con macchine desktop.

La necessità di sviluppare macchine per il calcolo automatico ad alta velocità e su larga scala era pressante. Tra la fine degli anni '40 e l'inizio degli anni '50, con l'avvento delle macchine di calcolo elettronico, la frase "computer computing" cedette gradualmente a "computer". Durante il breve periodo in cui coesistevano i vecchi e nuovi significati del "computer", il pre fi x "elettronico" o "digitale" di solito erano usati per distinguere la macchina da quella umana. Come affermato da Turing, le nuove macchine elettroniche erano "destinate a eseguire qualsiasi regola del pollice che avrebbe potuto essere eseguita da un operatore umano che lavorava in modo disciplinato ma non intelligente" (Turing 1950: 1).

Fotogrammi principali, laptop, calcolatrici tascabili, palmari - tutti eseguono un lavoro che un operatore umano può fare, se lui o lei lavora abbastanza a lungo e ha una scorta abbondante di carta e matite. La macchina di Turing è un'idealizzazione del computer umano (Turing 1936: 231).

In conclusione Wittgenstein disse: Le "macchine" di Turing sono umani che calcolano. (Wittgenstein 1980: §1096)

L'Entscheidungsproblem

L'Entscheidungsproblem, o problema decisionale, era la principale preda di Turing in "Numeri OnComputabili". Il problema decisionale fu portato alla ribalta dalla matematica dal matematico tedesco David Hilbert Hilbert ei suoi seguaci sostenevano che i matematici dovrebbero cercare di esprimere la matematica nella forma di un sistema formale completo, coerente, decidibile - un sistema che esprime "l'intero contenuto del pensiero della matematica in modo uniforme" (Hilbert 1927: 475).

Il progetto di formulare la matematica in questo modo divenne noto come "Hilbertprogram". Un sistema coerente è quello che non contiene contraddizioni; un sistema completo in cui ogni vera affermazione matematica è dimostrabile. Un sistema completo, coerente, decidibile bandirebbe l'ignoranza dalla matematica. Data qualsiasi affermazione matematica, si sarebbe in grado di dire se l'affermazione è vera o falsa decidendo se è dimostrabile nel sistema. Hilbert ha dichiarato importante il sistema che esprime "tutto il contenuto del pensiero della matematica" dove questo deve essere coerente.

Un sistema incoerente - un sistema che contiene contraddizioni - è inutile, dal momento che qualsiasi affermazione, vera o falsa, può essere derivata da una contraddizione mediante semplici passaggi logici.

Quindi in un sistema incoerente, sono dimostrabili assurdità come 0 = 1 e 6 ≠ 6. Un sistema indecidibile potrebbe, a volte, lasciarci nell'ignoranza. Solo se il sistema matematico fosse decidibile potremmo essere fieri di poter sempre dire se una determinata affermazione è dimostrabile o meno.

Sfortunatamente per il programma Hilbert è diventato chiaro che i sistemi matematici più interessanti sono, se coerenti, incompleti e indecidibili. Nel 1931 Gödel dimostrò che l'ideale di Hilbert è impossibile da soddisfare, anche nel caso della semplice aritmetica. Ha dimostrato che il sistema chiamato aritmetica Peano è, se coerente, incompleto. Questo è noto come il primo teorema di incompletezza di Gödel. In seguito, Gödel ha generalizzato questo risultato, sottolineando che "a causa del lavoro di Turing, può ora essere fornita una definizione precisa e indiscutibilmente adeguata del concetto generale di sistema formale", con la conseguenza che l'incompletezza può "essere dimostrata rigorosamente per ogni coerente sistema contenente un certo importo.

L'intelligenza Artificiale

L'Intelligenza Artificiale consiste nella costruzione di macchine "pensanti", ossia capaci di aiutare o assistere l'uomo nel risolvere compiti teorici o pratici. La sua nascita ufficiale risale al 1956. Tra i diversi campi di studio dell'IA, si è sviluppata la robotica, il cui scopo principale è quello di sostituire l'uomo in alcune attività produttive. I robot della prima generazione hanno capacità di memoria, mentre quelli della seconda vengono progettati per interagire con l'ambiente esterno.

Il campo di ricerca e gli studi che ruotano attorno alla tematica dell'IA hanno una storia molto recente. Possiamo indicare il 1956 come anno in cui nasce tale disciplina anche se troviamo ampie e chiare anticipazioni, se pur a livello concettuale, nelle tesi di Alan Turing. L’IA è caratterizzata dall'interesse per gli aspetti di: percezione dell’ambiente, per es. attraverso l’elaborazione di segnali provenienti da sensori di vario tipo per estrarre gli elementi utili alle decisioni o alla comprensione; interazione con l’ambiente, per es. attraverso interfacce uomo-macchina basate su meccanismi di comprensione del linguaggio naturale, dei manoscritti, di segnali vocali o di immagini; apprendimento, con conseguente modifica del comportamento nel tempo; rappresentazione della conoscenza, sia per una efficace interazione con l’ambiente, sia per facilitare l’analisi, sia per un’efficace soluzione dei problemi di decisione; risoluzione di problemi, anche di tipo non strutturato e tale da richiedere l’elaborazione di informazioni in forma simbolica; realizzazione di processi decisionali ovvero traduzione di decisioni aggregate in decisioni operative e, in particolari ambiti, attuazione delle decisioni.

Tuttavia, per penetrare in fondo a tale paradossalità e tentarne la risoluzione è bene analizzare le varie tappe che portarono alla realizzazione di una macchina che possiamo considerare intelligente: il calcolatore. Un calcolatore, anche chiamato macchina calcolatrice, è una macchina da calcolo in grado di eseguire calcoli matematici.[2] I calcolatori sono costruiti dall'uomo per semplificare e velocizzare l'esecuzione dei calcoli matematici. Attualmente i calcolatori più avanzati sono in grado di sostituire completamente l'uomo nell'esecuzione dei calcoli matematici e hanno capacità di calcolo nemmeno paragonabili a quelle dell'uomo. Un calcolatore automatizzato e in grado di eseguire complessi calcoli matematici, è anche chiamato "elaboratore" o "computer".

La Macchina di Turing

La Macchina di Turing è un dispositivo formato da :

1. Un ideale nastro, cioè una striscia continua di celle ciascuna delle quali può essere vuota o contenere i simboli di un alfabeto.
2. Una testina di lettura-scrittura.
3. Un dispositivo di controllo che in ogni istante si trova tra un numero finito di stati.

La macchina deve essere impostata in modo che, se lo scanner è posizionato su un qualsiasi quadrato del nastro e la macchina è in movimento, stamperà cifre binarie alternate sul nastro, 0 1 0 1 0 1. . ., lavorando a destra dal suo punto di partenza, lasciando un quadrato vuoto tra ogni cifra. Per fare il suo lavoro, la Macchina di Turing (MdT) usa quattro stati etichettati "a", "b", "c" e "d" con un’ alternanza di spazi e numeri, interruttori e spine. Lo spazio che vi è tra i numeri ricorda i vecchi telefoni a disco.

I maggiori contributi di Turing allo sviluppo del computer moderno furono:

1. L'idea di controllare la funzione della macchina informatica memorizzando un programma di istruzioni nella memoria della macchina.
2. La sua dimostrazione che, con questo mezzo, una singola macchina di struttura fissa è in grado di fare ogni calcolo che può essere eseguito da qualsiasi macchina di Turing.

La Computazione Umana

Quando Turing scrisse "On Computable Numbers", un computer non era affatto una macchina, ma un essere umano o meglio un assistente matematico che calcolava a memoria, in accordo con un "metodo efficace" fornito da un sorvegliante prima del calcolo. Si trattava di un grande calcolatore che aveva la funzione di aiutare gli esseri umani, come ci testimonia la presenza della macchina della verità adottata da molti eserciti. Il termine "macchina calcolatrice" era usato per riferirsi a macchine calcolatrici che meccanizzavano elementi del lavoro del computer umano. Questi erano in effetti omuncoli, calcolavano più rapidamente di un computer umano non assistito, ma non facevano nulla che in teoria non potesse essere fatto da un impiegato umano che lavorasse in modo efficace. Le prime macchine svolgevano solo calcoli semplici, erano infatti simili alle calcolatrici manuali : non erano automatiche e ogni fase veniva avviata manualmente dall'operatore umano. All’inizio degli anni 40 cresceva la necessità di costruire macchine in grado di svolgere calcoli sempre più complessi in modo da superare le capacità umane, tuttavia per svolgere un calcolo complesso erano necessarie diverse dozzine di computer e uno stesso numero di esseri umani che avevano il compito di avviarli. Questa macchina svolgeva gli stessi compiti dell’uomo, ma in maniera non intelligente.

La macchina di Turing è un'idealizzazione del computer umano e secondo lo studioso ci sono compiti matematici che non possono essere svolti senza un procedimento scientifico.

La tesi di Church e Turing

Secondo Turing si agisce in modo scientifico quando il metodo utilizzato è ripetibile. La Macchina di Turing segue il programma e le istruzioni che ha ricevuto da un essere umano, dunque le operazioni che segue sono sempre logiche se a programmarla non è stato un folle. Una cosa che si può replicare esiste, in caso contrario non esiste e non è neppure giusta matematicamente. Turing esponendo la sua tesi ci dice che tutto ciò che può fare un computer umano può essere fatto anche dalla sua macchina. Church utilizza un linguaggio più formale per sostenere la tesi di Turing aggiungendo che la presenza di un essere umano, mentre la macchina è in azione, permette di verificare una eventuale anomalia e risolverla immediatamente. Resta il fatto che entrambi gli studiosi affermano la medesima cosa in quanto sostengono la validità del metodo matematico.

La Macchina Universale di Turing

Turing chiama qualsiasi numero che possa essere scritto da una Macchina di Turing numero computabile, sia esso intero o decimale. Lo scienziato vuole capire se esistono algoritmi capaci di risolvere tutti i problemi. Una funzione infatti è computabile se esiste un algoritmo che la calcola. Si tratta quindi di procedimenti compiuti dalle cosiddette Macchine di Turing (UTM). Tuttavia Turing ha dimostrato che non tutti i numeri reali sono calcolabili. In realtà, i numeri computabili sono relativamente scarsi tra i numeri reali. Partendo dal presupposto che ci sono più numeri reali che interi, Turing dice che nella sua macchina esistono programmi per ogni numero computabile, reale o intero. Dunque ci sono molti numeri computabili perché ci sono molti numeri differenti.

Il problema di stampa e il problema dell’arresto

Turing ha descritto una serie di problemi matematici che non possono essere risolti dalla macchina di Turing.

Uno è il problema di stampa. Alcuni programmi stampano "0" ad un certo punto nelle loro composizioni, mentre i programmi rimanenti non stampano mai "0". Il problema di stampa è il problema di decidere in quale di queste due categorie cade un programma arbitrariamente selezionato.

Il problema dell'arresto è un altro esempio di un problema che non può essere risolto dall'UTM. La Macchina di Turing si può fermare improvvisamente, alcune volte ciò si vede immediatamente, altre no. Naturalmente osservare il funzionamento della macchina (o una simulazione della macchina) non è di alcun aiuto, perché cosa si può concludere se dopo una settimana o un anno la macchina non si è fermata? Se alla fine la macchina si ferma, un umano che guarda se ne accorgerà, ma nel caso di una macchina che non si è ancora fermata, non esiste un metodo efficace per prevedere se si fermerà o meno. In teoria il problema dell’arresto sarebbe risolvibile se ci fosse una costante presenza umana a controllare il funzionamento della macchina, pronta ad intervenire in caso di bisogno. Ciò è impossibile se si pensa ad una macchina che stia in azione per molto tempo, quindi il problema dell’arresto è considerato irrisolvibile. In altri termini non è possibile per una macchina di Turing capire se un'altra macchina di Turing si arresterà o no, dati uno stato e un nastro iniziale.

La funzione dell’arresto

Una funzione è una mappatura da "argomenti" (o input) a "valori" (o output).

Si dice che una funzione è calcolabile dalla macchina di Turing se una macchina di Turing assumerà argomenti della funzione (o coppie di argomenti ) e se dopo aver eseguito un numero finito di operazioni di base, produrrà il valore corrispondente indipendentemente dall'argomento della funzione. Ad esempio, l'addizione sugli interi è calcolabile dalla macchina di Turing, poiché questa può essere impostata in modo tale che ogni volta che due numeri interi sono inscritti sul suo nastro (in notazione binaria, ad esempio), la macchina emetterà la loro somma.

La funzione di arresto è la seguente: supponiamo che le macchine di Turing siano ordinate in modo da poterle numerare. Gli argomenti della funzione di arresto saranno semplicemente 1, 2, 3,. . . . (Come la funzione di squadratura, la funzione di interruzione prende singoli argomenti.) Il valore della funzione di interruzione per qualsiasi argomento sarà 1 se la Macchina di Turing si interromperà alla fine quando verrà avviato su un nastro vuoto, e sarà 0 se la medesima macchina funzionerà all'infinito.

L'Entscheidungsproblem

L'Entscheidungsproblem è un problema posto da David Hilbert nel 1928, all'interno del dibattito sui fondamenti della matematica. Tale problema può essere esposto come segue:

esiste un metodo, universalmente valido, che permetta di stabilire con sicurezza la verità o la falsità di un qualsiasi enunciato della logica formale?

Per fare questo cercò di trovare un sistema.

Un sistema coerente è quello che non contiene contraddizioni, al suo interno ogni vera affermazione matematica deve essere dimostrabile. "Decidibile" significa che esiste un metodo efficace per dire, di ogni stato matematico, se la dichiarazione è dimostrabile nel sistema. Un sistema completo, coerente, decidibile eliminerebbe l'ignoranza dalla matematica. Data qualsiasi affermazione matematica, si sarebbe in grado di dire se l'affermazione è vera o falsa decidendo se è dimostrabile nel sistema.

È importante che il sistema che esprime tutto il contenuto del pensiero della matematica sia coerente. Un sistema incoerente, ovvero un sistema che contiene contraddizioni, è inutile dal momento che qualsiasi affermazione, vera o falsa, può essere derivata da una contraddizione mediante semplici passaggi logici. Se l'ignoranza deve essere bandita in modo assoluto, il sistema deve essere decidibile. Un sistema indecidibile potrebbe, a volte, lasciarci nell'ignoranza poiché per stabilire se una cosa è vera o falsa dobbiamo partire necessariamente da un presupposto e se questo è sbagliato, e noi non lo sappiamo, anche il risultato lo sarà. Solo se il sistema matematico è decidibile potremmo dimostrare ogni affermazione data. Sfortunatamente per Hilbert è diventato chiaro che i sistemi matematici più interessanti sono, se coerenti, incompleti e indecidibili.

Nel 1931 Gödel dimostrò che l'ideale di Hilbert era impossibile da soddisfare. Gödel aveva dimostrato che non importa quanto i matematici possano tentare di costruire il sistema formale onnicomprensivo previsto da Hilbert, il prodotto delle loro fatiche sarebbe, se coerente, inevitabilmente incompleto.

Il teorema di Gödel non menziona la decidibilità. Questo aspetto è stato affrontato da Turing e da Church. Ognuno ha mostrato, lavorando indipendentemente, che nessun sistema formale coerente di aritmetica è decidibile. Il modo in cui Turing dimostra che il calcolo del predicato di primo ordine è indecidibile riguarda il problema di stampa. Se nessuna macchina di Turing è in grado di eseguire l'operazione in questione, non esiste un metodo efficace per eseguirla. Il sogno di Hilbert era ormai in rovina.

Se l'indecidibilità dovesse fallire, la matematica, nel senso attuale, cesserebbe di esistere; il suo posto sarebbe preso da una regola completamente meccanica, con l'aiuto della quale ogni uomo sarebbe in grado di decidere, di qualsiasi affermazione data, se la dichiarazione può essere dimostrata o meno.

Fonti

• Programmers’ handbook for Manchester electronic computer, University of Manchester Computing Laboratory. [A digital facsimile is available in The Turing Archive for the History of Computing, <http://www. AlanTuring. net/programmers_handbook>.] von Neumann, J. 1927. “Zur Hilbertschen Beweistheorie” [On Hilbert’s proof theory], Mathematische Zeitschrift 26 (1950), pp. 1–46.
• David Hilbert and his Mathematical Work, Bulletin of the AmericanMathematical Society, 50 (1944), pp. 612–654.
• L. Wittgenstein, Remarks on the Philosophy of Psychology, vol. 1, Blackwell, Oxford 1980.