Computer Laboratory

Raspberry Pi

Section 3: Building the Turing Machine

Introduction

Turing tape LEDs

In this project, we shall build a 3-symbol Turing machine using 11 bicoloured LEDs to represent the cells on the tape. Green represents a 1, red represents a 0 and a blank is represented when the LED is off. We shall call these the tape LEDs. The middle LED is labelled with a tape to identify it as the head of the machine.

Turing machine switches

We will also have 6 pushbutton switches, 3 of them are operation switches (Write/Erase, Move Tape Left, and Move Tape Right) for operating the Turing machine, and the other 3 are program switches (Run/Pause, Continue, and Reset) for running the Turing machine programs. The additional bicoloured LED is for displaying whether the program is running or not. We'll call this the Program LED.

The final product should look like this:

the final product

To make your Turing machine, you will need:
– 1 × Working Raspberry Pi with an Internet connection
– 1 × Breadboard + jumpers
– 12 × Male/female jumper cables or 1 × Adafruit cobbler breakout kit, but the latter requires soldering
– 12 × Bicoloured LEDs
– 6 × Pushbutton switches
– 12 × 270Ω resistors
– 6 × 10kΩ resistors
– 3 × PCF8574AN I/O Expanders

Turing machine components

The circuit diagram is below. If it seems rather complicated, don't panic: this tutorial will guide you through building it a bit at a time.

Turing machine circuit diagram

Step 1: Set up the supply rails

Components:
– 1 × Breadboard and jumpers.
– 1 × M/F jumper cables.

Link the rails together as before using the jumpers and connect the M/F jumper cables to the rails (red to 3.3V, black to GND). You may choose to use jumpers of other lengths instead of the ones in the picture and wire them differently, depending on the jumpers and breadboard that you have.

breadboard supply rail connection

Step 2: Add the 11 LEDs to represent the tape

Components:
– 11 × Bicoloured LEDs.
– 11 × 270Ω resistors.
– Jumpers.

Turing tape LEDs breadboard
Tape LEDs circuit board

Connect the bicoloured LEDs and resistors as shown below. The pins corresponding to the green LEDs are positioned on top, while the pins corresponding to the red LEDS are positioned below. Each resistor should be placed between the central pin and the 3.3V rail.

The exact location to place the LEDs isn't that important, it is OK to be off by one or two squares.

LED breadboard placement

Step 3: Add the switches and the program LED

Components:
– 1 × Bicoloured LED.
– 6 × Pushbutton switches.
– 1 × 270Ω resistors.
– 6 × 10kΩ resistors.
– Jumpers.

switch location on breadboard
switch circuit diagram

Add the switches and LED in the following manner. Connect a 10kΩ resistor between the left pin of each switch and the 3.3V rail, and a jumper between the right pin of each switch and the GND rail. Then, connect a 270Ω resistor between the central pin of the LED and the 3.3V rail.

connecting the switches to the breadboard

Step 4: Add the I/O expanders

Components:
– 3 × PCF8574AN I/O expanders.
– Jumpers.

i/o expander breadboard addition
i/o expander circuit diagram
  1. Add the 3 I/O expanders and connect their Vdd and Vss pins to the 3.3V and GND rails respectively. Refer to Section 2: Expanding the Raspberry Pi pin header for the pin information of the I/O expander.
    i/o expanders connected
  2. Connect the address pins of the I/O expanders accordingly; they should be set to 000, 001, and 010. Do note that the pins A2, A1, A0 are from bottom to top.
    addresses of the i/o expanders

Step 5: Connect the SDA and SCL lines

Components:
– 2 × M/F jumper cables.
– Jumpers.

SDA and SCL breadboard connection
SDA and SCL connetion circuit diagram
  1. Connect the SDA and SCL pins of each I/O expander together to form the SDA and SCL rails.
    SDA and SCL pin connections
  2. Connect the 3.3V, GND, SDA and SCL rails on the breadboard to the pins on the Raspberry Pi. Refer to Section 2: Expanding the Pi header for the pin information of the Raspberry Pi.
    Connect the Pi's pins and rails

Step 6: Connect the tape LEDs to the I/O expander pins

Components
– Jumpers.

connecting the tape LEDs to the pins
tape LED connnections diagram

The LEDs will be connected to the I/O expanders in the following way:

