1)Linear Bounded Automaton
2)Multi-stack Machines
3)Counter Machines
4)Limits on the number of states and symbols
Explanation:
1)Linear Bounded Automaton:
is a type of turing machine wherein the tape is not permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input,the head stays where it is,in the same way that the head will not move off the left-hand end of an ordinary turing machine's tape.
A Linear bounded automaton is a TM with a limited amount of memory. It can only solve problems requiring memory that can fit within the tape used for the input. Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor.
2)Multi-stack Machines:
A deterministic two-stack machine is a deterministic TM with a read only input and two storage tapes. If a head moves left on either tape, a blank is printed on that tape.
Lemma: An arbitrary single tape TM can be simulated by a deterministic two-stack machines.
Proof: the symbols to the left of the head of the TM being simulated can be stored on the stack,while the symbols on the right of the head can be placed on the other 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.
3)Counter Machines:
are offline TMs (is a multi-tape TM whose input tape is read only) whose storage tapes are semi-infinite,and whose tape alphabets contain only two symbols Z and B(Blank).
Furthermore the symbol Z,which serves as a bottom of stack marker,appears initially on the cell scanned by the tape head and may never appear on any other cell.
An integer i can be stored by moving the tape head i cells to the right of Z. A stored number can be incremented or decremented by moving the tape head right or left. We can test whether a number is zero by checking whether Z is scanned by the head,but we cannot directly test whether two numbers are equal.
Instantaneous description of a counter machine can be described by the state,the input tape contents,the position of the input head,and the distance of the storage heads from the symbol Z.
The counter machine can really only stores a count on each tape and tell if that count is zero.
4)Limits on the number of states & symbols:
Another way to restrict a TM is to limit the size of the tape alphabet or the number of states.
If the alphabet,number of tapes,and number of states are all limited,then there is only a finite number of different TMs,so that restricted model is less powerful than the original.
2)Multi-stack Machines
3)Counter Machines
4)Limits on the number of states and symbols
Explanation:
1)Linear Bounded Automaton:
is a type of turing machine wherein the tape is not permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input,the head stays where it is,in the same way that the head will not move off the left-hand end of an ordinary turing machine's tape.
A Linear bounded automaton is a TM with a limited amount of memory. It can only solve problems requiring memory that can fit within the tape used for the input. Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor.
A deterministic two-stack machine is a deterministic TM with a read only input and two storage tapes. If a head moves left on either tape, a blank is printed on that tape.
Lemma: An arbitrary single tape TM can be simulated by a deterministic two-stack machines.
Proof: the symbols to the left of the head of the TM being simulated can be stored on the stack,while the symbols on the right of the head can be placed on the other 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.
3)Counter Machines:
are offline TMs (is a multi-tape TM whose input tape is read only) whose storage tapes are semi-infinite,and whose tape alphabets contain only two symbols Z and B(Blank).
Furthermore the symbol Z,which serves as a bottom of stack marker,appears initially on the cell scanned by the tape head and may never appear on any other cell.
An integer i can be stored by moving the tape head i cells to the right of Z. A stored number can be incremented or decremented by moving the tape head right or left. We can test whether a number is zero by checking whether Z is scanned by the head,but we cannot directly test whether two numbers are equal.
Instantaneous description of a counter machine can be described by the state,the input tape contents,the position of the input head,and the distance of the storage heads from the symbol Z.
The counter machine can really only stores a count on each tape and tell if that count is zero.
4)Limits on the number of states & symbols:
Another way to restrict a TM is to limit the size of the tape alphabet or the number of states.
If the alphabet,number of tapes,and number of states are all limited,then there is only a finite number of different TMs,so that restricted model is less powerful than the original.
Comments
Post a Comment