Site map :

Last upgrade to the site:
august 10th, 2002.

There has been 

access to my Lego pages since creation.

This is an unofficial LEGO® web site.
LEGO® is a trademark of the LEGO® Group of companies which does not sponsor, authorize or endorse this site.
You can visit the official LEGO website at: http://www.lego.com

Copyright 1996, 2000, Denis Cousineau

A Turing machine is the simplest form of a computer. The concept was invented by Alan Turing in 1936.  This was the first computer invented (on paper only).

I- Principles of a Turing machine.

In its simplest form, a Turing machine is composed of a "tape", a ribbon of paper of indefinite length. There is a "head" that can read the symbol, chose to write a new symbol in place, and then move left or right. The Turing machine is said to be in a certain "state". Finally, the program is a list of "transitions", that is a list that says, given a current state and a symbol currently under the head, what should be written on the tape, what state the machine should go, and whether the head should move left or right.

The tape is used to store data. In addition, it can also store a series of transitions (a small programs) and thus, the head can run "sub-programs". We then say a Turing machine is emulating another one (the one on the tape).

By analogy with modern computers, the tape is the memory and the head is the microprocessor. 

Although it is composed of pretty simple capabilities, Turing argued that this simple machine could performed any computation, that is, could realize anything that results from operations. In 1950, he discussed that the mind is itself the results of operations (at the neural level) and thus is the creator of the artificial intelligence studies.

I chose to implement in Lego a slightly different version of the original Turing machine. Instead of having a bi directional tape, it uses a stack. When the symbol beneath the stack is read (and removed), the machine changes "states" and can add zero, one or two symbols on top of the stack.

This variation is maybe very different yet it is possible to show that this simple machine has the same capabilities than a Turing machine. Among other things, it can emulate a Turing machine placed on the stack. 

I programmed a small interface (through an Access database so Microsoft Access must be installed on your computer) to enter an test simple Automaton With Append (AWA or AAA in French). Follow this link to download the demo: AAA.zip.

One reason to build the automaton with append instead of the original Turing machine was that I avoided building a bi directional (near) infinite tape.

III- Building the automaton with LEGO

It turned out to be a very difficult project since, among other things, the construction needs to be "binary", that is, to be able to deliver one and only one symbol on the top of the stack, to pull one and only one symbol from beneath the stack, and that, for an indefinite period of time. In itself, adding a symbol is not that complicated, but doing this with "binary" precision is another matter entirely.

a) the symbols

The symbols themselves are made of cylinders. Using plates, I can code in binary so that the cylinder below is (1,0,1) or the number 5. This kind of bar code is easy to read using the light detector.

b) the memory

The stack is a small hollow tower in which the symbols can fall horizontally. It is therefore a "compact" memory, containing near 10 bytes per 6 inches! Another difficulty is to make sure the symbols will always remain horizontal, which implies equal friction everywhere. Below is shown one section but many can be connected together. I used two sections (since I pretty much ran out of beams at that point).

c) the reader

The reader is at the bottom of the memory. It is a mechanism meant to expulse one symbol at a time. The expulsed symbol pass in front of the light detector (not shown) so that the bar code can be read .

It is composed of the lower part of the memory stack and of a lever (shown on the side) that pushes the symbol out, activated in and out by the red axle.

d) the stacker

The stacker is at the top. Its purpose is to place new symbols on the stack. It is maybe the most difficult part of the automaton. Only one bank is shown in the picture, but 5 were actually implemented (see pictures below).

It works using the two blue blades. Every time the blades turn 90 degrees, one symbol falls down the memory onto the stack.

In order to turn exactly 90 degrees, I used the rotation sensor described in the section "Rotation sensor", connected onto the red axle for each bank.

Since in the full implementation, there are 5 banks, the correct bank cannot be controlled directly from the RCX which has only three outputs. Therefore, a selector is required that can select, using one motors, which of (up to 5) output must be activated. I used the third design from the page on my 2-to-7 multiplexors.