I/O Expander Pin 0 Pin 1 Pin 2 Pin 3 Pin 4 Pin 5 Pin 6 Pin 7
000 LED 0 (green) LED 1 (green) LED 2 (green) LED 3 (green) LED 3 (red) LED 2 (red) LED 1 (red) LED 0 (red)
001 LED 4 (green) LED 5 (green) LED 6 (green) LED 7 (green) LED 7 (red) LED 6 (red) LED 5 (red) LED 4 (red)
010 LED 8 (green) LED 9 (green) LED 10 (green) NULL NULL LED 10 (red) LED 9 (red) LED 8 (red)
  1. Connect the pins of each green LED to the respective pins on the I/O expander according to the circuit diagram.
    green LED pin connections
  2. Similarly, connect the red pins of each red LED to the respective pins on the I/O expander according to the circuit diagram.
    red LED pin connections

Step 7: Connect the switches and program LED to the Raspberry Pi pin header

Components:
– 8 × M/F jumper cables.
– Jumpers.

switch and LED layout
switch + LED circuit diagram

We will connect the switches and the program LED to the following GPIO pins of the Raspberry Pi:

Program switches Program LED Operation switches
Run/Pause Continue Reset Green Red Write/Erase Move tape left Move tape right
GPIO 7 GPIO 11 GPIO 13 GPIO 8 GPIO 10 GPIO 12 GPIO 16 GPIO 18
  1. Connect the pins of the Raspberry Pi to the breadboard using the male/female jumper cables, in the same layout as the pin header:
    Pi GPIO pin connections
  2. Use jumpers to connect the program switches to the appropriate M/F jumper cables, disconnecting the unnecessary M/F jumper cables from the breadboard temporarily.
    connect switches with jumper cables
  3. Connect the program LED pins to the respective M/F jumper cables after reconnecting them to the breadboard.
    connect LEDs to jumper cables
  4. Similarly, connect the operation switches to the respective M/F jumper cables.
    operation switches to jumpers
  5. Print and stick labels for each of the switches and the program LED and the Turing machine is complete! There are, however, additional steps which we can take to make the circuit neater: these will be discussed next.
    labels for switches and LEDs

Step 8: Make the circuit neater (optional)

Components
– 1 × Adafruit Pi cobbler breakout kit.
– Jumpers.

make the breadboard and circuit neater
  1. Trim the ends of the resistors. This is good practice so as to prevent shorting of wires. Nonetheless, you may not choose to do so if you wish to reuse the resistors for future projects.
    trimmed resistors
  2. Use an Adafruit Pi cobbler breakout kit instead of the M/F jumper cables. Some soldering is required to put it together and the instructions can be found here. Some rewiring has to be done along with the shifting of the program switches but the pins remain the same. Just ensure that the components are connected to the right pins on the Pi cobbler's header.
    Pi cobbler connections

Step 9: Test and troubleshoot the circuit

Components:
– 1 × Multimeter.

  1. With the breadboard connected to the Raspberry Pi, use the multimeter to measure the voltage between the rails by connecting the test leads as shown below. It should give a value of 3.3V.
    rail voltage checks
  2. Leaving the black test lead of the multimeter as it is, use the red test lead to check the voltage of the other sections of the rails. The 3.3V rail should give a value of 3.3V while the GND rail should give a value of 0V.
    voltage check of other rails
  3. Measure the voltage of the switch pin that is connected to the Raspberry Pi pin header as shown below. It should give a value of 3.3V when the switch is pressed and 0V when it is not. Do this for all the switches.
    pin and switch voltage checks
  4. Connect one end of a jumper to the GND rail on the breadboard and the other end to the pin of either red or green LED pin of each bicoloured LED. Doing so should light up the LED. Do this to check if all of the LEDs are connected.
    LED connection checks
  5. Measure the voltage of each address pin of every I/O expander to check if they are set to the right voltage, 3.3V if set high, 0V if set low. Measure the voltage of the Vdd and Vss pins of every I/O expander as well: they should be set to the right voltage.
    check voltage of I/O expanders
  6. Now, disconnect the breadboard from the Raspberry Pi. Change the multimeter setting to do a connectivity test between the SDA pin connected to the Raspberry Pi pin header and the SDA pin of each I/O expander. Do the same for the SCL pins.
    pin header + I/O adapter connectivity test
  7. Finally, check every other GPIO and I/O expander pin to see if they are connected to the correct switch or LED pin according to the tables in step six and step seven.

Step 10: Operating the Turing machine

