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 proved that the
acceptance problem for Turing machines is undecidable. Today we will
show how we can prove that other problems are undecidable as well by
applying a technique called reduction. This technique works as
follows: we prove that if the new problem, call it P, were
decidable then the acceptance problem, or some other problem we
already know to be undecidable, would be decidable too. This is a
contradiction that allows us to conclude that the problem P is
undecidable.
We shall use this technique to prove that it is undecidable whether
a Turing machine halts on an input,
a Turing machine accepts the empty language, and
two Turing machines accept the same language.
Time and Location
Friday, 8 October, 2004 at 10:15 in A4-106.
Reading Material
Material in pages 171-176 and Section 5.3 of Sipser's book.
Exercises
Finish any starred exercise you have left over from our previous
meetings.
Prove, making use of reductions, that it is undecidable
whether a Turing Machine
accepts the empty string,
accepts every string,
accepts a finite language
Work out problems 4.17(*) and exercises 5.4-5.7 in
Sipser's book.