Note the inverse function, code-1, from CWL to TM, is not total; that is, not every word w in CWL is the code for a TM.
Back
to Topic 10
Beyond the limits of computability lie
languages that cannot be recognised by any TM.
But could we prove that there is any such language?
Suppose we believe that some language,
L, has that property.
Our proof would have to address the entire space of TMs and demonstrate conclusively
that nowhere in that space was there a TM that recognises L.
In order to do this, we must have a way of referring to the entire collection
of TMs.
The way this is done is to define a formal language in which TM
may be described by a word in the language.
In other words, we need to find a way of encoding TMs.
We have already seen a tabular presentation of TMs in five columns:
From State, To State, Read, Write, and Move Head
A row in such a table that reads:
6, 2, b, a, L
means
'from State 6, if a b is read, write an a, move the tape head to the left and go to State 2'
We are looking for a code in which each
such row of the tabular presentation of any TM might be represented as a string
in a small alphabet, say {a,b}.
Many such encodings are possible.
We will use the following one:
We also need a way of indicating which
states are the start state and HALT state.
Conventionally, and with no loss of generality, we will take State 1 to be the
start state of every TM and State 2 to be its HALT state.
The row
6, 2, b, a, L
would be coded as
aaaaaab aab ab aa a
Spaces have been placed betwen the groups of symbols here for ease of interpretation only; they are not part of the code.
The successive rows of the table representing
a TM would be coded this way and the codes of the rows concatenated to provide
a string that is the code word for the entire TM.
Note that the rows of such a table may be rearranged in any order without changing
the TM that it represents, but that each rearrangement will generate a different
code word.
On the other hand, each code word can be decoded into its corresponding TM,
if there is one, in only one way.
We will refer to the set of such strings
as the Code Word Language (CWL) and we will refer to the code word in
that language for a TM, T, as code(T).
Note the inverse function, code-1, from CWL to TM, is not total;
that is, not every word w in CWL is the code for a TM.
Back
to Topic 10
The code-words in CWL are strings that
could be input to Turing Machines.
This means that it is potentially possible to have a TM that takes descriptions
of TMs as input.
Now, if we feed such a TM with its own code-word, it might either accept it, or reject it, or loop forever.
Let us now define a special language, ALAN, that consists of each word in CWL that either
is not accepted by the TM that it represents, or
does not represent a TM at all.
Formally:
Note that ALAN is a well-defined
language.
Every word in it satisfies a condition that is readily checkable.
So, given any string, we can tell whether or not it is in ALAN.
Consider the following trivial TM
It is represented by the one line table:
1, 2, b, b, R
The code word for this machine is:
ab aab ab ab b
If we input this word to the TM that it
code for, then the TM will crash in State 1 when trying to read the first
symbol of the string, since there is no edge for the letter a leaving
state 1.
Therefore the string abaabababb is a word in ALAN.
A string such as bbbb is clearly not a representation of a TM at all, and hence this is also a word in ALAN.
Note that
because its own code word is among the words it accepts.
because its own code word is among the words it rejects.
Consider the code word
w = ab aaab aa aa b aaab aaab aa aa
b aaab aab ab ab a
We are now ready to tackle the question that we asked at the start of this topic:
Can we prove that there exists a language that is not recognisable by any TM?
There does not exist a TM that can recognise
ALAN.
Or, more formally, ALAN is not recursively enumerable.
The proof will be by reductioad absurdum, where we assume the opposite of what we are trying to prove and try to show that that hypothesis leads to a contradiction.
So we start with the following
Then, by the definition of the recursively
enumerable languages, there must be at least one TM, which we will call X, that
recognises ALAN.
That is, X ACCEPTs all the words in ALAN
Now, the string code(X) is either in
ALAN or it is not in ALAN.
We consider each possibility in turn, numbering the steps in the proof and justifying
each step:
CASE 1: Hypothesis 2: code(X) is in ALAN.
CASE 2: Hypothesis 3: code(X) is not in ALAN.
Both hypotheses 2 and 3 have to be rejected
as each leads to a contradiction.
But since they are mutually exclusive, they cannot both be false.
This contradiction forces us to withdraw the last hypothesis before the contradiction,
which is now hypothesis 1,
We must conclude that ALAN is not recursively enumerable!
So there does exist at least one language that no TM can recognise.
QED
Back
to Topic 10
A closely related question, and a more significant one for computation, is:
Given any string and any TM, is there a procedure for deciding whether that TM will HALT when presented with that string?
Note that we don't care whether the string
is ACCEPTed or REJECTed by the TM.
All we want to know is whether the TM will LOOP forever or will eventually HALT.
In more familiar computing terms, this
question, which is called the Halting Problem, asks if it is possible
to write a program that can decide whether any other program will ever fail
to terminate.
That property is obviously important and seems, at first sight, to be readily
determinable.
We have claimed that TMs can compute anything that is computable.
So if there is a decision procedure for the Halting Problem, we would expect
there to be a TM that could execute it.
We can, however, prove that there can be no such TM.
The Halting Problem cannot be decided
by a TM.
Or, formally:
There is no TM that can input any string w and the code for any TM T
and always decide correctly whether T halts on w.
Consider a TM, called Halting Problem Acceptor
(HPA).
HPA takes as input a string (T, DT) that consists of:
the code word for some TM, T, concatenated with
a string, DT, that might be input to T
and behaves as follows:
Now modify HPA so that, whenever it is
about to reach its accept state, it goes instead into an infinite loop, which
is easy to arrange, but it still rejects as before.
This modified TM, which we will call HPL, behaves as follows:
Now modify HPL slightly so that its input
strings are the codes for TMs that input their own codes.
This modified HPL requires only the code for a TM, T, on its input
tape, as the string to be input to T is merely a copy of its own code
word.
The behaviour we require is now that:
What happens if we give HPL itself
as input?
Its required behaviour may be derived by substituting HPL for T, which
gives:
Since this is clearly a contradiction,
HPL cannot exist.
But HPL was derived from HPA, the TM whose existence we assumed at the beginning.
So HPA cannot exist either.
There is, therefore, no TM that can decide the Halting Problem.
QED
Shocking though this conclusion may be, the same proof technique can also be used to show that:
That is, even the emptiness property for r.e. languages is undecidable by
TMs.
Consider the language
that contains every word that is accepted by the TM that it codes for.
Is TURING recursively enumerable?
What functions cannot be computed by a
Turing Machine?
To approach this question, we must turn our attention away from the machines
that compute and towards what has to be computed.
In particular, we will focus on functions from numbers to numbers.
Consider the function
f(m,n) = mn2 + 3m2m + 17
To compute the value of this function for
any given values of m and n, we must compose the results of applyiing
simpler functions -- addition, multiplication, exponentuation -- on the same
arguments.
These, in turn, are recursively defined in terms of simpler functions.
Thus, for example, mn= 1 if n = 0 and mmn-1
otherwise.
And multiplication can similarly be defined recursively in terms of addition.
If we can start with functions on the natural numbers that are so simple that
we can show how to compute them with TMs, then by applying recursive constructions,
we should be able to generate a whole class of non-trivial functions that are
known to be computable.
This notion of computability will then be identical to those we have developed
in this module.
Start with the following basic functions of type: NATk -> NAT, where k *0:
We refer to functions that take n arguments as n-ary functions.
Next, introduce ways of combing functions to get slightly more complex ones:
Given a k-ary function g and k m-ary functions h1, h2, ...hk,with k,m * 0,
the composition, f, of g with h1, h2, ...hk is defined as:
f(n1, n2, ...nm ) = g(h1(n1, n2, ...nm ), h2(n1, n2, ...nm ), ...,hk(n1, n2, ...nm )).
Clearly, if g and all the hk are computable (by some machine), then so is their composition, which just requires each of the hk to operate in turn on (a copy of) the input, n1, n2, ...nm ), leaving their results in sequence for g.
Given a k-ary function g and a (k+2)-ary function h,
the (k+1)-ary function, f, defined recursively by g and h is defined as:
f(n1, n2, ...nk, 0) = g(n1, n2, ...nk)
f(n1, n2, ...nk, m+1) = h(n1, n2, ...nk, m, f(n1, n2, ...nk, m))
for all n1, n2, ...nk, m in NAT.
Again, if g and h are computable on some machine, then so is f, because it can compute f(n1, n2, ...nk, m+1) as follows:
r1 = g(n1, n2, ...nk)
r2 = h(n1, n2, ...nk, 1, r1)
r3 = h(n1, n2, ...nk, 2, r2)
and so on, until
rm+1 = h(n1, n2, ...nk, m, rm)
The primitive recursive (PR) functions are all the basic function together with all functions that can be obtained from them by any number of successive applications of composition and recursion.
Every PR function can be defined in terms
of the basic functions, and can therefore be represented as a string in a finite
alphabet.
This alphabet should contain symbols for the identity, successor and zero functions,
symbols for recursion and composition, parentheses, and 0 and 1 for indexing
purposes.
We could then enumerate all the strings in this alphabet, keeping only those
that are definitions of PR functions.
Without loss of generality, we could even cut this list down to representations
of the unary PR functions (those with a single argument).
We could arrange this list in some lexicographic order, according to
some arbitrary ordering on the alphabet.
In principle, given any integer n we could find the nth unary
PR function in this list, fn, and use its definition to compute
the number fn(n)+1.
Call this number g(n).
Clearly, g is a computable function -- we have just shown how to compute
it.
But it is NOT a primitive recursive function!
If it were, then it would appear in our list, let's say at position m,
for some m*0.
But then we would have:
g = fm
therefore
g(m) = fm(m), since the function are equal
but
g(m) = fm(m)+1, by definition of g
so
fm(m) = fm(m)+1, which is absurd.
We must therefore conclude that g
is not in our list of PR functions, and is therefore not PR.
This is a diagonalisation argument for the existence of non-computable
functions.
It is believed that every function whose
calculation can be described by any well-defined algorithm that people can be
taught to perform, can be computed by some TM (i.e. is primitive recursive).
And vice versa, that anytthing that cannot be computed by some TM cannot be
computed at all.
This statement is called the Church-Turing Thesis
(not their ÔtheoremÕ because it cannot be formally proven Ñ
there are no axioms that deal with people).
Thus the TM is believed to be the ultimate
calculating machine (at least in terms of what it can do, not how it does it).
So the fact that there exist functions not computable by any TM demonstrates
that not everything is computable.
That is, that there are limts to what computers can, or will ever be able to,
do.
We have seen Turing's model of computation
and his conception of what an algorithm is.
Alonzo Church developed a different model called lambda calculus.
Kurt Gödel and Stephen Kleene produced their own version
called m-recursive functions.
Other models of computation have been developed, including Markov Algorithms
and H.E. SturgisÕ Register Machine.
These models are demonstrably equivalent, in that all can be shown to
have the same computational limits as the Turing Machine.
The forms of argument used in these models, such as diagonalisation and other
proofs by contradiciion, have also been applied at the very foundations of mathematics
itrself.
Much of Alan Turing's work took place in
the background of an agenda that had already been set by the mathematician David
Hilbert.
When Hilbert saw problems arising in Set Theory, he proposed that the following
statements should be proven:
The mathematician G. H. Hardy believed
that if statement 3 were true, then Mathematics as a subject for research would
come to an end.
In 1930, Kurt Gödel proved that statements 1 and 2 cannot both be
true.
Then in 1936, Alonzo Church, Stephen Kleene, Emil Post
and Alan Turing showed that statement 3 is false.
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 นำมาเพื่อเป็นเอกสารเปรียบเทียบและอ้างอิง มิได้หวังผลประโยชน์ใดๆ
และขอบอกว่าเค้ามีลิขสิทธิ์นะ
Start
of Module