e- putting it all together

All the designs shown above are available in LDRAW files:
    a- the symbol: symbol.dat
    b- the memory: memory.dat
    c- the reader: reader_b.dat, reader_a.dat
    d- the stacker: provider.dat and the rotation sensor: rotation3.dat
    e-the selecter: multi_v3.dat

IV- Programming

Well, this Turing machine is not entirely mechanical... I used the RCX to store the transition table. Since the symbols are bar codes read with a light detector, it would have been very difficult to continue with a physical mechanism.

Three subroutines are required, one to select which symbol to provide on top of the memory, one to turn the provider one quarter of a turn, and  one to pull out one symbol from the bottom of the memory (reading it on the way).

These routines were programmed using PRO-BOT.

The subroutine Stacker turns the provider one quarter of a turn. It uses a sensor that turns off then on:

Declare Stacker CONSTANT 2
Declare stack MOTOR 1
Declare stacking SENSOR 0
Declare stacker_duration CONSTANT 10
SetSensorType(stacking, SWITCH_TYPE)
BeginOfSub(Stacker)
   On(stack)
   While(stacking = Open)
   EndWhile()
   Wait(stacker_duration)
   While(stacking = Close)
   EndWhile()
   Wait(stacker_duration)
   Off(stack)
EndOfSub()

The second subroutine select which symbol to provide. It uses two global variables, one which indicates the current location and another one which indicate which is the desired symbol. It compares the actual position with the desired position and move the motor Selecter accordingly:

BeginOfSub(Selecter)
   {if there is a move to do}
   If(objective <> actual_pos)

      {decide which way, backward or forward}
      If(objective < actual_pos)
         SetRwd(select)
      Else
         SetFwd(select)
      EndIF()

      {perform the moves for the right duration}
      While(actual_pos <> objective)
         SetVar(select_duration, next_step) 
         {if this is the last or first symbol}
         If(actual_pos = nrnotch)
            SetVar(select_duration, first_step)
         EndIF()
         If(actual_pos = CONSTANT,1)
            SetVar(select_duration, first_step)
         EndIF()

         {move one notch}
         On(select)
         Wait(select_duration) 
         Off(select)

         {update actual position }
         If(objective < actual_pos)
            SubVar(actual_pos, CONSTANT,1)
         Else
            SumVar(actual_pos, CONSTANT,1)
         EndIF()

      EndWhile()
   EndIF()
   PlayTone(400,20)
EndOfSub()

The last subroutine Reader removes one symbol from the bottom of the memory stack, reading it along the way, returning in the variable Symbol the number of black bars on it:

Declare Reader CONSTANT 4 
Declare read MOTOR 2 
Declare reading SENSOR 2 
Declare reader_duration CONSTANT 19 
Declare gray_luminance CONSTANT 700
Declare couleur VARIABLE 30 
Declare Symbol VARIABLE 29 
Declare read_timer TIMER 0
BeginOfSub(Reader)
   {0-initialise}
   SetVar(Symbol, constant,1)
   SetVar(couleur, black)

   {a- pull out}
   ClearTimer(read_timer)
   On(read)
   While(read_timer < reader_duration)
   EndWhile()
   AlterDir(read)

   {b- push in, reading the symbol}
   ClearTimer(read_timer)
   While(read_timer < reader_duration)
      If(couleur = white)
         If(reading > gray_luminance)
            SetVar(couleur, black)
            SumVar(Symbol, constant,1)
         EndIF()
      EndIF()
      If(couleur = black)
         If(reading < gray_luminance)
            SetVar(couleur, white)
         EndIF()
      EndIF()
   EndWhile()
   AlterDir(read)
   Off(read)

   {c- remove two for the black of the reader}
   SubVar(Symbol, constant,2)

EndOfSub()

A complete listing of the source code is provided in this text file: AAA.rcp.   

