Nel 1854, il matematico britannico George Boole (1815 - 1864), elaborò una matematica algebrica che da lui prese il nome. Nell'algebra booleana le procedure di calcolo si possono effettuare grazie a operatori matematici (AND, OR, NOT, ecc.) corrispondenti alle leggi della logica.
L'algebra di Boole entrò prepotentemente alla ribalta nel 1936, quando il matematico britannico Alan Mathison Turing (1912-1954), immaginò una "macchina" o "automa" - esistente unicamente a livello teorico - con la quale dimostrò formalmente la possibilità di eseguire qualsiasi algoritmo: una procedura di calcolo o, più in generale, la sequenza delle operazioni necessarie per risolvere un problema in un numero finito di operazioni. In tal modo, Turing aprì la strada al campo di quelle ricerche informatiche che prendono il nome di intelligenza artificiale (v. test di Turing), e l'algebra di Boole si rivelò di fondamentale importanza nella progettazione degli odierni computer.
|
Per far questo, supponiamo di eseguire una somma di due numeri (naturali), per fissare le idee, 2 + 4
Per ottenere il risultato della somma proposta, dobbiamo quindi seguire questi passaggi:
Questo è dunque l'algoritmo della somma di due numeri.
La sequenza di operazioni esaminata, si presta anche per eseguire moltiplicazioni. Per esempio, 2 x 6 equivale ad addizionare 6 volte il numero 2 (o 2 volte il mumero 6)
Come si vede, si è aggiunto un secondo controllo. Con analogo procedimento, è possibile anche l'elevazione a potenza. Per esempio, 23 = 2 x 2 ripetuta 3 volte. In questo caso, si dovrà aggiungere un terzo controllo.
Si potrebbe vedere (ma la questione è irrilevante per questa discussione) che il procedimento utilizzato per addizioni, moltiplicazioni ed elevazione a potenza, vale anche per le operazioni inverse: sottrazione, divisione (una successione di sottrazioni: 17/5 = 17 - 5 - 5 - 5 = 3 con il riporto di 2), estrazione di radice.
Ricordando che la prima calcolatrice, la pascalina, fu inventata nel 1642 da Blaise Pascal, per comprendere l'importanza della macchina o automa di Turing, dobbiamo fare una distizione tra le calcolatrici ed i moderni calcolatori. La linea di separazione può essere individuata nel fatto che le calcolatrici riescono ad eseguire un certo numero di operazioni ma non possono essere programmate: manca la possibilità di specificare alla macchina processi di calcolo articolati e complessi, definiti in base ad opportune sequenze di comandi che possano essere eseguiti in modo completamente automatico.
L'idea fondamentale alla base del calcolatore programmabile (elaboratore o computer), è che qualsiasi tipo di computazione consiste nella manipolazione di simboli (ne bastano solo 2 come nei calcolatori digitali) seguendo un'insieme di regole (algoritmo). Con questo modello nasce l'idea di "calcolatore universale".
Il metodo di programmazione di Turing, essenzialmente descriveva una macchina che utilizzava alcuni semplici istruzioni. Fare sviluppare ad un computer un compito particolare, era soltanto una questione di dividere il problema in una serie di problemi più semplici (un'operazione identica al processo affrontato dagli odierni programmatori) risolvibili appunto con semplici operazioni.
Una macchina o automa di Turing è definita da un insieme di regole che definiscono il comportamento della macchina su un nastro di Input-Output (lettura e scrittura). Il nastro può essere immaginato come una sottile striscia di carta divisa in quadratini dette celle e di lunghezza adeguata per eseguire qualsiasi algoritmo. Ogni cella contiene un simbolo oppure è vuota. L'automa utilizza una testina che si sposta lungo il nastro leggendo, scrivendo oppure cancellando simboli nelle celle del nastro. La macchina analizza il nastro, una cella alla volta, iniziando dalla cella che contiene il simbolo più a sinistra nel nastro.
Da quanto esposto, una macchina di Turing puo' essere immaginata come una sorta di registratore a nastro con una testina di lettura, scrittura e cancellazione. La testina possiede un indicatore che determina, per ogni passaggio di calcolo, lo stato specifico in cui la macchina si trova mentre sta leggendo il simbolo che corrisponde alla particolare cella del nastro sul quale è posizionata.
Definita la macchina, devono essere specificate le regole – l’equivalente del moderno software – che indichino che cosa fare in corrispondenza della combinazione di stati e di simboli letti sul nastro.
In generale, un automa di Turing deve poter effettuare le seguenti operazioni:
Per esempio, la seguente istruzione contenuta in tabella, impone che se l’indicatore di stato è in posizione 1 e la testina sta leggendo il simbolo A, l’istruzione consiste nel cancellare il simbolo, far avanzare la testina e cambiare lo stato della macchina a 2.
| stato iniziale | legge | scrive | azione | stato finale |
| 1 | A | cancella | > | 2 |
Per dare ragione dell'universalità della macchina di Turing, occorrerebbe mostrare come effettuare le 4 operazioni fondamentali (addizione, sottrazione, moltiplicazione e divisione) in quanto tutte le altre sono riducibili a queste. Tuttavia, ci limiteremo ad esaminare solo l'operazione di somma perché la programmazione di una macchina di Turing è laboriosa in quanto richiede un linguaggio di basso livello, "comprensibile" dalla macchina (oggi gli elaboratori possono utilizzare linguaggi di alto livello che sono più vicini alla logica umana).
La tabella seguente contiene le istruzioni per addizionare un certo numero di "A" (per esempio, 4) ad una sequenza di "A" (per esempio, 2). E' da notare che le istruzioni non vengono necessariamente eseguite sequenzialmente, ovverosia una dopo l'altra, bensì in base allo stato dell'automa.
| stato iniziale | legge | scrive | azione | stato finale |
| 4 | A | A | > | 4 |
| 4 | - | A | > | 3 |
| 3 | - | A | > | 2 |
| 2 | - | A | > | 1 |
| 1 | - | A | STOP | 0 |
Per esempio, nel caso della somma proposta (addizionare 4 volte "A"), la prima istruzione prevede che se l'automa si trova nello stato iniziale 4 e legge la lettera "A", deve riscrivere la lettera, poi l'automa si sposta di una casella verso destra e mantiene il suo stato interno (4) finquando trova una A da leggere.
Il programma visto puo' essere realizzato con una sequenza di istruzioni dinamiche: le istruzioni non sono predefinite, ma vengono via via specificate. In questo modo, un programma di addizione è valido per qualsiasi combinazione di addendi (nel caso si vogliano addizionare quattro "A", si imporrà n = 4). E' da notare che l'istruzione n = n - 1 non è un'equazione algebrica, ma implica che lo stato n deve diventare n - 1: se n = 4, diventa n = 4 - 1 = 3.
| stato iniziale | legge | scrive | azione | stato finale |
| n | A | A | > | n |
| n | - | A | > | n = n - 1 |
| 1 | - | A | STOP | 0 |
Con la macchina di Turing (che, per quanto possa sembrare strano, riassume la struttura funzionale di un computer) è possibile risolvere anche problemi non numerici; infatti basta associare ai simboli un significato alfabetico o alfanumerico. (v. algebra booleana)
Turing non costruì materialmente la sua "macchina universale". Infatti, per quanto tecnicamente realizzabile, il meccanismo (elettromeccanico) sarebbe stato lento e poco affidabile per impieghi pratici. D'altra parte, data la sua semplicità, una macchina di Turing puo' essere simulata con carta e penna: se un operarore umano puo' eseguire le istruzioni senza incertezze e ambiguità, allora la procedura è automatizzabile.
|
