Theorem 9.2.3: the halting problem is undecidable for Turing machines.
The Halting Problem for Turing machines: given a Turing machine T, and an input w__* for T, does T halt when started on w?
The algorithm test for Turing machines: given a Turing machine T, does T halt for every input w__*?
Theorem 9.2.4: the algorithm test is undecidable.
Previous slide | Next slide | Back to first slide | View graphic version |