Turing Machine

Alan Turing - one of the founding fathers of computer technologies and cryptography - described extremely simplified abstract "computer" in 1936. While quite inefficient, it potentially allows to encode any imaginable program and solve any problem. Turing used it to solve a couple of theoretical questions about "general computability", but we generally do not care.

The main point is that Turing's Machine itself is significantly different from our programming experience - and thus is the source of amusement for programmers.

How it works

Imagine the tape (a kind of endless list or array) with values as its "external" memory. Small robotic insect sits atop one of the cell of this "tape". It has single "internal" memory value, called its "state" and generally denoted by letter q.

At every step this robot can see the value on the tape in the current cell (let's denote it with a) and can do operations of three kinds:

• change the value a in the current cell of the tape to some different
• change its own state q to some different
• shift to the adjacent cell on the tape (to the left or right)

The "program" for such machine consists of set of rules for every possible pair of q and a which actions should be taken.

Consider an example:

robot:     (*0*)

tape:  ___  _X_  _X_  _X_  _X_  ___

We have a sequence of letters X written on the tape. All other spaces are filled with spaces. Robot is initially in the sate q=0 and positioned at the leftmost cell of the sequence. The goal is to change rightmost letter of the sequence to Y.

So we need a robot to traverse sequence to the right till end of sequence is found, then step back 1 cell and write Y here. The set of rules is "academically" represented as a table with robot states in columns and tape values in rows:

            |      q = 0      |       q = 1        |
------------+-----------------+--------------------+
 a = X      |   step right    |  write Y to tape   |
            |                 | change q to "stop" |
------------+-----------------+--------------------+
 a = space  |  change q to 1  |                    |
            |    step left    |                    |
------------+-----------------+--------------------+

We are going to have some problems to be solved with it - and so we have prepared TM interpreter and below the description of its syntax follows.

Turing Language Description

I'm not aware of any "standard" of language for Turing Machine, so here is some custom implementation.

The "program" consists of "rules" for certain q and a each. Rules may be written in any order. Every rule occupies a line (or could be split to several for convenience). The example above may be written as follows:

q=0 a=X   R         ; comments start with semicolon
q=0 a=.   q:1 L     ; dot means "space" for values on the tape
q=1 a=X   a:Y q:!   ; exclamation mark means state of "halt" (e.g. stop, end)

Every rule should have q=... and a=... to describe state and cell value this rule is about. Also up to 3 actions could be specified:

• changing internal state is written with q:...
• changing value on the tape is written with a:...
• moving to the left or right is denoted with L and R

Initial state is always 0. Values of the tape are represented with single characters, but internal states could be even whole words for convenience. Let's regard another example.

Order of the parts forming a rule is unimportant (so a=. q=0 L q:1 and L a=X q:1 q=0 will work the same) - however note that "actions" are always performed "simultaneously" - robort first decides what changes are to be done to current cell, internal state and position - and then all those changes happen at once. So action L a:Y doesn't mean that robot shall first move tan then write (to the neighboring cell) - that's mistake.

Larger example

Suppose the tape has binary number (consisting of 0-s and 1-s) on it. Robot starts on the left side and needs to crawl over the number, then append "parity bit" on the right side, so that total number of 1s is even.

Program could be written like this:

;at the beginning switch to "even" state (not regarding current cell content)
q=0 a=01.
  q:even

;now in either "even" or "odd" state, if current digit is 0, simply shift further
q=even,odd a=0
  R

;but if current digit is 1 we need not only shift, but also toggle the state - hense two rules
q=even a=1
  q:odd R
q=odd a=1
  q:even R

;at last, when space is found, we need to put 1 or 0 here, depending on current state
q=even a=.
  q:! a:0
q=odd a=.
  q:! a:1

You see here some convenient features:

• empty lines and comments are of course ignored
• lines with indentation (padding) are continuations to preceeding lines, so we write rule state on first line and actions on the next
• rule for several statuses is written with q=even,odd, while rule for several values is written with a=01.

If the program finishes successfully (reaches state q=!) the output is the piece of tape till the last changed cell.

Two-Dimensional (extension)

In some problems we want turing machine to work on the 2d plane, rather than on a linear tape. For this just small additions are used.

1. Everything about machine state and values on tape (now rather grid) remains the same - all q... and a... things.
2. We only get additional ways to move. To enable this special comment ;2d should be used - after it is encountered, parser will allow the new movement commands.
3. For convenience there are two manners of making moves - "cartesian" and "polar". For "cartesian" manner we simply add moves 'U' for "up" and 'D' for "down" to existing 'L' and 'R' (left, right).
4. Polar (or "turtle") manner is different. Machine is supposed to have some "direction" and could turn 90 degrees left and right, move forward and backward. Corresponding commands are 'TL' and 'TR' (for turns) and 'FW', 'BK' (for forward and back).
5. Machine's direction is not changed on going back. It is also not affected by "cartesian" moves.
6. Initial direction is towards right.
7. Machine starts at top-left corner of the square representing input (non-empty fragment of the plane)

For example, consider we have a rectangle filled with 0s and 1s - a kind of carrot-and-cabbage field. And we want to change its border to '+'s - i.e. make a fence around it.

The program could be like this:

q=0 a=01        a:+ FW      ; normal state - change 0 or 1 to '+' and move on
q=0 a=.         q:1 BK      ; got out of the field? make step back
q=1 a=+         q:2 TR      ; now turn to the right
q=2 a=+         q:0 FW      ; make step forward out of already marked and switch to normal state
q=0 a=+         q:!         ; if in "normal state" we find already marked cell - halt!

Here how it should convert the field:

 initial             processed

101010101            +++++++++
010101010            +1010101+
101010101            +0101010+
010101010            +1010101+
101010101            +++++++++