4.5.2 Impli ca tions of Halting Prob lem
(a) Pro gramming
The Theorem of “Halting Problem” does not say that we can never determine
whether or not a given program halts on a given input.
Most of the times, for practical reasons, we could eliminate infinite loops
from programs. Sometimes a “meta-program” is used to check another
program for potential infinite loops, and get this meta-program to work most of
the time.
The theorem says that we cannot ever write such a meta-program and have
it work all of the time. This result is also used to demonstrate that certain other
programs are also impossible.
The basic outline is as follows:
(i) If we could solve a problem X, we could solve the Halting problem
(ii) We cannot solve the Halting Problem
(iii) Therefore, we cannot solve problem X.
(b) Arti fi cial Intel li gence (AI)
It has been tried to use the Halting Problem as an argument against the
possibility of intelligent computers. The argument is as follows:
(i) There are things computer cannot do
(ii) We can do those things
(iii) Therefore, we must be superior to computers.
The first premise given above is definitely TRUE. The second premise is
generally supported by displaying a program which solves some subset of the
Halting Problem, then describing a nice trick which is not incorporated into the
program, that solves a slightly larger subset. There may well be valid
arguments against the possibility of AI. This is not one of them.
4.5.3 Reduc tion to Halting Prob lem
In order to reduce a problem P to the Halting problem, look at the following
steps:
(i) Assume that you have an effective procedure—either a Turing
machine or any kind of algorithm to solve problem P.
(ii) Show how to use the program for P to solve the Halting problem.
(iii) Conclude that problem P cannot be solved.
State Entry Prob lem
This problem otherwise called “dead code problem” is to determine whether
Turing machine M, when given input w, ever enters state q. The only way a
Turing Machines
201
(a) Pro gramming
The Theorem of “Halting Problem” does not say that we can never determine
whether or not a given program halts on a given input.
Most of the times, for practical reasons, we could eliminate infinite loops
from programs. Sometimes a “meta-program” is used to check another
program for potential infinite loops, and get this meta-program to work most of
the time.
The theorem says that we cannot ever write such a meta-program and have
it work all of the time. This result is also used to demonstrate that certain other
programs are also impossible.
The basic outline is as follows:
(i) If we could solve a problem X, we could solve the Halting problem
(ii) We cannot solve the Halting Problem
(iii) Therefore, we cannot solve problem X.
(b) Arti fi cial Intel li gence (AI)
It has been tried to use the Halting Problem as an argument against the
possibility of intelligent computers. The argument is as follows:
(i) There are things computer cannot do
(ii) We can do those things
(iii) Therefore, we must be superior to computers.
The first premise given above is definitely TRUE. The second premise is
generally supported by displaying a program which solves some subset of the
Halting Problem, then describing a nice trick which is not incorporated into the
program, that solves a slightly larger subset. There may well be valid
arguments against the possibility of AI. This is not one of them.
4.5.3 Reduc tion to Halting Prob lem
In order to reduce a problem P to the Halting problem, look at the following
steps:
(i) Assume that you have an effective procedure—either a Turing
machine or any kind of algorithm to solve problem P.
(ii) Show how to use the program for P to solve the Halting problem.
(iii) Conclude that problem P cannot be solved.
State Entry Prob lem
This problem otherwise called “dead code problem” is to determine whether
Turing machine M, when given input w, ever enters state q. The only way a
Turing Machines
201