Essence of the culmination five years of full time work on the Halting Problem

0 views
Skip to first unread message

olcott

unread,
Jun 17, 2022, 3:39:57 PMJun 17
to
comp.theory:
[Solution to one instance of the Halting Problem]
On 3/14/2017 9:05 AM, peteolcott wrote:

Essence of the culmination five years of full time work on the Halting
Problem when I first discovered (see above) that a simulating halt
decider could correctly determine the halt status of the "impossible"
input:

When a simulating halt decider rejects all inputs as non-halting
whenever it correctly detects that its correct and complete simulation
of its input would never reach the final state of this input that all
[these] inputs (including pathological inputs) are decided correctly.





Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Mr Flibble

unread,
Jun 17, 2022, 3:41:12 PMJun 17
to
On Fri, 17 Jun 2022 14:39:49 -0500
olcott <No...@NoWhere.com> wrote:

> comp.theory:
> [Solution to one instance of the Halting Problem]
> On 3/14/2017 9:05 AM, peteolcott wrote:
>
> Essence of the culmination five years of full time work on the
> Halting Problem when I first discovered (see above) that a simulating
> halt decider could correctly determine the halt status of the
> "impossible" input:
>
> When a simulating halt decider rejects all inputs as non-halting
> whenever it correctly detects that its correct and complete
> simulation of its input would never reach the final state of this
> input that all [these] inputs (including pathological inputs) are
> decided correctly.

void Px(u32 x)
{
H(x, x);
return;
}

int main()
{
Output("Input_Halts = ", H((u32)Px, (u32)Px));
}

...[000013e8][00102357][00000000] 83c408 add esp,+08
...[000013eb][00102353][00000000] 50 push eax
...[000013ec][0010234f][00000427] 6827040000 push 00000427
---[000013f1][0010234f][00000427] e880f0ffff call 00000476
Input_Halts = 0
...[000013f6][00102357][00000000] 83c408 add esp,+08
...[000013f9][00102357][00000000] 33c0 xor eax,eax
...[000013fb][0010235b][00100000] 5d pop ebp
...[000013fc][0010235f][00000004] c3 ret
Number of Instructions Executed(16120)

It gets the answer wrong, i.e. input has not been decided correctly.
QED.

/Flibble

Richard Damon

unread,
Jun 17, 2022, 8:50:44 PMJun 17
to
On 6/17/22 3:39 PM, olcott wrote:
> comp.theory:
> [Solution to one instance of the Halting Problem]
> On 3/14/2017 9:05 AM, peteolcott wrote:
>
> Essence of the culmination five years of full time work on the Halting
> Problem when I first discovered (see above) that a simulating halt
> decider could correctly determine the halt status of the "impossible"
> input:
>
> When a simulating halt decider rejects all inputs as non-halting
> whenever it correctly detects that its correct and complete simulation
> of its input would never reach the final state of this input that all
> [these] inputs (including pathological inputs) are decided correctly.
>
>
>
>
>
> Halting problem undecidability and infinitely nested simulation (V5)
>
> https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
>
>

So, which H are you claiming is correct? You are describing two
different machines.

Is H the one that correctly emulates its input, and thus runs forever
emulation the input of H(P,P) for the P built on this H, and thus fails
to answer, or

Is H the one that does abort its emulation (and thus NOT do a corret
emulation) and return 0, and when we look at an ACTUAL correct emulation
that will behave just like P(P), for the P built on THAT H, we see that
P(P) does return, and thus H(P,P) returning 0 is incorrect.

If you want to claim that the behavior are different, what is the first
instruction accurately emulated from the input of H(P,P) that differs in
results from the direct execution of P(P).

Until you provide that evidence, your "impossible" claim needs to just
be considered a lie.

olcott

unread,
Jun 20, 2022, 2:42:04 PMJun 20
to
On 6/20/2022 9:27 AM, Paul N wrote:
> On Friday, June 17, 2022 at 8:39:57 PM UTC+1, olcott wrote:
>> comp.theory:
>> [Solution to one instance of the Halting Problem]
>> On 3/14/2017 9:05 AM, peteolcott wrote:
>>
>> Essence of the culmination five years of full time work on the Halting
>> Problem when I first discovered (see above) that a simulating halt
>> decider could correctly determine the halt status of the "impossible"
>> input:
>
> Stepping back a bit from the detail of this, may I ask where you intend going with this? Suppose for example that you posted something that did make Flibble, Richard and the others realise that they were mistaken and admit it. Would you regard the admiration of half a dozen people, one calling himself "Mr Flibble", as a worthwhile reward for five years of full-time work? Or do you intend going further, eg getting the results published elsewhere?

Ideally I want to get published in JACM the same way that Edsger
Dijkstra was published.

https://dl.acm.org/doi/10.1145/362929.362947