A graphical user interface (GUI) has been written for programming the Turing machine and is available for download. The GUI requires the installation of the 'PyQt4' Python module.

  1. Install PyQt4 with sudo apt-get install python-qt4.
  2. Download the GUI files and extract them, saving them to the /home/pi directory.
  3. One of the files is a configuration file (config.py) which is used to specify the pin connections for each LED and switch. You may rewire your pins and edit this file accordingly. You can also vary the number of pins that are used.
    Note that the tape LEDs have to be connected to the I/O expanders while the switches and program LED have to be connected to the Raspberry Pi pin header.
    A sample config.py file:

    # Specify the number of LEDs.
    LEDno = 11
    # Specify array of bus addresses in decimal: bus 0 corresponds to address 56; bus 1 corresponds to address 57.
    Bus = [56,57,58]

    # Create an array of LEDs.
    LED = []
    for x in range(LEDno):
        LED.append([])
        for y in range(2)
            LED[x].append([-1, -1])
    # Assign a bus and pin number to the LED, in the format LED[LED number][colour(R=0,G=1)] = [Bus number] [Pin number].
    # LED 0 (green) is connected to pin 0 of bus 0 (address 56)
    LED[0][1] = [0, 0]
    LED[1][1] = [0, 1]
    LED[2][1] = [0, 2]
    LED[3][1] = [0, 3]
    LED[3][0] = [0, 4]
    LED[2][0] = [0, 5]
    LED[1][0] = [0, 6]
    LED[0][0] = [0, 7]
    LED[4][1] = [1, 0]
    LED[5][1] = [1, 1]
    LED[6][1] = [1, 2]
    LED[7][1] = [1, 3]
    LED[7][0] = [1, 4]
    LED[6][0] = [1, 5]
    LED[5][0] = [1, 6]
    LED[4][0] = [1, 7]
    LED[8][1] = [2, 0]
    LED[9][1] = [2, 1]
    LED[10][1] = [2, 2]
    LED[10][0] = [2, 5]
    LED[9][0] = [2, 6]
    LED[8][0] = [2, 7]

    # Assign Raspberry Pi GPIO pins to the pushbutton switches.
    RunPause = 7
    Continue = 11
    Reset = 13
    WriteErase = 12
    MoveTapeLeft = 16
    MoveTapeRight = 18
    ProgramLEDRed = 8
    ProgramLEDGreen = 10
    # Set a delay (in seconds) between steps when running the program.
    RunDelay = 0.5

  4. To use the GUI, first extract the downloaded files with the command: tar -xvf turing-machine-gui.tar.gz, then run the python code by typing python gui.py. If you encounter an error message "IOError: [Errno 5] Input/output error", the I/O expanders on the circuit are not wired correctly. Check that the Vss/Vdd/SDS/SCL and address pins are connected correctly.
  1. Now, let's revisit the bit inversion program mentioned in the first section by implementing it on the Turing machine we've built.
  2. Firstly, click "Add State" to create a 2-state Turing machine.
    GUI one, Turing machine state choice
  3. Next, configure the state table using the guide below. Save the program by clicking the "Save Program" button, and you can load it using "Load Program" in the future.
    state table configuration
  4. Alternatively, configure the state table using the more conventional state table in view two:
    alternate GUI Turing state view
  5. Next, initialise the tape to 110 by using the "Write/Erase", "Move tape left" or "Move tape right" switches.
    initialise the values on the tape
  6. Alternatively, you could use the GUI to initialise the tape.
    GUI tape initialisation
  7. Finally, click the "Run/Pause" switch to run the program which you have created and click it again to pause the simulation. The Program LED will turn green to signify that the program is still running and the message window in the GUI will display the current simulation step and current state that the Turing machine is in.
    run/pause Turing machine program
    The "Continue" switch allows you to step through the simulation to observe what the Turing machine is doing at each step.
    At the end of the simulation, the Program LED will turn red to signify that the simulation has ended. You can click the "Reset" switch to reset the simulation and the tape to its original configuration. Clicking "Run/Pause" and "Continue" straight after the simulation will rerun the program from State 0 but it will process the tape from the end of the previous simulation.
  8. To create a new program, click "Clear Program" to keep the current number of states but reset the instructions to their default options, or "Reset Program" to recreate a new state table altogether with only one state.
    Try creating other programs on your own! There are more exercises in the next section which you can follow as well.