Would Professor Sipser agree that you have refuted his halting problem
proof?
If I understand this correctly, it does not support the idea that a
general "simulating halt decider" can actually exist.
In the above, let D be a program that may or may not halt, and let H be
an observer who attempts to determine whether or not D halts.
Concretely, let D be this C program or equivalent:
int main(void) { while (1) { } }
and I'll be H. I can observe D. I can simulate it until I get bored,
which won't take long (one iteration, two iterations, three iterations,
zzzzzzzzz). I can, while simulating it, conclude that it will never
halt, abort the simulation, and report that it never halts. It wouldn't
be difficult to automate the process in a way that works for this simple
case.
In other words, a halt decider that works correctly for *some* programs
is entirely possible. Nobody disputes that, and the statement that you
report Dr. Sipser made is consistent with that.
What is impossible is a *general* halt decider that can report the halt
status for *any* program.
For example, it would be easy to write a program (assuming unbounded
memory resources) that halts if and only if Goldbach's conjecture is
false. If a general halt decider (simulating or not) existed, it could
be applied to such a program and solve Goldbach's conjecture.
(Goldbach's conjecture is that every even number greater than 2 is the
sum of 2 prime numbers. It has been demonstrated for values up to
4*10^18, but not proven or disproven in general.)
The part you seem to be handwaving over is *how* a simulating halt
decider is able to determine, in *all* cases, that a computation does
not halt. That is what has been proven to be impossible.
(My characterization of "handwaving" might be unfair. I have not read
everything you've posted here, and I have read very little of your
writings elsewhere that you've cited.)
Your premise is
If H does correctly determine that its correct simulation of D would
never stop running unless aborted ...
Of course the conclusion follows IF H does what you say. That's
trivial. You would need to demonstrate that H can *always* do so, for
any D.
It would be useful, I suppose, to study your own writings that you've
cited and point out precisely where you went wrong. I personally have
neither the time nor the expertise to do so.
But let me give you a simple challenge:
Write or obtain a program that, assuming unbounded memory, will halt if
and only if Goldbach's conjecture is false. Use whatever language is
most convenient.
Apply your simulating halt decider to this program. The result should
be either "yes, it halts" or "no, it doesn't halt".
Post here and tell us whether Goldbach's conjecture is true or false.
Show your work.
I believe you will be unable to do this.
(It's theoretically possible that someone could prove or disprove
Goldbach's conjecture without solving the halting problem. That would
be very interesting, but I doubt that anyone here has the expertise to
do so.)
--
Keith Thompson (The_Other_Keith)
Keith.S.T...@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */