Test: Multistack Machines, Counter Machines - Computer Science Engineering (CSE) MCQ

The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

nstantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.

 Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.

 Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.

A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.

Both the statements are true. Both the statements are properties of Multistack machines.

A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.

For a basic TM, there exists a 2-counter, 3-counter and 4-counter machines
We can prove them using Deterministic two stack turing machine.
Counter machine: