Halting problem undecidability and infinitely nested simulation

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Halting problem undecidability and infinitely nested simulation

Post 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
alan1000
Posts: 312
Joined: Fri Oct 12, 2012 10:03 am

Re: Halting problem undecidability and infinitely nested simulation

Post 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?)
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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
promethean75
Posts: 4881
Joined: Sun Nov 04, 2018 10:29 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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?
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
wtf
Posts: 1178
Joined: Tue Sep 08, 2015 11:36 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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."
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
wtf
Posts: 1178
Joined: Tue Sep 08, 2015 11:36 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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).
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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).
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Halting problem undecidability and infinitely nested simulation

Post 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/
PeteOlcott
Posts: 1514
Joined: Mon Jul 25, 2016 6:55 pm

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Halting problem undecidability and infinitely nested simulation

Post 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.
Skepdick
Posts: 14347
Joined: Fri Jun 14, 2019 11:16 am

Re: Halting problem undecidability and infinitely nested simulation

Post 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).
Post Reply