Letters to the editor: go to statement considered harmful
Author: Edsger W. Dijkstra

Communications of the ACM Volume 11 Issue 3 March 1968 pp 147–148
https://doi.org/10.1145/362929.362947

olcott

unread,
Jun 20, 2022, 2:52:27 PMJun 20
to
On 6/20/2022 1:38 PM, Ben Bacarisse wrote:
> Paul N <gw7...@aol.com> writes:
>
>> On Friday, June 17, 2022 at 8:39:57 PM UTC+1, olcott wrote:
>>> comp.theory:
>>> [Solution to one instance of the Halting Problem]
>>> On 3/14/2017 9:05 AM, peteolcott wrote:
>>>
>>> Essence of the culmination five years of full time work on the Halting
>>> Problem when I first discovered (see above) that a simulating halt
>>> decider could correctly determine the halt status of the "impossible"
>>> input:
>>
>> Stepping back a bit from the detail of this, may I ask where you
>> intend going with this? Suppose for example that you posted something
>> that did make Flibble, Richard and the others realise that they were
>> mistaken and admit it. Would you regard the admiration of half a dozen
>> people, one calling himself "Mr Flibble", as a worthwhile reward for
>> five years of full-time work?
>
> Five? He first "solved" the halting problem 18 years ago!
>
> BTW, if it was you that gave him the "review" he wanted in
> comp.lang.c++, you were lead stray by his trace. It does not show
> what he claims it shows.
>
> He's now being very clear about the trick he's trying to pull. There's
> nothing "in P" that can stop the apparent infinite recursion, but that's
> just sophistry. H is as much part of the computation as any other and H
> should, stop the recursion when it returns 0 to P. But he gets around
> that by "aborting" (by which I think he means a non-local transfer of
> control) so execution never reaches P's ret instruction. His claim that
> H is a pure function is just bogus.
>

#include <stdint.h>
typedef void (*ptr)();

