22187_Turing-MProgramming

A Turing machine M is a finite device, which performs operations on a paper tape. This tape is infinite in both directions, and is divided into single squares along its length. At any given time each square of the tape is either blank or contains a single symbol from a fixed finite list of symbols s₁, s₂, ... , s_n, the alphabet of M. We will let B denote a blank, and count it as the symbol s₀ belonging to M's alphabet. M has a head which at any given time may read and/or write a single square of the tape.

M is capable of three kinds of simple operation on the tape, namely:

(a) write a symbol from the alphabet of M into the square which the head is pointing to,

(b) move the head one square to the right of that being scanned,

(c) move the head one square to the left of that being scanned.

At any given time M is in one of a fixed finite number of states, represented by symbols q₁, q₂, ..., q_m. During operation the state of M can change. The action that M takes at any instant depends on the current state of M and on the symbol currently being scanned. This dependence is described in M's specification which consists of a finite set Q of quadruples, each of which takes one of the following forms:

q_i  s_j  s_k  q_l
q_i  s_j  L  q_l
q_i  s_j  R  q_l

( 1 ≤ i, l ≤ m, 0 ≤ j, k ≤ n )

A quadruple q_i  s_j  x  q_l in Q specifies the action to be taken by M when it is in the state q_i and scanning the symbol s_j, as follows:

(1) Operate on the tape thus:

   (a) if x = s_k, erase s_j and write s_k in the square being scanned;

   (b) if x = L, move the head one square to the left;

   (c) if x = R, move the head one square to the right;

(2) Change into state q_l.

The specification Q is such that for every pair q_i  s_j there's at most one quadruple of form q_i  s_j  x  q_l ; otherwise there could be ambiguity about what M does next.

To begin a computation, M must be provided with a tape and positioned so that a specified square is being scanned; further, M must be set in some prescribed initial state. Then, if M is in the state q_i and scans the symbol s_j, it acts as described above provided that there is a quadruple of form q_i  s_j  x  q_l in Q. This kind of action is then repeated for the new state and symbol scanned, and so on. M continues in this way for as long as possible. The operation of M terminates only when it is in a state q_i scanning a symbol s_j such that there is no quadruple of the form q_i  s_j  x  q_l, i.e. there is no quadruple in Q that specifies what to do next.

To simplify our problem, let's make some limits to the Turing-M and Q:

(1) n = 1, s₀ = B, s_i = *, i.e. the symbol is either * or blank ;

(2) m ≤ 100, i.e. there are at most 100 states;

(3) computation (determined by Q, initial state and the initial configuration of the tape) must terminate within 100000 steps.

Now we use this limited Turing-M for computing a function f(x), x and f(x) are non-negative integers and 0 ≤ x ≤ 50.That's to say, for any given x, M terminates to f(x). Here is how it works:

First we define the input for M, x is represented by (x+1) consecutive symbol '*'s on the tape, other squares on the tape contains symbol B, i.e. blank, and the head initially points to the leftmost '*';

We assume that the initial state for M is q_l, now M computes according to Q until it terminates;

Finally we define the output of M is the number of '*' on the tape in the end (unnecessary to be consecutive), and this number should be f(x).

If for every x∈dom(f), M outputs f(x), we say M is computing f.

The problem here is to devise a program for M (Q indeed) so that it's computing a given f. For simplicity, f here is function in the form of f(x) = ax + b ( a, b are non-negative integers and 0 ≤ a, b ≤ 10, dom(f) = [0, 50], i.e. 0 ≤ x ≤ 50 ).

There're several test cases. For each case there's a single line containing two numbers, a and b. Input is terminated by EOF.

For each case first output the case number "case 1:", "case 2:", etc. then output the program, i.e. several lines of quadruples of Q (at most 100 states), use number i to represent q_i output format should be the same as sample output. The solution may be not unique, just output any proper one.

1 2
1 0

case 1:
1 * L 7
7 B L 8
8 B * 3
10 * L 5
case 2:
1 * B 2

M is to compute f(x) = x + 2, now let M to compute f(3), the initial configuration of M would be

             ↓ (q1)

......BBBB****BBBB......

and final configuration would be

             ↓ (q3)

......BB*B****BBBB............

since there're 5 '*'s at last, so output of M is 5, which is equal to f(3) = 3+2 = 5.

"10 * L 5" is actually unnecessary.