Solution To The Halting Problem

[Mr Flibble]

Does anyone know the solution to the problem of halting olcott's Usenet posts?

/Flibble

--
😎

[Kaz Kylheku]

On 2021-05-02, Mr Flibble <fli...@i42.REMOVETHISBIT.co.uk> wrote:
> Does anyone know the solution to the problem of halting olcott's Usenet posts?

Everyone halts. For this case, specifically, there is an unproven
and empirically untested hypothesis about an early halt that occurs
if everyone stops responding.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[Richard Harnden]

On 02/05/2021 15:03, Kaz Kylheku wrote:
> On 2021-05-02, Mr Flibble <fli...@i42.REMOVETHISBIT.co.uk> wrote:
>> Does anyone know the solution to the problem of halting olcott's Usenet posts?
>
> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.
>

We can ask him to stop. We can't prove that he will.

[Bonita Montero]

>> Does anyone know the solution to the problem of halting olcott's Usenet posts?

> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.

The only halting-problem is whether he will halt to post off-topic
issues to comp.lang.c/c++.

[Real Troll]

Killfile should work for you. Try it.

I am surprised you are asking this because you like trolls here. I have seen you are responding to that religious nutter on every post he writes about his saviour Mr Christ.

[olcott]

On 5/2/2021 9:03 AM, Kaz Kylheku wrote:
> On 2021-05-02, Mr Flibble <fli...@i42.REMOVETHISBIT.co.uk> wrote:
>> Does anyone know the solution to the problem of halting olcott's Usenet posts?
>
> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.
>

I am going to continue to post until an accurate review proves that I a
right or proves that I am wrong. This will remain true even if no one on
this forum ever responds. In this case the reason for posting is to
establish my copyright ownership of every incremental improvement.

Occasional cross-posts are for redundant backup of my key ideas

The bigger question is when are my reviewers going to provide an
accurate review?

It is a fact that this infinite recursion detection criteria is correct:

If the execution trace of function Y() shows:
function X() is called twice in sequence from the same machine address
of Y()
with the same parameters to X()
with no conditional branch or indexed jump instructions in Y()
with no function call returns from X()
then the function call from Y() to X() is infinitely recursive.

It is a fact that this criteria correctly decides all calls from
H_Hat() to Halts() are infinitely recursive:

If the execution trace of H_Hat() by function Halts() shows:
(1) Function Halts() is called twice in sequence from the same machine
address of H_Hat().
(2) With the same parameters to Halts().
(3) With no conditional branch or indexed jump instructions in H_Hat().
(4) With no function call returns from Halts().
then the function call from H_Hat() to Halts() is infinitely recursive.

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}

All of the details including a fresh execution trace are provided here:

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf



--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

[Real Troll]

> I am going to continue to post until an accurate review proves that I
> a right or proves that I am wrong.

Don't be sure about that because people will get fed up of you and write to your NewsServer provider:

<
ab...@giganews.com
>

So be very careful before you test people's tolerance threshold here.

[olcott]

Since all of my posts have the analysis of "C" code as their primary
focus, none of my posts can be reasonably construed as off topic for C
or C++ groups.

This is the "C" code that is the primary focus of all of my posts:

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
}

int main() {
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}

Can a C/C++ function be defined that correctly decides whether or not
H_Hat((u32)H_Hat) halts?

[wij]

I have not really read all your posts, and still do not really understand the appeal
of your question. So far as I understand:

Y() (H_Hat(u32)) can be written such that X() (Halts(u32,u32)) has no way
recognizing being simulated...(Why so much focus on recursions?)

Another one has nothing to do with 'pathological form'

// [Return] true (n is even): There exist two prime numbers a,b such that n=a+b
// false: Otherwise
bool is_goldbach(BigNum n);

void Y() {
for(BigNum n=4; is_goldbach(n); n+=2) {
}
}

Can your halting decider program decide whether or not Y() terminate?

[olcott]

My halt decider does correctly decide the simplest example of the
halting problem undecidability proof counter-examples that are supposed
to "prove" that a universal halt decider is impossible:

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}

All of the details including a full x86 execution trace are in this paper:

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf

