Page 1 of 2
Halting problem undecidability and infinitely nested simulation
Posted: Sun Jun 13, 2021 7:52 pm
by PeteOlcott
The x86utm operating system was created so that the halting problem could be examined at the high level of abstraction of the C programming language. The partial halt decider named H correctly decides that the conventional "impossible" input is simply a program that never halts.
Code: Select all
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
The pathological self-reference of the conventional halting problem proof counter-examples is overcome. The halt status of these examples is correctly determined. A simulating halt decider remains in pure simulation mode until after it determines that its input will never stop running unless its simulation is aborted. This eliminates the conventional feedback loop where the behavior of the halt decider effects the behavior of its input.
To eliminate the pathological self-reference(Olcott 2004) from the halting problem such that there is no feedback loop between what the halt decider decides and how the input behaves the simulating halt decider simply watches what the input does without interfering at all.
As soon as the simulating halt decider determines that the simulation of the input on its input would never reach its own final state (whether or not this simulation is aborted) it aborts the simulation of this input and reports that its input does not halt.
Here it is in an adaption of the Peter Linz notation: Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ never reaches its final state (whether or not this simulation is aborted) then when Ĥ.qx transitions to Ĥ.qn it is necessarily correct.
My new paper:
Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publicatio ... simulation
Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (315-320)
https://www.liarparadox.org/Peter_Linz_ ... 5-320).pdf
Re: Halting problem undecidability and infinitely nested simulation
Posted: Thu Feb 24, 2022 2:08 pm
by alan1000
I'm fascinated by the idea that there may be a solution to the halting problem. But I'm unfamiliar with the programming context you provide. Can you express the argument in a more user-friendly language such as Xbase (or even natural language?)
Re: Halting problem undecidability and infinitely nested simulation
Posted: Sun Feb 27, 2022 12:32 am
by PeteOlcott
alan1000 wrote: ↑Thu Feb 24, 2022 2:08 pm
I'm fascinated by the idea that there may be a solution to the halting problem. But I'm unfamiliar with the programming context you provide. Can you express the argument in a more user-friendly language such as Xbase (or even natural language?)
I created an actual halt decider on the basis of creating the x86utm operating system such that the halt decider is written in C can be applied to the x86 machine language of functions written in C. The x86utm operating system is based on an x86 emulator. This provides the means for any C function to emulate any other C function in debug step mode.
https://www.researchgate.net/publicatio ... ulation_V2
Re: Halting problem undecidability and infinitely nested simulation
Posted: Thu Mar 03, 2022 12:37 am
by promethean75
Pete what the hell are you doing? If you've created a work-around, you don't publicly post the damn thing dude! You want somebody to steal it and cash in on your work?
Re: Halting problem undecidability and infinitely nested simulation
Posted: Thu Mar 03, 2022 4:39 pm
by PeteOlcott
promethean75 wrote: ↑Thu Mar 03, 2022 12:37 am
Pete what the hell are you doing? If you've created a work-around, you don't publicly post the damn thing dude! You want somebody to steal it and cash in on your work?
Protecting the copyright to a work is best maintained by posting every incremental improvement to permanent and purely public forums such as USENET. Copyrights are good for the rest of my life plus 70 years. I am at the point now where I need actual computer scientists to review it.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Tue Mar 08, 2022 2:32 am
by wtf
alan1000 wrote: ↑Thu Feb 24, 2022 2:08 pm
I'm fascinated by the idea that there may be a solution to the halting problem.
Turing showed in 1936 that there could never be a solution to the halting problem. Given that, isn't it more likely that our friend Pete is mistaken? Either that, or Alan is "Turing over in his grave."
Re: Halting problem undecidability and infinitely nested simulation
Posted: Tue Mar 08, 2022 8:29 am
by Skepdick
wtf wrote: ↑Tue Mar 08, 2022 2:32 am
Turing showed in 1936 that there could never be a solution to the halting problem. Given that, isn't it more likely that our friend Pete is mistaken? Either that, or Alan is "Turing over in his grave."
What's most likely is Pete doesn't even know which problem he's working on.
He isn't working on the halting problem, but on provably terminating algorithms. He's re-inventing
Loop unrolling.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Thu Mar 10, 2022 4:51 am
by wtf
Skepdick wrote: ↑Tue Mar 08, 2022 8:29 am
He isn't working on the halting problem, but on provably terminating algorithms. He's re-inventing
Loop unrolling.
I know what loop unrolling is but I could not discern from his posts in this thread that this is what he's doing. Did you determine this from his papers, which I didn't look at? Just curious how you worked this out.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Sun Mar 20, 2022 7:10 pm
by PeteOlcott
wtf wrote: ↑Tue Mar 08, 2022 2:32 am
alan1000 wrote: ↑Thu Feb 24, 2022 2:08 pm
I'm fascinated by the idea that there may be a solution to the halting problem.
Turing showed in 1936 that there could never be a solution to the halting problem. Given that, isn't it more likely that our friend Pete is mistaken? Either that, or Alan is "Turing over in his grave."
In my newest post I apply my analysis directly to the Peter Linz proof, which is included in full at the end of the paper.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Sun Mar 20, 2022 7:12 pm
by PeteOlcott
Skepdick wrote: ↑Tue Mar 08, 2022 8:29 am
wtf wrote: ↑Tue Mar 08, 2022 2:32 am
Turing showed in 1936 that there could never be a solution to the halting problem. Given that, isn't it more likely that our friend Pete is mistaken? Either that, or Alan is "Turing over in his grave."
What's most likely is Pete doesn't even know which problem he's working on.
He isn't working on the halting problem, but on provably terminating algorithms. He's re-inventing
Loop unrolling.
Try and find any error in my newest post that directly refutes the Peter Linz proof (which is included in full at the end of the paper).
Re: Halting problem undecidability and infinitely nested simulation
Posted: Sun Mar 20, 2022 7:13 pm
by PeteOlcott
alan1000 wrote: ↑Thu Feb 24, 2022 2:08 pm
I'm fascinated by the idea that there may be a solution to the halting problem. But I'm unfamiliar with the programming context you provide. Can you express the argument in a more user-friendly language such as Xbase (or even natural language?)
Please see my newest post that directly refutes the Peter Linz proof (that is included in full at the end of the paper).
Re: Halting problem undecidability and infinitely nested simulation
Posted: Sun Mar 20, 2022 8:02 pm
by Skepdick
PeteOlcott wrote: ↑Sun Mar 20, 2022 7:12 pm
Try and find any error in my newest post that directly refutes the Peter Linz proof (which is included in full at the end of the paper).
Dude. You are literally wasting everyone's time. Proofs are programs. You understand this, yes?
Take a dependently-typed language like Coq, Agda, LEAN. In fact - I would even settle for Idris2.
Formalise your proof in any of those systems. And then the entire community of experts in automated theorem proving/proof assistants will help you.
https://proofassistants.stackexchange.com/
Re: Halting problem undecidability and infinitely nested simulation
Posted: Mon Mar 21, 2022 2:55 am
by PeteOlcott
Skepdick wrote: ↑Sun Mar 20, 2022 8:02 pm
PeteOlcott wrote: ↑Sun Mar 20, 2022 7:12 pm
Try and find any error in my newest post that directly refutes the Peter Linz proof (which is included in full at the end of the paper).
Dude. You are literally wasting everyone's time. Proofs are programs. You understand this, yes?
Take a dependently-typed language like Coq, Agda, LEAN. In fact - I would even settle for Idris2.
Formalise your proof in any of those systems. And then the entire community of experts in automated theorem proving/proof assistants will help you.
https://proofassistants.stackexchange.com/
I have spent 12,000 hours on this since 2004.
If you care about the truth please read the paper in my other post.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Mon Mar 21, 2022 10:08 am
by Skepdick
PeteOlcott wrote: ↑Mon Mar 21, 2022 2:55 am
I have spent 12,000 hours on this since 2004.
If you care about the truth please read the paper in my other post.
Have you spent 12000 hours; or have you spent 1 hour 12000 times?
You are like a broken record. You are working in isolation so you are re-discovering stuff other people already know.
If you had taken the time to consult the existing body of knowledge and learn the common language used by your peers you could have saved yourself 11000 hours.
Re: Halting problem undecidability and infinitely nested simulation
Posted: Mon Mar 21, 2022 10:13 am
by Skepdick
wtf wrote: ↑Thu Mar 10, 2022 4:51 am
I know what loop unrolling is but I could not discern from his posts in this thread that this is what he's doing. Did you determine this from his papers, which I didn't look at? Just curious how you worked this out.
I have broadly skimmed over his papers/posts so I have a gut feel on his end goal.
His obsession is with "provability", and provability is analogous to program/proof termination. He is fixated on identifying heuristics which detect non-terminating code and his pet heuristic is cyclical graphs (loops that haven't been unrolled).