Introduction
Turing machines are simple, abstract computational tools created to aid in examining the scope and boundaries of what may be calculated. Alan Turing initially introduced them in Turing 1936-7. The "automatic machines," as Turing referred to them in 1936, were created expressly for calculating real numbers. Alonzo Church gave them the moniker "Turing machines" in a critique of Alan Turing's work (Church 1937). They are now regarded as one of the fundamental theories in the development of computability and (theoretical) computer science.
A mathematical model known as a Turing Machine (TM) consists of an infinitely long tape that has been partitioned into cells on which input is provided. A head reads the input tape in this device. The state of the Turing machine is kept in a state register. An input symbol is read, substituted by another symbol, its internal state is altered, and it advances from one cell to the right or left after that. The input string is accepted if the TM reaches the end state; else, it is denied.
A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −
Q is a finite set of states
X is the tape alphabet
∑ is the input alphabet
δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
q0 is the initial state
B is the blank symbol
F is the set of final states
There are several ways to possibly increase the computational capability of a typical TM through extensions of the TM model. In every case, the objective is to demonstrate that these expansions do not increase processing power because a conventional TM can successfully imitate their behaviour, supporting the Church-Turing Thesis. A typical 1-tape Turing computer is capable of computing anything that can be done algorithmically.
Extensions consist of: numerous cassettes, separate scan heads for each, and a two-way, endless tape (with a single scan head) many independent scan heads on a same tape.
Multiple-Tape Turing Machines
Formally, a 6-tuple (Q, X, B,, q0, F) can be used to define a multi-tape Turing machine.
Q is a finite set of states
X is the tape alphabet
B is the blank symbol
δ is a relation on states and symbols where
δ: Q × Xk → Q × (X × {Left_shift, Right_shift, No_shift })k
where there is k number of tapes
q0 is the initial state
F is the set of final states
2. Two-way infinite tape
A two way infinite tape can move indefinitely in either direction. This can be shown to be equivalent to a one way infinite tape by the following argument: It is clear that two one-way infinite tape TMs can be used to simulate a two-way infinite tape. If these are lined up ``side by side'' and the two tapes are interleaved, then a single one-way infinite TM can be constructed which is equivalent.
Any two-sided infinite tape Turing Machine can be simulated on a Turing Machine with a single-sided infnite tape.
A DTM with a one-way infinite tape that simulates an ordinary DTM having a two-way infinite tape. The top track represents the portion of the two-way infinite tape that extends to the right and the bottom track represents the portion extending to the left.
3. Multi Head Turing Machine
A single tape turning machine with "n" number of heads simultaneously reading the symbols on the tape is referred to as a multi head turning machine. All the heads individually move and write after simultaneously sensing the scanned symbols.
As a result, we have a partition of states Q1, Q2,..., Qk for k heads, where each Qi comprises the set of states that use the i'th head. We might have the following for k = 3:
This variant is a useful for certain problems. Consider the language L = {a^n b^n c^n | n ≥ 0}. We know this language is not context-free, but we can build a multi-head Turing machine with k = 3 to recognize this language. Lets call this machine M, which works as follows:
M = “On input w:
i. Initialize each head as follows:
(a) Let head 1 rest on the first input symbol of w.
(b) Let head 2 scan the input for consecutive a symbols until the first b is encountered.
(c) Let head 3 scan the input for consecutive a symbols, followed by consecutive b symbols, until a c is encountered. At this point head 1 should rest on the first a symbol, head 2 should rest on the first b symbol, and head 3 should rest on the first c symbol.
ii. Until the end of string is encountered, loop as follows:
(a) Test if head 1 rests on an a symbol and move right.
(b) Test if head 2 rests on a b symbol and move right.
(c) Test if head 3 rests on a c symbol and move right.
If head 3 rests on a symbol, then the end of the string is has been encountered and
we go on to the next step.
iii. Accept if at the end of the string we have the following:
(a) Head 1 rests on the first b symbol.
(b) Head 2 rests on the first c symbol.
(c) Head 3 rests on the first symbol.
Otherwise, reject the string if any of the tests fail.”
4. Random Access Turing Machines
It is used to speak about small complexity classes.
A straightforward computational model is a random access machine (RAM). Its memory contains of an unbounded sequence of registers. A single integer value may be stored in each register. An organised list of statements, is stored in the control unit of a RAM. The next statement to be executed is determined by the program counter.
A random access Turing machine has:
• a registers of fixed number
• a program of finite length, operators such as read, write, load, store, add, sub, jump composing instructions
• a tape
• a program counter
Theorem: Random access and traditional Turing computers Computing is equivalent on Turing machines. Additionally,a polynomial in the number of steps required by a random access machine limits the number of steps required by a conventional machine.
5. Nondeterministic Machine
A non-deterministic Turing machine has a single infinite one-way tape.
For a given state and input symbol, each choice has several options for the path that it might take for a given input string (finite number of choices for the next move).
A non-deterministic Turing machine is the deterministic Turing machine's equivalent.
In a Non-Deterministic Turing Machine, the TM can perform a set of actions for each state and symbol. As a result, the transitions are not deterministic in this case. A non-deterministic Turing Machine computation is a tree of configurations that can be reached from the start configuration.
If there is at least one node in the tree that is an accept configuration, the input is accepted; otherwise, it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is referred to as a Decider, and if all branches are rejected for some input, the input is also rejected.
A non-deterministic Turing machine can be formally defined as a 6-tuple (Q, X, ∑, δ, q0, B, F) where −
- Q is a finite set of states.
- X is the tape alphabet
- ∑ is the input alphabet
- δ is a transition function;
- δ : Q × X → P(Q × X × {Left_shift, Right_shift}).
- q0 is the initial state
- B is the blank symbol
- F is the set of final states
Conclusion
There are several ways to possibly increase the computational capability of a typical Turing machine through extensions of the TM model. In every case, the objective is to demonstrate that these expansions don't offer any more computational power because a conventional Turing machine can successfully replicate their behaviour.
A typical 1-tape Turing computer is capable of computing anything that can be done algorithmically.
For two machines the host and the guest, the Setup is where the guest machine configuration is converted into a suitable host machine configuration. Other steps include Step by step simulation where each step taken by the guest machine affects the host machine, and the other being the Tear Down phase where the guest machine enters a halt state while the host machine reaches a pre-halt state and begins the tear down phase leaving a terminal configuration on host which mirrors itself on the guest.
The host machine's state set is something like this:
K ∪ K×{0,1,2,...}
The most effective method for "expanding" TM capabilities is the multiple tape paradigm. Of course, we're simply making it a lot simpler to compute, not extending it.
Since the calculation begins and finishes on tape 1, a multi-tape TM computes the function f: Σ0* → Σ0*.
A two-way infinite tape may go left or right in any direction since it has no left end. We'll explain how a 2-tape Turing Machine may emulate such a Turing Machine. We are basically replicating the 2-way Turing Machine by a standard Turing Machine because a normal Turing Machine may imitate a 2-tape Turing Machine.
In a k-head TM, there are k indicated places (which can be the same position). A move entails reading each position and doing individual actions at each point. When two or more heads indicate the same stance, disagreements must be resolved in some way. It is simple to understand how a k-tapeTM with identical contents on each tape might replicate this.
A two-way infinite tape may go left or right in any direction since it has no left end. We'll explain how a 2-tape TM may emulate such a TM. We are basically replicating the 2-way TM by a standard TM because a normal TM may imitate a 2-tape TM.
A state and marked string are again a configuration for this machine, with the marked string having a limited amount of blanks on either end. Thus
...###a####... should be denoted by a simple #, not a ##, #a, etc.
A multi head turing machine is a single tape turing machine that has "n" number of heads reading the symbols on the tape concurrently. Following the simultaneous detection of the scanned symbols, each head independently moves and writes.
A random access computer is a simple computational paradigm (RAM). Its memory is made up of an infinite series of registers. Each register may hold a single integer value. The control section of a RAM stores an organised collection of statements. The programme counter decides which statement will be performed next.
These were the different types of extensions that could be used with turing Machines in order to increase their performance and further get results with efficiency and accuracy.
References
https://www.cs.wcupa.edu/rkline/fcs/tm-extensions.html
https://plato.stanford.edu/entries/turing-machine/
https://cs.uwaterloo.ca/~watrous/ToC-notes/ToC-notes.13.pdf
Comments
Post a Comment