Karel J Robot as a Turing Machine

The most general kind of computation is defined by a Turing Machine, invented by the mathematician Alan Turing. The word "computable" means able to be computed by a Turing Machine. Modern computers and computer languges simulate finite Turing Machines. Karel J. Robot is no different. Actually we don't need the full power of Karel to simulate the operation of a Turing Machine. Actually there are many equivalent definitions of Turing Machines. Most universities have a course called something like Computability and Automata that explain this in detail. There are also several such books.

Here we will use the following characterization of a Turing Machine.

A Turing Machine has

• a tape that is infinite in two directions, divided up into numbered cells. At each cell of some finite portion of the tape there is initially either nothing or a 1. The initial tape is the input to the machine.
• a movable read/write head that is initially positioned over cell 0.
• a set of internal "states". One of these is the initial state and the machine always begins in this state. One of the states is a final state and if the machine ever enters this final state it halts. If it halts the current values on the tape are its output.
• a definite "program" that will proceed step by step. At each step it does the following. It reads the current cell of the tape. Depending on what it finds there and its current state, it optionally writes something (a blank or a 1) at that position of the head, moves the head one cell left or right or not at all, and changes to some state, which could be the current state or another.

You can read more about Turing Machines at http://plato.stanford.edu/entries/turing-machine/.

Simulating a Turing Machine using Karel J Robot

The tape will be first street and first avenue, with the origin as the zero cell. A single Robot with an infinite number of beepers in its beeper bag will be the tape head. Its initial position is the origin. We read the current tape position by asking if there is a beeper on the current corner. We can either place a beeper (after clearing the corner) or just clear the corner to simulate writing a 1 or a blank. The program will consist of a set of mutually recursive methods defined by a set of rules to be given below. These methods represent both the states and the program. A robot changes its state by sending itself the message corresponding to that state.

First we need some infrastructure. These define how the "head" moves and how it writes on the tape. We will also show the finalState.

public void putBlank()
{
	while(nextToABeeper())
		pickBeeper();
}

public void putOne()
{
	putBlank();
	putBeeper();
}

public void moveLeft()
{	
	faceWest();
	if (frontIsClear())
	{	move();
	}
	else
	{	turnRight();
		move();
	}
}

public void moveRight()
{
	faceSouth();
	if(frontIsClear())
	{	move();
	}
	else
	{	turnLeft();
		move();
	}
} 

public void finalState()
{	turnOff();
}

With this infrastructure the states of the machine are a set of methods that might be called state1, state2, etc. The body of the method defines how the machine behaves in that state for any value on the tape. The first message sent to the robot is always state1 (the initial state). One of your states is the final state and it simply executes a turnOff instruction.

The bodies of all the other states consists of an if statement with an else part. The test is always on nextToABeeper. The if part represents seeing a 1 on the tape and the else part seeing a blank. Within each part the structure is identical with up to three statements in each part with the statements that appear always in the following order.

1. you may send the message putBlank or putOne, but do this first.
2. you may send the message moveLeft or moveRight, but do this second
3. you now must send the message corresponding to some state (perhaps this same one or another, including finalState).

For example state 1 might look like:

public void state1()
{	if(nextToABeeper())
	{ 	putBlank();
		moveRight();
		state3();
	}
	else
	{ 	moveLeft();
		state7();
	}
} 

A Turing machine can run infinitely (never halt) or it can enter the final state and halt. Don't forget to provide a final state which isn't like these, but just sends turnOff.

Notes on implementation. You could create a TuringMachine class that extends Robot and has the infrastructure methods (along with turnRight, etc.) but no state methods except the finalState method. Then, to build an individual turing machine, create a new class that extends TuringMachine and provides the (other) state methods. Then create one of these at the origin with an infinite number of beepers and send it the state1 message. Of course you must create a world that has some beepers (perhaps) along first street and/or first avenue.

Last updated: October 12, 2003