Programming Turing Machines

In the previous post, we built a LEGO Turing machine. However, we did not talk about how to run the machine. In this post, we focus on how to program Turing machines. Starting from a very naive implementation which only uses a single task, we will add more features to the machine incrementally:

• multi-task
• concurrent movements
• log via USB
• support its own programming language
• transfer a program via USB

Turing Machine

Turing Machine is an abstract computing device which was contrived by Alan Turing. It runs the following algorithm:

1. Read : Read the current cell of the tape.
2. Transition : Determine the next state, output, and shift direction based on the current state and the content of the current cell. If the new state is either Accept or Reject state, stop the machine.
3. Write : If needed, change the value of the current tape cell.
4. Move : Move the tape to the left or right based on the result of 2.
5. Goto 1.

1. Simple, Single-task Turing Machine (Download)

We start with a simple implementation. This implementation has the following properites (limitations):

• Single-task
• Controlled by a Transition Relation
• Serialized Movement: Read - Write - Move, one by one.
• No Logging

1.1 Main Loop

TASK(TM)
{
    while(true)
    {
        /* Read */
        input = Read();

        /* Make transition */
        (state, output, dir) = transition(state, input);
        if(state == HALT_STATE)
            HALT;

        /* Write (Optional) */
        if(input != output) {
            write(output);
        }

        /* Move */
        move(dir);
    }
}

The main loop is a direct translation of the algorithm presented above. Repeatedly, it reads the tape cell, makes a transition which is defined in transition function, optionally changes the current tape cell, and moves the tape as directed.

1.2 Reader

_Bool read()
{
    U16 color;
    _Bool input;

    /* 1. Move READ Header to TAPE */
    nxt_motor_set_speed(READ_MOTOR, SPEED, 1);
    while(nxt_motor_get_count(READ_MOTOR) <= READ_REV) {
        /* do nothing */
    }
    nxt_motor_set_speed(READ_MOTOR, 0, 1);

    /* 2. Read Sensor Value */
    ecrobot_set_nxtcolorsensor(COLOR_SENSOR, NXT_LIGHTSENSOR_GREEN);
    ecrobot_process_bg_nxtcolorsensor();
    color = ecrobot_get_nxtcolorsensor_light(COLOR_SENSOR);
    input = color < COLOR_THRESHOLD ? 1 : 0;
    ecrobot_set_nxtcolorsensor(COLOR_SENSOR, NXT_LIGHTSENSOR_NONE);
    ecrobot_process_bg_nxtcolorsensor();

    /* 3. Move READ Header back */
    nxt_motor_set_speed(READ_MOTOR, -SPEED, 1);
    while(nxt_motor_get_count(READ_MOTOR) >= 0) {
        /* do nothing */
    }
    nxt_motor_set_speed(READ_MOTOR, 0, 1);

    return input;
}

read function does three operations:

1. Move the READ header to the TAPE
2. Read the sensor value
3. Move the READ header back

Let’s focus on the actual reading operation (in step 2) because it is relatively trivial to move the header back and forth (step 1 & 3). At line 14, it turns on the color sensor and set it to NXT_LIGHTSENSOR_GREEN mode. At line 16, ecrobot_get_nxtcolorsensor_light function returns the raw value which measures the reflection around the sensor. We use the pre-defined constant COLOR_THRESHOLD to determine whether the given raw value is interpreted as 0 or 1. (line 17). Then, it turns off the light sensor (line 18).

Note that it is necessary to call ecrobot_process_bg_nxtcolorsensor function at line 15 and line 19. When we change the sensor mode by calling ecrobot_set_nxtcolorsensor at line 14, nothing really happens on the sensor side. It only changes the sensor status on the memory without affecting the sensor itself. It is the job of ecrobot_process_bg_nxtcolorsensor function which makes requested changes on the sensor side and copies the raw value of the sensor to the memory. If we do not call ecrobot_process_bg_nxtcolorsensor at line 14, 1) the sensor is not set to green light mode and 2) the value we read at line 16 can be an outdated value— it is the value of the sensor when ecrobot_process_bg_nxtcolorsensor function was called last time.

1.3 Writer

void write(_Bool output)
{
    int sign = output == 1 ? 1 : -1;
    nxt_motor_set_speed(WRITE_MOTOR, sign * SPEED, 1);
    while (sign * nxt_motor_get_count(WRITE_MOTOR) <= WRITE_REV) {
        /* do nothing */
    }
    nxt_motor_set_speed(WRITE_MOTOR, 0, 1);
    nxt_motor_set_count(WRITE_MOTOR,
                        nxt_motor_get_count(WRITE_MOTOR) % WRITE_REV);
}

Writing operation is simple. It flips the bit on the tape based on the output value — clockwise to write 0 and counter-clockwise to write 1. The constant WRITE_REV is defined to be 180.

1.4 Tape Mover

void move(_Bool dir)
{
    int sign = dir == RIGHT ? 1 : -1;
    nxt_motor_set_speed(TAPE_MOTOR, sign * TAPE_MOV_SPEED, 1);
    while (sign * nxt_motor_get_count(TAPE_MOTOR) <= TAPE_MOVE_REV) {
        /* do nothing */
    }
    nxt_motor_set_speed(TAPE_MOTOR, 0, 1);
    nxt_motor_set_count(TAPE_MOTOR,
                        nxt_motor_get_count(TAPE_MOTOR) % TAPE_MOVE_REV);
}

move function is similar to write. Based on the given argument dir — which is either LEFT or RIGHT, it rotates the motor to move the tape to the given direction. The constant TAPE_MOVE_REV is set to 1800 (five cycles).

Limitations

This implementation works well, however, there are limitations of this implementation.

• Single-task with polling : We have one big monolithic task doing every operation — read/write/move — in it. It uses busy-wait polling to control motors as the following code (part of move function).

   while (sign * nxt_motor_get_count(TAPE_MOTOR) <= TAPE_MOVE_REV) {
      /* do nothing */
   }

Problem: It wastes CPU cycles and prevent us from doing other tasks. We are going to improve this by implementing multi-task version.

• Controlled by a Transition Relation : In this implementation, we need to provide a transition relation to program the machine. For example, the unary addition program has the following transition relation:

This form is difficult to understand and maintain. We will introduce an assembly-like language to program the machine. With the new language, we may program the unary addition as follows:

/* Before it meets the first ones */
0:  READ
    CJUMP1 1
    MOVE   L
    JUMP   0

/* scanning first operand */
1:  MOVE   L
    READ
    CJUMP1 1
    WRITE  1
    MOVE   L

/* scanning second operand */
2:  READ
    CJUMP0 3
    MOVE   L
    JUMP   2

/* last position */
3:  MOVE   R
    READ
    CJUMP0 ERR
    WRITE  0

/* computation finished, keep moving to the right until it ends */
4:  MOVE   R
    READ
    CJUMP1 4
    HALT

ERR:
    ERROR

• Serialized Movement: In the current implementation, Read/Write/Move operations occur one after another, even if it is physically possible to do them simulataneously in some cases. For example, the read header can start to move to the tape while the tape is being moved to the next position. The only constraint here is that the tape should not move when the colorsensor reads the value. By the same argument, we may move the writer lever and the read header simulataneously. However, we should be careful to avoid any physical collision. To implement concurrent movements, it is natural to program using multiple tasks. This extension will introduce more complexity to an implementation. We will see how to use our verification tool to make sure that an implementation has desired properties.

• No Logging : Currently, we do not have any logging feature so that it is difficult to check the internal status of the machine or debug a program. We will start to add logging by using the LCD display in the NXT brick. Then, we will use USB communication to output log messages to the connected computer.