> // [Return] true (n is even): There exist two prime numbers a,b such that n=a+b
> // false: Otherwise
> bool is_goldbach(BigNum n);
>
> void Y() {
> for(BigNum n=4; is_goldbach(n); n+=2) {
> }
> }
>
> Can your halting decider program decide whether or not Y() terminate?
>

I am not going to begin to look at these things until after my first
proof is accepted as correct or proven to be incorrect.

[Chris M. Thomasson]

On 5/2/2021 10:21 AM, olcott wrote:
> On 5/2/2021 11:01 AM, Real Troll wrote:
>>
>>> I am going to continue to post until an accurate review proves that I
>>> a right or proves that I am wrong.
>>
>>
>> Don't be sure about that because people will get fed up of you and
>> write to your NewsServer provider:
>>
>> <
>> ab...@giganews.com
>>>
>>
>> So be very careful before you test people's tolerance threshold here.
>>
>
> Since all of my posts have the analysis of "C" code as their primary
> focus, none of my posts can be reasonably construed as off topic for C
> or C++ groups.
>
> This is the "C" code that is the primary focus of all of my posts:
>
> void H_Hat(u32 P)
> {
>   u32 Input_Halts = Halts(P, P);
>   if (Input_Halts)
>     HERE: goto HERE;
> }
>
> int main() {
>   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>   Output("Input_Would_Halt = ", Input_Would_Halt);
> }
>
> Can a C/C++ function be defined that correctly decides whether or not
> H_Hat((u32)H_Hat) halts?
>

One suggestion... use a proper function pointer?

[olcott]

I have to force everything to be 32 bits.

[Chris M. Thomasson]

Does your simulator force this? How does it handle simulating C code
that uses function pointers?

[olcott]

I created the x86utm operating system so that the halting problem could
be explored using the much higher level languages of C and x86.

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf

32-bit function pointers are generally cast into unsigned 32-bit
integers to more closely correspond to an actual Turing machine.

Most anything that can be written 32-bit in C can probably be executed
in x86utm because the x86 emulator is quite robust. The one thing that
is excluded is linked libraries. The x86utm operating system directly
executes COFF object files that have not been linked to libraries.

[Chris M. Thomasson]

Iirc, you mentioned that you did not create the simulator/emulator?
Right? What one are you using?

[Tim Woodall]

This is crazy. If everything is 32 bits (including memory being bounded
by 32 bit addressing)
then the halting problem for that subset of programs is trivially[1]
decidable on a 64 bit machine as the step function is computable.

[1] Where trivially means it will take a lot longer than the lifetime of
the universe to decide for some programs but it will decide eventually.

[Juha Nieminen]

In comp.lang.c++ Tim Woodall <new...@woodall.me.uk> wrote:
> On 2021-05-06, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>> On 5/5/2021 7:52 AM, olcott wrote:
>>> I have to force everything to be 32 bits.
>>>
>>
>> Does your simulator force this? How does it handle simulating C code
>> that uses function pointers?
>
> This is crazy. If everything is 32 bits (including memory being bounded
> by 32 bit addressing)
> then the halting problem for that subset of programs is trivially[1]
> decidable on a 64 bit machine as the step function is computable.

Rather obviously if the machine can only be in a finite number of different
states, the problem is trivial: Simply check if a previous state has been
reached or not.

Of course such a solution is quite useless because it doesn't tell us much.
The reason for this is that, for example, any binary "yes / no" problem
actually becomes a trinary problem: "Yes / no / out of memory". All the
interesting problems would fall into that last category, thus making
it useless. (Even if some problem could be solved in the finite amount
of space, they may take too long to check.)

> [1] Where trivially means it will take a lot longer than the lifetime of
> the universe to decide for some programs but it will decide eventually.

I don't think "the lifetime of the universe" begins to even scratch the
surface. I think a computer with an address space of just a few
hundreds of bytes would take longer than the age of the universe to go
through every possible state.

[Tim Woodall]

