|
|
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
|
|