Re: Halting Problem for Humans

Peter Olcott says...

"Daryl McCullough" <stevendaryl3016@xxxxxxxxx> wrote

This is exactly and precisely one aspect of the line-of-reasoning
that I have provided showing that there are some issues with
calling at least some of the variations of the Halting Problem
un-decidable. Daryl can decide the answer, yet, Daryl can not
provide the answer.

But the halting problem can be phrase in a way to eliminate
this possibility.

Give it a shot, try and show this.

First of all, for a computer program it doesn't make any
sense to say that the program knows something but can't
say it. The only sense in which a computer program can
be said to "know" some piece of information is if has
entered into a particular state associated with that
piece of information.

So let H(p,x) be any program that takes two string arguments,
p (a source code for a program of one string argument) and x
(an input to p). If you claim that H can "know" that the program
whose source code is p will halt on input x, then there must be
some point in the execution of H(p,x) where H enters into the
"knowing" state. Let's call the state in which H knows that
p will halt on input x, h(p,x), and call the state in which
H knows that p will not halt on input x, l(p,x).

Now, we construct a second program, L(p), with one string
input p. L(p) behaves as follows:

L(p) simulates the execution of H(p,p).

1. If H ever enters the state l(p,p), then
L(p) quits the simulation and halts.
2. If H ever enters the state h(p,p), then
L(p) enters into an infinite loop.
3. If H ever halts without having entered
state l(p,p), then L(p) enters into an
infinite loop.
4. The simulation of H will continue until
the simulation halts, or until H enters the
state l(p,p).

Now, consider the execution of H(L,L).
If H ever figures out that L(L) will not halt,
then it must enter into the state l(L,L).
But if H ever enters into that state, then
the simulation of H by L will enter that state.
But if the simulation enters the state l(L,L),
then L will halt. So H is wrong.

It doesn't work to say that H knows something
but it can't show it. To know something *means*
to enter a particular state, and if H enters
that state, then that fact will be detectable.

The alternative is to say that the program's
mind can know something that isn't reflected
in the program's state. That's a pretty mystical
notion, don't you agree?

--
Daryl McCullough
Ithaca, NY

.

Relevant Pages

  • Re: Halting Problem for Humans
    ... calling at least some of the variations of the Halting Problem ... Daryl can decide the answer, yet, Daryl can not ... The TM could halt on one of many possible integer values that vary for each ... Lquits the simulation and halts. ...
    (sci.logic)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (comp.theory)
  • Re: Halting Problem Final Conclusion
    ... > was to detect programs that failed to halt, ... The primary benefit of a universal Halting Problem ... about programs that fail to halt. ... if this program would halt" analyzer may be as ...
    (sci.logic)
  • Re: The formal and informal proofs
    ... I am paid to formalize all day. ... > HALT(x,y) = List the TMs that halt. ... > possible, you have a formalization of the Halting Problem, the Every ...
    (sci.logic)
  • Re: A modern view of the halting problem
    ... program will halt. ... design of the language? ... The halting problem is not about stopping at specific instructions; ... using Riemann Hypothesis instead. ...
    (alt.lang.asm)