Vrftsjtryk

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:

Operation (Op)

Do operation based on current color ($C$) and its state ($S$) i.e. $Op(c, s)$:

1. replace color $C$ with $0$ or $1$. (at current position of tape head) move


2. tape-head (change its position).


3. 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.

Example

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*

Recap

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?

To answer any kind of question like this, you need to choose one of the standard definitions of Turing machines (there are several but they're all essentially the same) and prove that adding the feature you want doesn't increase the computational power. You do that by showing how to simulate the feature using the standard machine.

• 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?).

It doesn't matter. If you want three halting states and I insist that there can be only one, then have three states called $h_1$, $h_2$ and $h_3$ and design the transition function so that, if the machine ever enters one of those, its next transition is to $mathrm{HALT}$.

• 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?

Again, it doesn't matter. If I insist you must move left or right, you can move one step left and then move back to the right; you can move two steps to the right by moving one step, twice.

• Can the tape-head move more than one unit to the left or right?

Even that doesn't affect things: random-access Turing machines have an "address tape" onto which you can write a number and a special state that causes the head to move straight to the tape cell indexed by that number. Again, same power.

Multiple tapes, inserting and deleting characters, two-dimensional (or more!) tapes. Almost anything you can imagine makes no difference, and proving these things are standard exercises in computation theory textbooks.