On 2021-05-06, Juha Nieminen <nos...@thanks.invalid> wrote:
> In comp.lang.c++ Tim Woodall <new...@woodall.me.uk> wrote:
>> On 2021-05-06, Chris M. Thomasson <chris.m.t...@gmail.com> wrote:
>>> On 5/5/2021 7:52 AM, olcott wrote:
>>>> I have to force everything to be 32 bits.
>>>>
>>>
>>> Does your simulator force this? How does it handle simulating C code
>>> that uses function pointers?
>>
>> This is crazy. If everything is 32 bits (including memory being bounded
>> by 32 bit addressing)
>> then the halting problem for that subset of programs is trivially[1]
>> decidable on a 64 bit machine as the step function is computable.
>
> Rather obviously if the machine can only be in a finite number of different
> states, the problem is trivial: Simply check if a previous state has been
> reached or not.
>

You don't even need to do that. Just calculate an upper bound of how
many steps it takes until the program either MUST have repeated or
terminated and then run the program for that number of steps (or until
it terminates). If it doesn't terminate then you know it never
terminates as it is looping (you don't know how many steps in the loop
but you don't care).

That's why S(n) has to be non-computable in general.
https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S(n)_and_%CE%A3(n)

(and the known lower bound for S(7) tells you why it's a false errand
even thinking you can "disprove" the halting problem using a (simulation
of a) 32 bit machine.)

[olcott]

Linz H decides not halting on Linz Ĥ on the basis of infinite recursion.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

[olcott]

Good point

[olcott]

On 5/6/2021 10:26 AM, Ben Bacarisse wrote:

> olcott <No...@NoWhere.com> writes:
>
>> Linz H decides not halting on Linz Ĥ on the basis of infinite recursion.
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>

> No. In order to save time (yours and mine), I've said I'll ask if you'd
> like to learn this material before taking the time to explain. Do say
> if you have time to learn why this is wrong.
>

More literally for every at least partial halt decider H that bases its
halting decision on simulating its input unless H decides infinitely
nested simulation (not halting), stops simulating Ĥ(Ĥ), and decides not
halting the alternative is that H never returns and Ĥ remains in
infinitely nested simulation.

[Chris M. Thomasson]

Don't be afraid. Its okay. For instance, I have C/C++ code that
generates files that a wonderful program called PovRay can read. I
create a shit load of files and PovRay reads and renders them. I did
that to create the following animation. My C/C++ can be used as a
generator, then PovRay can read the results and render the damn thing!

https://youtu.be/skGUAXAx6eg

So, My work was in C++ for this. The ray tracer was in PovRay:

http://www.povray.org

Its a text format, easy...

[olcott]

On 5/7/2021 8:25 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>

>> On 5/6/2021 7:47 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 5/6/2021 6:39 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 5/6/2021 5:53 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/6/2021 4:22 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/6/2021 10:26 AM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> Linz H decides not halting on Linz Ĥ on the basis of infinite recursion.
>>>>>>>>>>>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>>>>>>>>>>
>>>>>>>>>>> No. In order to save time (yours and mine), I've said I'll ask if you'd
>>>>>>>>>>> like to learn this material before taking the time to explain. Do say
>>>>>>>>>>> if you have time to learn why this is wrong.
>>>>>>>>>>
>>>>>>>>>> More literally for every at least partial halt decider H that bases
>>>>>>>>>> its halting decision on simulating its input unless H decides
>>>>>>>>>> infinitely nested simulation (not halting), stops simulating Ĥ(Ĥ), and
>>>>>>>>>> decides not halting the alternative is that H never returns and Ĥ
>>>>>>>>>> remains in infinitely nested simulation.
>>>>>>>>>

>>>>>>>>> Well that saves me some time. You don't want to know why you were wrong
>>>>>>>>> in the previous post.
>>>>>>>>
>>>>>>>> You can say that I am wrong and this has as much actual truth behind
>>>>>>>> is as Trump won the election by a unanimous consensus.
>>>>>>>>
>>>>>>>> Any dishonest lout can falsely claim that someone is wrong.
>>>>>>>
>>>>>>> Yes. And someone knowledgeable a truthful like me could tell you what
>>>>>>> you got wrong, but you told me you don't have time for that, so I won't
>>>>>>> unless you ask me to. And I'm only offering to do that for the first
>>>>>>> mistake above.
>>>>>>
>>>>>> _Infinite_Loop()...
>>>>>
>>>>> I am offering to explain one thing: why "Linz H decides not halting on
>>>>> Linz Ĥ on the basis of infinite recursion" is wrong but you keep
>>>>> ignoring this offer. Either ask me to explain (and take the trouble to
>>>>> read what then write) or leave the thread alone.
>>>>>
>>>>
>>>> Try and refute this more accurately stated basis:
>>>>
>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>
>>>> The above is adapted from (Linz:1990:319).
>>>> It shows that Turing machine Ĥ copies its input at (q0) and begins
>>>> executing an embedded copy of the original halt decider with this
>>>> input at (qx).
>>>
>>> I like your use of . to identify the TM a state belongs to, but you
>>> never use it to its full potential. Instead of having to say what qx
>>> is, you could write H.q0.
>>
>> That would be incorrect.
>> The code from H that is now embedded within Ĥ is no longer H.
>
> You can call the states of H^ anything you like. Using H.s for those
> copied from H just helps talk about them
>
>>> And you could show the H'.qa and H'.qb states
>>> rather the describing them in words.
>>
>> It is no longer H' states. The whole thing is now a single contiguous
>> Ĥ
>
> Then there is no point in using the dot. It just gets in the way.
>
>>>> It can be understood from the above specification that when the
>>>> embedded halt decider @Ĥ.qx bases its halting decision on simulating
>>>> its input, and it has (Ĥ, Ĥ) as its input that:
>>>
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy then
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy then
>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with this copy...
>>>> unless and until the halt decider @Ĥ.qx stops simulating its input.
>>>
>>> Yes. I wonder why you think this is in doubt.
>>
>> It means that the halting problem instance is decidable as not
>> halting.
>
> No. Explanation available on request.
>
>>>> Linz, Peter 1990. An Introduction to Formal Languages and
>>>> Automata. Lexington/Toronto: D. C. Heath and Company.
>>>
>>> Take care here. This makes it look like Linz wrote the silly stuff
>>> about simulation. He didn't.
>>>
>>> Does this mean you /would/ like me to say why "Linz H decides not halting
>>> on Linz Ĥ on the basis of infinite recursion" is wrong? Maybe you can
>>> see it for yourself now?
>>
>> As I said infinite recursion is not precisely correct it is actually
>> infinitely nested simulation.
>
> So you don't want your original mistake explained? OK. Why not just
> say "no", rather than blather?
>
>> You just agreed that for every at least partial halt decider H that is
>> based on simulating its input that Ĥ(Ĥ) does specify infinitely nested
>> simulation unless H stops simulating it.
>
> The nested simulations are finite in number. What /would/ happen unless
> something or other were done is irrelevant. What matters is what /is/
> done, and the nested simulations are stopped and are therefore not
> infinite.
>
>> So what is left that you could possibly say is incorrect:
>
> The same as ever: that Halts(H_Hat, H_Hat) is false when the arguments
> denote a finite computation. I.e. that it gives the wrong answer. You
> can't get round this with words.
>

void Infinite_Loop()
{

HERE: goto HERE;
}

int main()
{

Halts(Infinite_Loop(), Infinite_Loop());
}

How is it that you are not making the mistake of calling Infinite_Loop()
a finite computation because its simulation was stopped?

That would be like called a dead cow alive on the basis that it moves
when the rendering plant workers pick up its corpse.

> Also incorrect is that you reject one or other or both of these:
>
> (A1) For every instance of the halting problem that represents a finite
> computation, the correct answer is "yes".
> (A2) For every instance of the halting problem that does not represent
> a finite computation, the correct answer is "no".
>
> You keep trying to make the wrong answer sound reasonable, but even if
> you could, you are not saying anything about the halting problem because
> I tell /you/ what the right answers are for that problem.
>

If you are saying that infinite loops are not infinite then what you are
saying makes much less sense than what I am saying and others will know
this and agree.

> Your not-the-halting-problem is, none the less, interesting because, in
> general, it too is undecidable, but you don't know that yet.

[Christian Gollwitzer]

Am 02.05.21 um 22:08 schrieb olcott:

>> // [Return] true (n is even): There exist two prime numbers a,b such
>> that n=a+b
>> //               false:  Otherwise
>> bool is_goldbach(BigNum n);
>>
>> void Y() {
>>   for(BigNum n=4; is_goldbach(n); n+=2) {
>>   }
>> }
>>
>> Can your halting decider program decide whether or not Y() terminate?
>>
>
> I am not going to begin to look at these things until after my first
> proof is accepted as correct or proven to be incorrect.

Then you haven't understood the point. This program demonstrates that
your halt decider, if it actually works, can decide the Goldbach
conjecture (which is an unsolved problem in maths today).

So it is far more likely that your halt decider is wrong than that it
solves the Goldbach conjecture. In fact, by extending on the idea, if a
correct halt decider would exist, it could be used to prove *any* such
conjecture about the natural numbers.


Christian

[olcott]

On 5/7/2021 11:01 AM, Christian Gollwitzer wrote:
> Am 02.05.21 um 22:08 schrieb olcott:
>>> // [Return] true (n is even): There exist two prime numbers a,b such
>>> that n=a+b
>>> //               false:  Otherwise
>>> bool is_goldbach(BigNum n);
>>>
>>> void Y() {
>>>   for(BigNum n=4; is_goldbach(n); n+=2) {
>>>   }
>>> }
>>>
>>> Can your halting decider program decide whether or not Y() terminate?
>>>
>>
>> I am not going to begin to look at these things until after my first
>> proof is accepted as correct or proven to be incorrect.
>
> Then you haven't understood the point. This program demonstrates that
> your halt decider, if it actually works, can decide the Goldbach
> conjecture (which is an unsolved problem in maths today).
>

Yes and in this same way we can make a program that only halts when it
knows what Donald Trump has for lunch two years from now.

Such a halt decider would solve the "predicting the future" problem.

> So it is far more likely that your halt decider is wrong than that it
> solves the Goldbach conjecture. In fact, by extending on the idea, if a
> correct halt decider would exist, it could be used to prove *any* such
> conjecture about the natural numbers.
>
>
>     Christian

[Tim Woodall]

On 2021-05-07, Christian Gollwitzer <auri...@gmx.de> wrote:
>
> So it is far more likely that your halt decider is wrong than that it
> solves the Goldbach conjecture. In fact, by extending on the idea, if a
> correct halt decider would exist, it could be used to prove *any* such
> conjecture about the natural numbers.
>

AIUI, there is no known 'halting proof' of the Collatz conjecture.

I'm not enough of a mathematician to say I have a gut feeling but I
wouldn't be surprised to learn that there are far more decision problems
that cannot be answered by a halting decider than that can be answered.

[Christian Gollwitzer]

Am 07.05.21 um 22:33 schrieb Tim Woodall:

Of course you are right, it can not prove any such theorem. Correctly
stated:

If a program P exists which decides the truth of a given hypothesis for
any natural number N in finite time, then the halt decider could be used
to decide if the hypothesis is true for all natural numbers by running
it on the code

void test() {

for (int i=1; P(i); i++) {}

}

That would still be a mighty tool. As for the Collatz conjecture, we
would need to nest it. The Collatz conjecture for number N is true, if
the sequence arrives at 1, so we use the halt decider to check whether
the sequence comes to an end, and this then goes into the test function
above. This is very simlar as the regular proof with the contradicting
halting program, that no such decider can exist.

I like the Goldbach thing more because it does not need to
self-reference the halt decider.

Christian

[Ben Bacarisse]

I've set followup-to in case this off topic subthread continues...

Tim Woodall <new...@woodall.me.uk> writes:

> I'm not enough of a mathematician to say I have a gut feeling but I
> wouldn't be surprised to learn that there are far more decision problems
> that cannot be answered by a halting decider than that can be
> answered.

Yes. Formally, decision problems are really about decidable subsets of
N. A set of natural numbers, D, is decidable iff there is a Turing
machine that, for every n in N, halts and accepts if n is in D, and
halts and rejects if n is not in D.

Since there are uncountably many subsets of N, and only countably many
Turing machines, what you say is correct. A similar point was made
Turing in his 1936 paper: almost all real numbers are not computable.

If, however, you insist that a decision problem be written down as a
finite string using a finite alphabet, then the answer is different!

--
Ben.

[Chris M. Thomasson]

What simulator are you using?