Re: Halting Problem for Humans


"Daryl McCullough" <stevendaryl3016@xxxxxxxxx> wrote in message
news:ehih0k0hj5@xxxxxxxxxxxxxxxxxx
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.

Since there is a scenario where this could be construed to make sense, this
statement is incorrect.

Within the specific context of TM's it may make less sense, yet probably still
some sense. The TM could enter a state where it secretly knows the answer, yet
this answer depends upon knowing the purely arbitrary encoding of these results.
The TM could halt on one of many possible integer values that vary for each
unique input, the value indicates halting or not halting, yet, only the TM knows
which is which.

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.

I agree with this completely.


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.

So in order for H to avoid making a mistake its only possible choice is to
refrain from entering either of these two states. So the only possible correct
choice would still be to refrain from answering the question, thus showing that
the question of halting is ill-formed, according to the definition of ill-formed
questions.

Since there exists no correct answer within the solution set. In this case the
solution set is narrowly defined not as the question "Does the program Halt,
(YES or NO)? (because refraining from answering the question causes the program
to halt), but "Does the program Halt {l(L,L) or h(L,L)}?" This is still an
ill-formed question according to the definition of ill-formed questions.


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: On The Proper Formulation Of The Halting Problem
    ... >> formulation of the Halting Problem is more or less along ... >> will halt, wwill loop, and vice versa. ...
    (sci.logic)
  • 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 ... whose source code is p will halt on input x, ... Lquits the simulation and halts. ...
    (sci.logic)
  • Re: PROOF that numbers are countable
    ... you're the one claiming such an enumeration of halting ... > halt, feel free. ... > If it is as powerful as TMs, then there are constructs that do not halt. ... > claim applies to your special selection, ...
    (comp.theory)
  • Re: before Cantor there was Rantor
    ... >>halting proof is contradiiction of the existence of a particular defined ... halt function is a SPECIFIC function. ... I did disprove the Halting Proof. ... in that time then it outputs TRUE, otherwise it timed out and outputs DONTKNOW. ...
    (sci.math)
  • Re: before Cantor there was Rantor
    ... >>halting proof is contradiiction of the existence of a particular defined ... halt function is a SPECIFIC function. ... I did disprove the Halting Proof. ... in that time then it outputs TRUE, otherwise it timed out and outputs DONTKNOW. ...
    (sci.logic)
Quantcast