Automata 09

Turing machine variations

Right input line Turing machine

A Turing machine with an input line being infinite only to the right instead of being infinite in both directions. The reading head moves identically to the classic Turing machine, with the exception that moving left in the left-most cell of the input line doesn’t move the head.

TS Turing machine

In the TS Turing machine, the reading head can stay in the same place, whereas in the classic model each transition must move the head to the right or to the left.

OR Turing machine

In the OR Turing machine, the reading head can either write something to the input line OR move to the Left/Right. This model is also equivalent to the TS Turing machine, and so is equivalent to the classic Turing machine. To show the equivalence with TS Turing machine, we can convert all writing transitions to S-transitions and all moving transitions into input-preserving moving transitions in TS. All non-S transitions in TS Turing machine can be represented as two transitions in the OR Turing machine - one writing and one moving.

Multi-line Turing machine

In each input line the reading head is independent of the others, it can move in any direction and write anything to its input line. Number of lines is finite and must be defined beforehand, we cannot take the number of lines as input.

Using Multi-line Turing machines to prove closure under intersection

A Multi-line Turing machine can represent classic Turing machines running on the same input line. If at least one of lines rejects the input - it is rejected by the whole machine. Lines can be run in sequence. This proves that intersection of definable languages is definable. What about acceptable languages? It is also true, similarly proved with the condition that the input is not accepted if any of the lines is not terminated or rejects the input. What is important - we must run the lines in parallel, as some lines might never terminate. Same can be inferred for union, where at least one line is needed to accept the input.

Double-stack PDA

A double-stack PDA is equivalent to the classic Turing machine. Such automaton is defined to first read all of the input to the first stack, then move it all to the second stack. First stack stores the input to the left of the reading head, second stack stores the input to the right of the reading head (including). The transitions (writing, moving) are then done by moving/popping/pushing elements in the two stacks.

2D Turing machine

A 2D Turing machine is defined to have a 2D infinite input line (bounded on the left and bottom). Moving is then defined in four directions - Left, Right, Up and Down. so clearly, 2D input line can be mapped to a single input line. The only thing left to do to prove equivalence to the classic Turing machine is to define the moving transitions.

We can now emulate 2D Turing machine using 4 input lines, one for the input (mapped from a 2D input using diagonals), one for the coordinate, one for the coordinate and one for re-computing coordinates given a one dimensional input.

Non-deterministic Turing machine

Non-determinism is not a new idea, but what is new is the definition of what input is accepted and rejected. If there exists a computation such that input is accepted, it is accepted. If for all computation input is rejected, it is rejected. Note that there is no symmetry, input is rejected only if there exists no computation that is not rejected. Non-deterministic Turing machine is especially useful when used on acceptable languages. Given a non-deterministic Turing machine , we can build a deterministic one, that runs all possible computations, accepts input if one of them accepts and rejects if all of them reject. We can enumerate all possible transitions from 1 on and then introduce a second input line, that will store the sequence of choices as numbers. Running the input on all possible sequence of choices is exactly equivalent to running with an exception that we will always terminate(!) each run. Note that the reading head on the second line will only move to the right. In order to run all possible sequences of choices, we will introduce the third input line, that will simply preserve input to be copied each time a new run is started.

Closure under prefix using non-deterministic Turing machine

Let there be a classic Turing machine that accepts language Let us add non-deterministic transitions that add letters to the input and then return back to the leftmost input position, arriving to the starting state of Non-deterministic Turing machine we defined now accepts (but doesn’t define!)

Closure under concatenation using non-deterministic Turing machine

Let there be classic Turing machines that define languages Let us define a non-deterministic 2-line Turing machine that defines Let us preserve the first input line (no writing) and use the second input line to run on some prefix of input and then run on the leftover suffix of input. If both accepted the input, accept. Otherwise reject.

In a similar fashion, we can prove that definable and acceptable languages are also closed under Kleen closure and DropOut.