Introduction
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.
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.
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
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.
Step 2: Add the 11 LEDs to represent the tape
Components:
– 11 × Bicoloured LEDs.
– 11 × 270Ω resistors.
– Jumpers.
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.
Step 3: Add the switches and the program LED
Components:
– 1 × Bicoloured LED.
– 6 × Pushbutton switches.
– 1 × 270Ω resistors.
– 6 × 10kΩ resistors.
– Jumpers.
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.
Step 4: Add the I/O expanders
Components:
– 3 × PCF8574AN I/O expanders.
– Jumpers.
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.
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.
-
Step 5: Connect the SDA and SCL lines
Components:
– 2 × M/F jumper cables.
– Jumpers.Connect the SDA and SCL pins of each I/O expander together to form the SDA and SCL rails.
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.
Step 6: Connect the tape LEDs to the I/O expander pins
Components
– Jumpers.
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) |
Connect the pins of each green LED to the respective pins on the I/O expander according to the circuit diagram.
Similarly, connect the red pins of each red LED to the respective pins on the I/O expander according to the circuit diagram.
Step 7: Connect the switches and program LED to the Raspberry Pi pin header
Components:
– 8 × M/F jumper cables.
– Jumpers.
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 |
- Connect the pins of the Raspberry Pi to the breadboard using the male/female jumper cables, in the same layout as the pin header
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.
3. Connect the program LED pins to the respective M/F jumper cables after reconnecting them to the breadboard.
4. Similarly, connect the operation switches to the respective M/F jumper cables.
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.
Step 8: Make the circuit neater (optional)
Components
– 1 × Adafruit Pi cobbler breakout kit.
– Jumpers.
- 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.
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.
Step 9: Test and troubleshoot the circuit
Components:
– 1 × Multimeter.
- 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.
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.
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.
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.
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.
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.
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.
- Install PyQt4 with sudo apt-get install python-qt4.
- Download the GUI files and extract them, saving them to the /home/pi directory.
- 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 - 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.
- Now, let’s revisit the bit inversion program mentioned in the first section by implementing it on the Turing machine we’ve built.
- Firstly, click “Add State” to create a 2-state Turing machine.
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.
4. Alternatively, configure the state table using the more conventional state table in view two:
5. Next, initialise the tape to 110 by using the “Write/Erase”, “Move tape left” or “Move tape right” switches.
6. Alternatively, you could use the GUI to initialise the tape.
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.
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.
Source: Section 3: Building the Turing Machine