void P(ptr x)
{
if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{
Output("Input_Halts = ", H(P, P));
}

_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P
[0000135d](05) e840feffff call 000011a2 // call H
[00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]

Every sufficiently competent software engineer can easily verify that
the complete and correct x86 emulation of the input to H(P,P) by H would
never reach the "ret" instruction of P.

>> Or do you intend going further, eg
>> getting the results published elsewhere?
>
> If he ever does publish, it will be in one of those predatory journals
> that change fees.

Mr Flibble

unread,
Jun 20, 2022, 3:02:10 PMJun 20
to
void Px(u32 x)
{
H(x, x);
return;
}

int main()
{

Richard Damon

unread,
Jun 20, 2022, 6:49:38 PMJun 20
to
Since the H that gives the non-halting answer doesn't do a complete and
correct x86 emulation of the input, this is a contradiction of terms.

BY DEFINITION, a "complete" x86 emulation doesn't stop until it reches
ah Halting state, this if the input is non-halting, the complete
emulation doesn't stop, so H can not as the same algorithm do both a
complete x86 emulation and return the value 0.

You are just showing your ignorance of what you are talking about.

olcott

unread,
Jun 21, 2022, 9:55:05 PMJun 21
to
On 6/20/2022 1:38 PM, Ben Bacarisse wrote:
> Paul N <gw7...@aol.com> writes:
>
>> On Friday, June 17, 2022 at 8:39:57 PM UTC+1, olcott wrote:
>>> comp.theory:
>>> [Solution to one instance of the Halting Problem]
>>> On 3/14/2017 9:05 AM, peteolcott wrote:
>>>
>>> Essence of the culmination five years of full time work on the Halting
>>> Problem when I first discovered (see above) that a simulating halt
>>> decider could correctly determine the halt status of the "impossible"
>>> input:
>>
>> Stepping back a bit from the detail of this, may I ask where you
>> intend going with this? Suppose for example that you posted something
>> that did make Flibble, Richard and the others realise that they were
>> mistaken and admit it. Would you regard the admiration of half a dozen
>> people, one calling himself "Mr Flibble", as a worthwhile reward for
>> five years of full-time work?
>
> Five? He first "solved" the halting problem 18 years ago!
>
> BTW, if it was you that gave him the "review" he wanted in
> comp.lang.c++, you were lead stray by his trace. It does not show
> what he claims it shows.
>
> He's now being very clear about the trick he's trying to pull. There's
> nothing "in P" that can stop the apparent infinite recursion, but that's
> just sophistry. H is as much part of the computation as any other and H
> should, stop the recursion when it returns 0 to P. But he gets around
> that by "aborting" (by which I think he means a non-local transfer of
> control) so execution never reaches P's ret instruction. His claim that
> H is a pure function is just bogus.
>
Every sufficiently competent software engineer can easily verify that
the complete and correct x86 emulation of the input to H(P,P) by H would
never reach the "ret" instruction of P because both H and P would remain
stuck in infinitely recursive emulation.

If H can determine that this is the case in a finite number of steps
then H could reject its input on this basis.

If you can't form a correct rebuttal in terms of the actual software
engineering of the *exact words specified above* then that would prove
that you are insufficiently technically competent on this point.

If you incorrectly paraphrase what I said and form a rebuttal to this
incorrect paraphrase then sufficiently technically competent software
engineers would know that you are trying to get away with the strawman
deception.

straw man
An intentionally misrepresented proposition that is set up because it is
easier to defeat than an opponent's real argument.
https://www.lexico.com/en/definition/straw_man



>> Or do you intend going further, eg
>> getting the results published elsewhere?
>
> If he ever does publish, it will be in one of those predatory journals
> that change fees.
>


Richard Damon

unread,
Jun 21, 2022, 10:35:34 PMJun 21
to
An even somewhat competent software engineer would understand that if H
actually DOES a complete and correct emulation of its input, it can't
stop that emulation to answer 0, now can it?

>
> If H can determine that this is the case in a finite number of steps
> then H could reject its input on this basis.

Thats your claim, but not proven. In fact, it has been proven to be
impossibe for H in emulating the input to H(P,P) for the P built on that H.

You CLAIM a lot, but seem to be weak on proof.

>
> If you can't form a correct rebuttal in terms of the actual software
> engineering of the *exact words specified above* then that would prove
> that you are insufficiently technically competent on this point.
>

Many have been given, if you can't understand them, the problem is on
your end.

> If you incorrectly paraphrase what I said and form a rebuttal to this
> incorrect paraphrase then sufficiently technically competent software
> engineers would know that you are trying to get away with the strawman
> deception.

If you statements were self-contradictiory, if might be easier to
comment on them.

Your H that both does a complete and correct emulation and also aborts
its emulation because it "proved" somethint that isn't true is an
impossibility on several levels.

>
> straw man
> An intentionally misrepresented proposition that is set up because it is
> easier to defeat than an opponent's real argument.
> https://www.lexico.com/en/definition/straw_man
>
>

So, why don't YOU answer the rebuttals made to your arguement rather
than just repeat your disproved statements.

The Journal editors won't take that sort of answer, if they even think
it is worth asking for the clariifcation before trashing your "paper".

olcott

unread,
Jun 21, 2022, 10:50:10 PMJun 21
to
Of course.

>>
>> If H can determine that this is the case in a finite number of steps
>> then H could reject its input on this basis.
>
> Thats your claim, but not proven. In fact, it has been proven to be
> impossibe for H in emulating the input to H(P,P) for the P built on that H.
>
> You CLAIM a lot, but seem to be weak on proof.

I just posted all of the details that sufficiently prove this point to
sufficiently competent software engineers.

A software engineer must be an expert in: the C programming language,
the x86 programming language, exactly how C translates into x86 and the
ability to recognize infinite recursion at the x86 assembly language
level. No knowledge of the halting problem is required.

All of the recent rebuttals try to bluff their way past this requirement
to hide the fact that they lack this sufficient technical competence.
Sufficiently competent software engineers will agree.

On 6/21/2022 9:38 PM, olcott wrote: [Technically competent Software
engineers can verify this halting problem proof refutation]

Richard Damon

unread,
Jun 21, 2022, 11:20:35 PMJun 21
to
No, you haven't, because you haven't dealt with the fact that your
statement is more impossible than the liar's paradox.

You CLAIM that H does BOTH a complete and correct emulation of its input
and also aborts its input to return its rejects.

That is just like saying your "CAT" barks, because what you call your
cat is actualy a dog.

H can NOT do the infinte job of being a complete and correct emulator
and also return an answer in finite time.

Until you explain how you figure you do that, you are just revealing
that you are totally ignorant of the basics of the field.

>
> A software engineer must be an expert in: the C programming language,
> the x86 programming language, exactly how C translates into x86 and the
> ability to recognize infinite recursion at the x86 assembly language
> level. No knowledge of the halting problem is required.

YEP, ALL OF THEM, except I understand the Halting Problem, which is your
problem.

I will note, one of your problems seems to be you don't understand the
difference between a C function and a C program, and that a C funciton,
under some interpretations, isn't the same as a function in computation
theory, as in computation theory, a function includes every thing it uses.

>
> All of the recent rebuttals try to bluff their way past this requirement
> to hide the fact that they lack this sufficient technical competence.
> Sufficiently competent software engineers will agree.

No, YOU are "bluffing" by just making impossible claims.

>
> On 6/21/2022 9:38 PM, olcott wrote: [Technically competent Software
> engineers can verify this halting problem proof refutation]
>
>

Which I have posted the refuation to it.
Reply all
Reply to author
Forward
0 new messages