H1B1 Lego TM

titolo vuoto

H1B1 --- An Electro-Mechanical Turing Machine with Finite Tape

H1B1 on Youtube shows the version 0.0 of H1B1 which stands for One-Hertz-One-Byte. H1B1 is the name of a possible electro-mechanical transposition of a Turing Machine with finite tape that runs at a speed of less than 1 Hertz with a memory equal to 1 byte.

H1B1 was born for fun, but it can have a pedagogical purpose. Observing a sequence of "boot, fetch-execute, fetch-execute, ..., stop" operating on a physical tape, a curious person could better grasp some aspects of how a Turing machine works.

The structure of H1B1 consists mainly of a trolley carrying a Lego Mindstorm (Trademark) back and forth on tracks. The trolley is the head of the machine which, step by step, aligns a worm gear to vertical gears which form the memory, i.e. the tape of the machine. The goal is to transform a starting configuration initially on the tape into a final configuration.

Each vertical gear is a bit of information that we can read and write. Each bit can rotate to expose colored bricks (red, blue, yellow, black) just below a color sensor. The sensor can recognize the color of the brick that the gear below it exposes upwards. The red is the symbol 0 while the blue encodes 1. The yellow and black colors represent values different from 0 and 1. The more symbols we can represent, the most the programs of the Turing machine and the data on which it operates will be compact. The rotation of a bit represents the writing of a new symbol. The writing is complete as soon as the required color appears below the color sensor.

A design choice consists in reserving the two leftmost bits of the tape to represent the state of H1B1. All other bits are used to contain the input, when H1B1 starts, and the output when H1B1 ends in the accepting state with the head positioned on the third bit, that is, on the least significant bit of the tape.

Versione italiana

H1B1 on Youtube è la versione 0.0 di H1B1 che sta per One-Hertz-One-Byte. H1B1 è il nome di una possibile trasposizione elettro-meccanica di una macchina di Turing con nastro finito che funziona a una velocità inferiore a 1 Hertz con una memoria pari ad 1 Byte.

H1B1 è nata per divertimento, ma può avere uno scopo pedagogico. Osservando una sequenza di "boot, fetch-execute, fetch-execute, ..., stop" che operi su un nastro fisico, una persona curiosa potrebbe meglio cogliere alcuni aspetti su come una macchina di Turing funzioni.

La struttura di H1B1 consiste di un carrello che trasporta un Lego Mindstorm (Trademark) avanti e indietro su dei binari. Il carrello è la testina della macchina che, passo dopo passo, allinea una vite senza fine ad ingranaggi verticali che formano il nastro di memoria. L'obiettivo è trasformare una configurazione iniziale in cui si trovi il nastro ad una finale.

Ogni ingranaggio è un bit di informazione che possiamo leggere e scrivere. Ogni bit può ruotare per esporre mattoncini colorati (rosso, blu, giallo, nero) appena al di sotto di un sensore colore. Il sensore può riconoscere il colore del mattoncino che l'ingranaggio sotto di esso espone verso l'alto. Il rosso rappresenta il simbolo 0 mentre il blu codifica il simbolo 1. I colori giallo e nero rappresentano valori diversi da 0 e 1. Più simboli noi possiamo rappresentare, più i programmi della macchina di Turing ed i dati su cui essa opera saranno compatti. La rotazione di un bit rappresenta la scrittura di un nuovo simbolo. La scrittura è completa non appena il colore richiesto si presenti sotto il sensore di colore.

Una scelta progettuale consiste nel riservare i due bit più a sinistra del nastro per rappresentare lo stato di H1B1. Tutti gli altri bit servono per contenere l'input, quando H1B1 comincia l'elaborazione, e l'output quando H1B1 termina nello stato accettante con la testina posizionata sul terzo bit, cioè sul bit meno significativo del nastro.

Ulteriore lavoro consisterà nel fornire (i) un video più pedagogico, (ii) le istruzioni di montaggio, (iii) i sorgenti BrixCC che controllano il comportamento della testina in modo che diventi l'interprete di una qualsiasi funzione di transizione di una macchina di Turing ragionevolmente compatta, (iv) le istanze di semplici, anche se non necessariamente banali, macchine di Turing, (v) la scrittura di una breve confronto tra H1B1 ed altre trasposizioni elettro-meccaniche di macchine di Turing, realizzate con il Lego Mindstorm (Trademark) disponibili online.