Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Formal Languages and Computability
In our previous lecture, we introduced the
Turing machine model of algorithms, and hinted at the fact that it is
a universal model of computation. In particular, we stated the
Church-Turing thesis that equates the intuitive notion of algorithm
with the formal notion of "algorithm that can be expressed as a
Turing machine". Our first aim in this lecture will be to offer some
justification for this thesis by showing that some natural variations
on the model of Turing machines---e.g., Turing machines with multiple
tapes, and nondeterministic Turing machines---, accept precisely the same
languages as standard Turing machines.
Having gained some evidence for the Church-Turing thesis, we shall
present our first example of an algorithmically unsolvable problem,
namely the acceptance problem for Turing machines.
Time and Location
Monday, 4 October, 2004 at 10:15 in A4-106.
Reading Material
Sections 3.2, 3.3 and pp. 159-168 of Sipser's book.
Pages 191-215 of D. Harel's book Algorithmics: The Spirit of
Computing. (Optional, but strongly recommended as an
introductory, and above all enjoyable and stimulating, further
reading. These pages will be available for photocopying from the
course folder in due course. Be patient!)
Exercises
Finish any starred exercise you have left over from our previous
meetings.
Exercise 3.3, 3.6(*), 3.13, 3.16(*) and 3.19.
Assume that A is a decidable language and that B is
included in A. Is B also guaranteed to be decidable?
Argue for your answer.
[For the keenest, but I strongly recommend that you try
this one!] In our previous lecture, I told you that the
possibility of writing programs that may loop forever on some inputs
is a vital feature in programming languages, or indeed any general
model of algorithms. In fact, I claimed that no formalism that can
only describe algorithms that always terminate is powerful enough to
express all such algorithms. This exercise is intended to convince
you that this, apparently paradoxical, claim does hold water.
Assume that we have a programming language L, and that
each program P in L computes a function
fP: N --> {0,1}.
We assume that programs in L are written using symbols
from some finite alphabet Sigma, and that there is a syntax checker for
L---that is, that there is an algorithm
C:
Sigma* ----> {0,1}
such that C(w) =1 iff w is a
legal program in L. Prove that there is a computable
function
f: N --> {0,1}
that is computed by no program in
L. [Hint: Assume that the programs in L are ordered
lexicographically thus P1, P2,
P3......, and that each program Pi computes
the function fi. Can you construct a function f that is
different from each of the fi's for at least one input?
Next argue that f is computable by giving an algorithm for it.]