All we have to do is to 'mark off' more regions of the TMs tape to represent the PDA's n stacks and simulate the PDA's instructions accordingly.
Thus every nPDA may be simulated by a TM, so no increase in power is obtainable.
Back
to Topic 7
The pushdown automata that we studied in
topic 6 had only one stack and could recognise all, and only, the context-free
languages.
Would the addition of a second stack to a PDA alter its power?
The instruction set of such a machine (a 2PDA) would comprise START,
HALT ACCEPT and READ, as before, together with separate instructions (say, PUSH1,
PUSH2, POP1 and POP2) for operating on its different stacks.
Can we show that there exists a non-context-free language that is recognisable
by some 2PDA?
Consider the language anbnan,
which we have already proved to be non-context free.
A 2PDA could recognise this language by performing the following algorithm:
There is a constructive algorithm
that converts any 2PDA to a TM that recognises the same language.
This simply divides the TM's tape into three regions, separated by some distinguished
symbol, say #, where the first region represents the PDA's input tape,
the second as its first stack and the third as its second stack.
Use this algorithm to convert into TMs the 2PDAs you designed in the previous exrecise.
It is also the case that
every TM may be simulated by a 2PDA,
The proof of this theorem relies on the
use of the 2PDA's two stack to represent those parts of the TM's tape that lie
on each side of its read head.
As the TM's head moves along, reading and writing symbols to its tape, the 2PDA
simulates it by moving corresponding symbols from one stack to the other.
The two theorems together assert that
TM = 2PDA
Clearly, adding a second stack to a PDA
considerably increases its power.
So we might expect that adding a third stack, or a fourth, fifth, etc., would
generate even more powerful classes of machine.
But this is not the case. In fact:
2PDA = 3PDA = 4PDA = ... = nPDA = TM
You may be able to see this intuitively
by extending the constructive algorithm developed for the 2PDA case.
All we have to do is to 'mark off' more regions of the TMs tape to represent
the PDA's n stacks and simulate the PDA's instructions accordingly.
Thus every nPDA may be simulated by a TM, so no increase in power is
obtainable.
Back
to Topic 7
We have just seen that extending
the PDA can increase its power.
We will now consider what can happen if we restrict the TM.
We consider the Read-Only TM, that can read form, but cannot write to,
its tape.
This simply means that, in every arc label, the read and write
fields are identical.
Clearly, such a TM cannot produce any output,
and therefore cannot compute any function on its input string.
But it can still recognise languages by coming to a HALT on those strings that
it accepts and crashing or looping on the others.
The Read-Only TM may therefore be considered as a FSA that has the additional
property of being able to move its head in both directions.
It is, in other words, a Two-Way FSA.
The question this time is,
what class of languages can these machines recognise?
Does the restriction to the TM decrease its power, or does the enhancement to the FSA increase its power, or both?
The answer is provided by showing, using a sequence of steps similar to those in Kleene's Theorem, that
any Read-Only TM can be converted to a regular expression.
The proof is not quite as constructive as the ones we have already seen, because it relies on a non-constructive step in which suitable regular expressions must be 'found'. But it does demonstrate that:
The Read-Only TM accepts only the regular languages.
Adding stacks to a PDA increases power.
What about adding tracks to a TM?
A k-track TM (or kTM) has
k TAPES and one tape head that reads all of them simultaneously.
Of course, its instruction set must be appropriately modified so that each transition
is labelled by a tuple that defines the symbols to be read from, and the (possibly
different) symbols to be written to, each of the k tapes.
Here is snapshot a 4-track TM at some point
in its execution, with the position of the read head marked by the coloured
square:
| TAPE 1 | a | b | b | a | a | ... |
| TAPE 2 | /\ | /\ | /\ | /\ | /\ | ... |
| TAPE 3 | b | /\ | /\ | a | /\ | ... |
| TAPE 4 | b | b | a | b | b | ... |
The kTM relates easily to traditional manual operations, such as the addition of columns of numbers, where the calculation procedes from right to left dealing with one column of digits at a time.
Can we simulate any kTM on a TM?
The clue to doing this is to see that each column of cells on the tape consists
of a 4-tuple of symbols.
It is straightforward to encode each of the possible values of this tuple
as a single symbol in some extended alphabet.
For example, if the original TM's alphabet had two symbols, say a and
b, and the blank tape indicator, /\, then each column could have one
of 8 (=23) values, so we define the alphabet for a new single track
TM that consists of 7 symbols plus, of course, the blank tape indicator.
If the kTM's program is encoded using this alphabet, the result will be an equivalent
TM.
We conclude that
TM = kTM
This encoding is tedious. There is little
to be gained by working it through on an example.
The important issue is not to be discovered by doing it, but by understanding
that, and how, it can be done.
Try reconstructing this argument by yourself, without looking at the notes.
Our TM model has a one-way-infinite tape; that is, the tape has an end, at the left, beyond which the machine may not go without crashing, but it is unbounded to the right, because even if though input string is finite, the machine may write indefinitely to the right hand end of tape.
Would there be any increase in power if we allowed the tape to be infinite to the left as well?
Again, the proof that this is not the case is in the form of constructive algorithms that show how to simulate any two-way infinite tape TM on some one-way infinite TM and vice versa.
Again, we conclude that
Two-Way Infinite TM = TM
The multi-TAPE TM differs from the kTM
in that it can has a separate tape head for each of its multiple tapes.
On each move, such a machine can
Intially, the input string appears on the
first tape and all the others are blank.
Once again, the proof of equivalence relies on the algorithmic construction
of a simulator on a kTM, which is then converted to a TM.
Each tape of the multi-TAPE TM (say, M1) is represented by two tapes
in the simulating kTM (M2), one of which replicates the tape contents and the
other being blank except for a marker that holds the symbol scanned by the corresponding
tape head of M1.
M2 stores the state of M1 together with a count of the number of head markers
currently to the right of M2's tape head.
| Head1 | X | |||||
| Tape1 | a1 | a2 | ... | ... | ... | am |
| Head2 | X | |||||
| Tape2 | b1 | b2 | ... | ... | ... | b1 |
| Head3 | X | |||||
| Tape3 | c1 | c2 | ... | ... | ... | c3 |
Each move of M1 is simulated by a sweep
from left ot right and then from right to left by the tape head of M2.
Initially, M2's head is at the leftmost cell containing a head marker.
To simulate a single move of M1, M2 sweeps right visiting each of the cells
with head markers, recording the symbol scanned by each head of M1, and updating
its count of head markers to its right.
After it has exhausted its head marker count, M2 has enough information to determine
M1's move.
Now M2 makes a pass left, counting head markers until it reaches the leftmost
one, and updating the tape at, and position of, each head marker as it passes
it.
Finally, M2 changes its record of M1's state. If this is an ACCEPT state, then
M2 accepts.
Back
to Topic 7
A non-determinsitic TM, or NTM,
has a single, one-way infinite tape, and, for a given state and input symbol,
has a finite number of choices for the next move, each choice consisting of
a new state, a symbol to write and a direction of head motion.
Like the NFSA and the NPDA, it may have several choices of path that it might
follow for a given input string.
An input string is accepted by a NTM if any such path leads to a HALT
state, even if some choices of path LOOP or CRASH.
Note that non-determinism adds no power
to the FSA class, but does add power to the PDA class.
The obvious question is whether:
NTM = TM?
Obviously, a NTM can do anything a TM can
do simply by not expliting its non-determinism.
But does the converse hold?
As before, we seek a constructive algorithm to convert any NTM to a TM that
accepts the same language.
This time, we generate a 3-tape TM (3TM), M2, that accepts the same language as any NTM, M1.
For any state and symbol of M1, there is
a finite number of choices for the next move.
These can be numbered 1, 2, 3, ...
Let r be the maximum number of choices for any state symbol pair in M1.
Then any finite sequence of choices can be represented by a sequence of the
digits 1, 2, ..., r.
Not all such sequences may represent choices of moves, since there may be fewer
than r choices in some situations.
M2 will have three tapes
If M1 enters a HALT state, then M2 HALTs.
If there is a sequence of choices that leads M1 to accept the input string,
then that sequence will eventually be generated by M2 on tape 2 and will lead
M2 to accept the string also.
But if there is no such sequence of moves, then M2 will not accept the input
string.
Back
to Topic 7
So far, we have considered only the power
of the machines we have been investigating, in terms of their ability to recognise
languages at all.
The relative efficiency of different machines recognising the same
language has not been an issue.
Note, however, that the simulation of a
two-way infinite tape TM by aone way infifnite tape TM was move-for-move,
whereas, in this simulation, many moves of M2 are need to simulate one move
of M1.
In fact, to simulate k moves of M2 requires about 2k2 moves
of M1.
This quadratic slowdown that occurs when we simulate a multitape TM on
a single tape TM is inherently necessary for certain languages.
The language EvenPalindrome = {ww-1
| w in (0+1)*} can be recognised on a one-tape TM by moving its head
up and down the tape, comparing symbols from both ends.
The number of moves that this machine takes to accept any word of the language
is approximately the square of the word length
To recognise this language on a two-tape TM, the input is copied to the second
tape and compared with its own reversal by moving the tape heads in opposite
directions (and checking that the length of the input is even).
For this machine, the number of moves to accept a word is proportional to the
word length.
Note that we have considered no aspect
of their construction other than their architecture.
This difference in efficiency is therefore not attributable to any 'technological'
factor, such as clock speed, that might differentiate the performace of real
machines.
In any cae, such technological factors usually contribute a scalar factor
to performance.
Here, the efficiency difference varies as the square of the input length.
So, for word of, say, 5 symbols, one machine will take 25 times
as many moves as the other.
For words 100 symbols long, the performance difference will be a factor
of 10000.
Clearly, this degree of difference in efficiency rapidly outstrips the influence
of any conceivable technological device.
If we make a multitape TM's input tape
read-only, we obviously get no difference in power.
Such an off-line TM can simulate any other TM simply by using
one more tape onto which it copies the input string and then continues with
that tape as its input.
The need for the off-line TM will become apparent in the next section, when we consider
computational complexity: the study of the relative efficiency of different classes of machine, and of bounds on the achievable efficiency of recognisers for different languages.
If you have comments or
suggestions, email to author at b.cohen@city.ac.uk
or me Vid-Com-Ram
/ members.tripod.com/bummerang
หมายเหตุ : เอกสารเวปหน้านี้นำมาจากมหาวิทยาลัยแห่งหนึ่งในประเทศอังกฤษ
เป็นหลักสูตรคล้ายคลึงกับ CT313 นำมาเพื่อเป็นเอกสารเปรียบเทียบและอ้างอิง มิได้หวังผลประโยชน์ใดๆ
และขอบอกว่าเค้ามีลิขสิทธิ์นะ
Next
Topic
Start
of Module