Java Programming Challenge: Creating a Simple Turing Machine - dummies

Java Programming Challenge: Creating a Simple Turing Machine

By Doug Lowe

In 1936, mathematician Alan Turing conceived of a deceptively simple type of computational machine called a Turing Machine. Turing never actually built a Turing Machine. Instead, it was a hypothetical device that he concocted to aid in the study of computability — that is, whether complex problems can be solved by computational steps and whether a machine can be devised that can solve any computable problem. (If you’re interested in knowing more about the history or application of Turing machines, you can find many articles about them on the Internet. Just use any search provider to search for “Turing machine”.)

The operation of a Turing Machine is simple. It embodies just a few basic concepts:

  1. The heart of a Turing Machine is an infinitely long tape which is divided into cells onto which information can be written.

    In actual practice, of course, no physical device can have an infinite number of cells. But in the theory of a Turing Machine, the tape is infinite.

  2. The information that can be written onto each cell is limited to a single symbol, such as a 0 or a 1. However, information can be represented by the combined values of successive cells.

    For example, you might represent numeric values by successive occurrences of the symbol 1 followed by a 0. Thus, 1110 represent the value 3 because there are three 1’s; 111111011110 might represent the values 6 and 4 (six 1’s followed by a zero, followed by four 1’s followed by another zero).

  3. The Turing Machine contains a read-write head that is always positioned over one (and only one) of the cells of the tape.

    This read-write head can read the symbol that’s contained in the cell. It can also erase the symbol and, if desired, write a new symbol in its place. The cell over which the read-write head is positioned is referred to as the current cell or the head cell.

  4. The tape is motorized so that it can be moved left or right under the read-write head one cell at a time.

  5. The machine has a state, which is represented by a symbol such as a letter of the alphabet.

Like any computer, a Turing Machine can be programmed. However, a program for a Turing Machine doesn’t remotely resemble a Java program.

Instead, a Turing Machine program is simply a set of rules that are evaluated to determine what actions the machine should take. Each rule identifies an action to be taken when the current cell contains a given symbol and the machine is in a given state. For example, a rule might dictate what to do if the current cell contains a 1 and the machine state is “a”.

Each rule can specify any of three actions:

  • Erase the current cell or write a new value to the cell.

  • Move the tape one cell to the left or one cell to the right.

  • Change the state of the machine to a new state.

For example, a rule might specify that if the current cell contains a 1 and the machine state is “a,” the Turing Machine should write a 0 in the current cell, advance the tape one cell to the right, and change the machine state to “b.”

In addition to a program, the Turing Machine’s tape can have an initial value.

That’s it; that is the entire definition of a Turing Machine. In spite of its simplicity, a Turing Machine can calculate anything from 2+2 to the trajectory of a rocket to Mars.

For this challenge, you must create a very simple Turing Machine. To simplify the problem, accept the following limitations on this version of the Turing Machine:

  • The tape doesn’t have to be infinite. You can use any Java feature — an array, a string, or a collection — to represent the tape.

    (Note that although the tape doesn’t have to be infinite, you must be able to easily move left or right from the current cell. If you choose to use an array, don’t start with the current cell at element 0 because you won’t be able to move left from there.)

  • A cell can be empty or it can contain any letter or numeral. An empty cell is represented by an underscore character.

  • The state can be any single alphanumeric character.

  • The program for the Turing Machine will be read from a text file. This text file contains one rule per line. Each rule contains five characters, separated by spaces, that provide the details for each rule, as follows:

    • Current cell: The value to be matched for the current cell.

    • Current state: The value to be matched for the current machine state.

    • New cell: The value to write to the new cell. _ to erase the cell, * to leave the cell unchanged.

    • Movement: L or R to move the tape left or right; H to halt the program; any other character to not move the tape.

    • New state: The new value for the machine state.

  • For example, the following says that when the current cell is 1 and the state is “a,” the current cell should be set to 0, the tape moved one cell to the left, and the state should be set to “b:”

    1 a 0 L b
    • The first line of the text file should contain a string that represents the initial values for the tape.

    • The second line of the text file should contain the initial status.

The following figure shows the user interface for the sample solution, but you’re free to use any user interface design you’d like for this project.

A potential Turing Machine interface.
A potential Turing Machine interface.

Here are some considerations for creating the interface:

  • Value and current cell: At the minimum, you should show the value of the tape and highlight the current cell.

  • Tools and display: You should also provide the ability to start, stop, or restart the program’s execution, and you should display the results of each step of the program.

  • Program execution: You can provide a way for the user to run the loaded program from start to finish, as well as a way for the user to single-step through the program by clicking a button to execute each step of the program.

  • Loading the program: You should provide buttons that let the user load a Turing Machine program from a text file and that let the user reset the machine to run the program again.

Here’s a tip for implementing the infinite tape: Use three string variables to hold the tape values, one for the single character stored in the current cell, a second for the characters to the left of the current cell, and a third for the characters to the right of the current cell. You can then easily move the current cell left or right by using the right combination of concatenation and substring operations.

You can find the solution to this challenge on the Downloads tab of the Java All-in-One For Dummies, 4th Edition product page.

Good luck!