Avanti Indietro Indice

5. Costruire la Macchina di Turing da Caffè

Vi struggete in memoria dei bei vecchi tempi, quando gli uomini erano uomini e si costruivano da soli la propria macchina da caffè?

Questo capitolo spiega il modo di assemblare una autentica, intelligente, macchina da caffè. Sarà un computer progettato con architettura di von Neumann, comprensivo di una CPU, ROM/RAM, I/O e sarà anche adatto ad impieghi più generici, una cosiddetta Macchina Universale di Turing.

5.1 Un linguaggio assembly adatto

Contrariamente ad altri complessi ma popolari sistemi quali CISC o RISC, la nostra macchina sarà semplicemente MISC: Mono-Instruction Set Computer!

Il nostro processore comprenderà soltanto un comando, ma ciononostante, con memoria e tempo sufficiente, sarà in grado di eseguire qualunque azione che possa essere compiuta dal vostro Pentium IV 3GHz, o simularla completamente. Può risolvere un qualunque problema computabile eseguendo del semplice codice come questo:


SBN     $mem1, $addr1
SBN     $mem2, $addr2
SBN     $mem3, $addr3
SBN     $mem4, $addr4
SBN     $mem5, $addr5
SBN     $mem6, $addr6
[...]

Il comando magico è chiamato SBN $mem, $addr (Subtract and Branch if Negative), che prende il valore dalla cella di memoria $mem, lo sottrae all'accumulatore (A è l'unico registro disponibile in questa architettura) e lo memorizza nuovamente nell'accumulatore e in memoria $mem: [mem] <= A <= A-[mem]. Se e solo se il risultato è negativo, salta all'indirizzo specificato da $addr. Se $addr punta al comando successivo, non vi è alcun salto condizionato. Ora, con questo comando a disposizione, è possibile sottrarre, sommare, azzerare gli indirizzi di memoria, spostare byte, moltiplicare, comparare e così via. Cosa migliore di tutte, ci si può costruire facilmente un compilatore ottimizzato.

Voila. Questo è un grande sistema per qualunque problema di Turing Completo, inoltre, è sicuramente più facile da programmare della Macchina di Turing originale!

5.2 Hardware ed interfacciamento

La gran cosa di questo innovativo processore MISC è che si ha bisogno di 0 bit per memorizzare l'opcode dei comandi. Questo rende la CPU molto, molto più semplice: si ha bisogno di leggere solo una coppia di operandi ogni volta. Si potrebbe voler estendere le possibilità del processore estendendo l'istruzione SBN a 3 o 4 operandi, così sarebbe in grado di caricare e memorizzare i dati dalla memoria principale. Questo è un esercizio lasciato al lettore; onore a google.

Il diagramma della CPU risulterà come segue:


<========= ADDRESS BUS ==============>
        =                =
        =  +---------+   =
        =  | CONTROL |   =
   +---------+  +-----------------+
   | ALU & A |  | Program Counter |
   +---------+  +-----------------+
        =  |  LOGIC  |   =
        =  +---------+   =
        =                =
<=========== DATA BUS ===============>

Ora, tutto quello che si deve fare è mettere insieme alcuni chip di memoria, ad esempio riciclando una RAM di cache statica da vecchi PC 386, una ALU e pochi componenti glue. Si può scegliere tra TTL o CMOS per le porte logiche e i latch; io sono un sostenitore di CMOS, ma questo dipende in realtà dalle proprie preferenze. Si può costruire un sistema ad 8, 16, 32, 64 bit o della dimensione di cui si ha bisogno. Nel caso servisse, per word più lunghe ho trovato preferibile costruire l'ALU con EPROM 27128 pre-programmate piuttosto dei chip 74x181s, più difficili da trovare. Ci si procuri anche un'unità di propagazione del carry.

La natura monolitica di questo sistema consente solo I/O mappato in memoria e richiede di provvedere ad un progetto particolare per l'interfacciamento bidirezionale, ma niente di più particolare di quanto già visto in sistemi di più vecchia generazione. AGC, il computer che ha guidato la missione Apollo 11 sulla Luna, è stato realizzato utilizzando questa tecnica, quindi dovrebbe essere sufficiente anche per i nostri scopi.

Si osservi che il bus dei dati deve essere ampio esattamente come il bus degli indirizzi; questo implica che la nozione di un byte è applicabile solo alle macchine da caffè ad 8 bit, il che risula essere più una funzionalità che un baco. Si resterà sorpresi da quale caffè si potrà ottenere con un bus a 8 o 16 bit! È davvero un hardware di impiego generale.

5.3 Software

Un sistema così puro si accoppierà bene con il linguaggio di programmazione FORTH, famoso per il controllo di sistemi embedded. Il più importante prerequisito per fare questo è di avere un meccanismo di stack, che in questo caso può essere realizzato con un contatore combinato con un pool di memoria.

Se si aspira ad una seria piattaforma di sviluppo per il caffè, la portabilità del C è una scelta obbligatoria. La propria scelta potrebbe essere quella di modificare gcc, lcc o sdcc, che con i giusti aggiustamenti ai back-end saranno in grado di produrre lo speciale codice assembly MISC. Un giorno si potrebbe anche voler riscrivere un altro linguaggio come il C; ci si scordi la lettera D, è già stata presa, quindi non si facciano gli stessi errori con il compilatore: http://www.gnu.org/software/gcc/projects/beginner.html

Qualora si stia pensando di scriversi il proprio compilatore, ci si documenti prima su flex, yacc e solo un altro po' di teoria. In particolare, si apprezzerà subito la tassonomia di Noam Chomsky sui linguaggi:

e così via. Si legga anche Computability Theory.

5.4 Una criticità minore della Macchina di Turing

A causa di come una Macchina di Turing opera (si guardi a proposito http://plato.stanford.edu/entries/turing-machine/), è un dispositivo molto complicato da programmare e su cui fare il debug una volta fatto tutto. La ragione è che il suo comportamento è un processo sequenziale completamente determinato dai seguenti parametri:

Contemporaneamente, il maggiore svantaggio della Macchina di Turing (MT) è che la sua natura sequenziale comporta che può essere efficacemente mappata su di essa solo una particolare classe di problemi. Le MT sono adatte per problemi che sono descritti su un supporto di immagazzinamento seriale (nastri) e che non fanno utilizzo di indici per referenziare i dati. Questo è in contrasto con la Macchina da Caffè (MC), che può gestire anche algoritmi ad Accesso Casuale (senza perdita di semplicità).

In aggiunta a questo, le MT costringono ad una notevole e non necessaria complessità sul punto (3) con l'idea di mantenere semplici i punti (1) e (2). E qualora non si ritenga che la così chiamata Tabella delle Istruzioni non sia di una complessità schiacciante, mai provato a scrivere un compilatore per una Macchina di Turing? Un sistema che non sia facilmente programmabile e sia di difficile debug, dovrebbe essere considerato un sistema seriamente discutibile, almeno per quanto riguarda l'Ingegneria dei Computer. Per esempio, si provi a simulare la Macchina da Caffè con una Macchina di Turing e viceversa. Beh, se ancora si è in disaccordo, mostratemi il codice!

Ultima annotazione: la Macchina da Caffè (MC) è un modello per l'architettura di von Neumann molto migliore ed ha una relazione O(1) con quella che è la pratica diffusa degli algoritmi pesati nell'attuale teoria della complessità.


Avanti Indietro Indice