Im trying to learn about and set up Turing Machines (TMs) the simplest ways using the simplest definite rules. I am using my previous knowledge on simple Cellular Automata to do this. I want to write the computer code, but first I have to get some understanding of the restrictions and possibilities of TMs.
Firstly i define an operation as follows:
Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:
- replace color $C$ with $0$ or $1$. (at current position of tape head) move
- tape-head (change its position).
- change state $S$ with $0$ or $1$ (at new position).
For each operation:
In general does a TM only have only one halting-operation? (i.e. can only one operation promote the halting or can more than one operation do that?).
Can the tape-head also stop at a fixed position? (i.e. not move its head). Instead of the rules $0$ (move left) and $1$ (move right), it can also $2$ (not move anywhere) or even jump two units to the left or right?
My last question is basically the same as the last question..
- Can the tape-head move more than one unit to the left or right?
The reason I ask this, is because if there is only one halting state in no more than one operation, the number of rules (in my setup) can be reduced. And if the tape-head can move more than one unit either to the left or right or both my guess is that it can produce more complex outputs. But my questions are concerning what is the limitations of a Turing Machine.
If something was unclear I can try this example:
inp: outp: Op(0,0) => 110 Op(0,1) => 101 Op(1,0) => 111 Op(1,1) => 001*
Of the output ($b_2b_1b_0$), where the first bit ($b_0$) represent the tapehead-move direction, $b_1$ represents the new state, and $b_0$ represents the changed color. The asterisk shows that a halting operation should be performed.
The first question I asked wether there was possible to have more than one halting operation in a TM. Basically I ask wether I can have two or more asterisks like this, or if its not allowed:
inp: outp: Op(0,0) => 110 Op(0,1) => 101 Op(1,0) => 111* Op(1,1) => 001*
So can more than one operation perform the halting operation?
Can we move the tape head more than one unit to the left or right, or can it stand still?