These three routines are the building blocks used in a main program that run the automaton. The main program can be generated automatically by the demo program indicated earlier, AAA.mdb.

V- A full example: the AxnBxn problem.

Suppose a very simple problem that we want to be solved by an automaton. We want a system that can decide whether the number of A's placed at the beginning of the input (on the memory stack) is the same as the number of B's following the A's. The symbol # indicates the end of the input.

A simple way to program the automaton is to (i) read the first A, (ii) all the A's that follow are place back on the top of the stack, (iii) to read the first B, (iv) all the remaining B's are placed back on the top of the stack, and (v) once the end-of-input is reach, put it back on top of the stack, and start the program again on the resulting input. Basically, it creates a new input that has one A and one B less than the original input.

A simple way to represent an automaton is with the following diagram:

Where the > sign next to q₀ indicates the starting state, and the double line around q_exit indicates the accepting state, that is, the input was adequate. The branches depend on the symbol found on the memory (at the bottom of the stack). On occasion, there is an indication "stack an A" which means that the automaton is adding a symbol on top of the memory.

Although this visual diagram is convenient to visualize the operations of the AxnBxn automaton, they are generally represented using the transition table, as follow:

 (q0, #) -> (nothing), (nothing), qExit 
 (q0, a) -> (nothing), (nothing), q1 
 (q1, a) -> a, (nothing), q1 
 (q1, b) -> (nothing), (nothing), q2 
 (q2, #) -> #, (nothing), q0 
 (q2, b) -> b, (nothing), q2 

where (nothing) means that nothing is added to the stack. You can check that both representation have the same meaning. 

The RCX program that will run this automaton is generated by the AAA.mdb demo program, and the result is:

{ Mapping of the internal states to a numeric value: }
Declare q0 CONSTANT 0 
Declare q1 CONSTANT 1 
Declare q2 CONSTANT 2 
Declare qEx CONSTANT 3 

{ Mapping of the internal symbols to a number of bars (and the banks): }
Declare # CONSTANT 0 
Declare a CONSTANT 1 
Declare b CONSTANT 2 

SetVar(State = q0) {starting state}
While(State <> qEx) {finishing state} 
  GoSub(Reader) { reads one symbol, unstacking it on the way}

  If( State = q0)
    If( Symbol = #)
      SetVar( State, qEx) {new state}
    EndIf()
  EndIf()

  If( State = q0)
    If( Symbol = a)
      SetVar( State, q1) {new state}
    EndIf()
  EndIf()

  If( State = q1)
    If( Symbol = a)
      SetVar( Objective = a) { stacks one symbol}
      GoSub( Selecter )
      GoSub( Stacker )
      SetVar( State, q1) {new state}
    EndIf()
  EndIf()

  If( State = q1)
    If( Symbol = b)
      SetVar( State, q2) {new state}
    EndIf()
  EndIf()

  If( State = q2)
    If( Symbol = #)
      SetVar( Objective = #) { stacks one symbol}
      GoSub( Selecter )
      GoSub( Stacker )
      SetVar( State, q0) {new state}
    EndIf()
  EndIf()

  If( State = q2)
    If( Symbol = b)
      SetVar( Objective = b) { stacks one symbol}
      GoSub( Selecter )
      GoSub( Stacker )
      SetVar( State, q2) {new state}
    EndIf()
  EndIf()

EndWhile() { end of the main loop}

This program is saved by AAA.mdb under the name of AAA_2.rcp, which is automatically inserted in the global program AAA.rcp.

IV- My implementation

Here is the final result:

Not exactly small, and the colors don't really match (I barely have enough LEGO to make it all ;-) ).

The main question is related to artificial intelligence. The Turing machine can perform any computation. Well, does the brain performs computations? If so, it is possible to imagine one day a computer that will have the same cognitive capabilities than a human. We could converse with it, it could discover new insight about physics, about the human nature... For more, check the Loebner Prize.