Turing Machine Architecture

This post describes the general discussions we have regarding the architecture of the Turing Machine robot.
Participants: Anders, Martin, Mikkel and Sean

Topics of discussion regarding the architecture of the Turing Machine.
In this log entry four central problems are presented along with the gist of our discussions on the topics and, in some cases, suggestions for solutions or concrete implementations.

Blank input symbols.
Problem: A Turing machine has an input alphabet and a blank symbol in its tape alphabet. Our Lego tape can only hold two different symbols (represented by shifting a Lego block to the right and left sides of the containing bit field). We cannot currently represent a blank symbol with a Lego brick.

One solution would be letting more than one Lego bit blocks represent a single character in the input alphabet. With two bits we have four possible symbols, or three input alphabet symbols and a blank symbol. We plan to use a binary input alphabet, which leaves us with an "extra" bit configuration if we use the idea of two bits per symbol. Using more bits would enable us to represent decimal numbers or even alphabetical A-Z symbols.
We will need a couple of methods to handle bits. When reading an input character that stretches across several bits, we will be reading the bits one at a time, and we will need a method that takes this stream of bits and converts it to a symbol in the input alphabet.
When writing, we will need to reverse the process, converting a symbol in the input alphabet to a stream of bits.

Reading, sending.
Problem: We plan to distribute the complete functionality of the Turing Machine across a PC and the NXT via Bluetooth connection. At which end does computation take place, who waits for signals and when?

The initial idea for control-flow went as follows:

1. Write initial tape configuration to the tape
2. Read the initial state
3. Send value to PC
4. React to answer (from PC)
5. Repeat steps 3-4 until a halting (accept or reject) state is entered

The NXT idles while waiting for a movement signal from the PC. When this is received, the PC waits for a confirmation signal from the NXT while it maneuvers the robot into position over a cell/bit, reads it and sends its contents.
In this model, the PC performs the Turing Machine computations and simply sends movement, read and write calls to the robot.

The PC could also take a hands-off approach, and simply starts the Machine by sending the transition function to the robot which performs all calculations and movements independently on the NXT.

Due to the limitations that the NXT imposes on java code, we have found that keeping a lot of the calculations on the PC might be easier to implement.
More specifically, it appears that maps aren't supported. Our implementation of the transition function uses two maps, one for states and one for input symbols. We find this to be the most intuitive and natural way of representing the transition table.

Converting bits to integers is simply a case of adding 2^i to the result for the i'th bit if it is 1.
Converting integers to bits is a question of taking the remainder of a division by 2 and the dividing the input by 2, rounding down, until the input is 0.

How are states represented?
Convention: What Turing called m-configurations, that is, the part of the Turing Machine that tells it what to do depending on the current input symbol, we have decided to call states, to avoid confusion.
Turing's original state concept has not been renamed, to increase confusion.
Concrete implementation: States are currently represented in the code as a map from input symbol to Action tuples, an Action tuple being a three-tuple of actions to perform on the given input: what to write, which way to shift and which state to enter next.

Initial state in input file?
Problem: We want to be able to give the transition function of the Turing Machine as input, but how do we know which state is the initial state and which states are final?

One solution to the first problem is simply to demand that the first state in the input always be the initial state.
The final, or halting state doesn't need a separate state in the input. Rather, we allow states to point to a next-state "HALT" which doesn't exists in the input. This we are able to do since we know that no actions can be taken once a halt state has been entered, and so we do not need to keep track of the information pertaining to the actions in the halt state.