Halting problem proofs refuted on the basis of software engineering (Simplified so that most anyone here can validate it)

olcott

unread,

Jul 14, 2022, 3:19:59 PM7/14/22

to

This is an explanation of a key new insight into the halting problem
provided in the language of software engineering. Technical computer
science terms are explained using software engineering terms. No
knowledge of the halting problem is required.

It is based on fully operational software executed in the x86utm
operating system. The x86utm operating system (based on an excellent
open source x86 emulator) was created to study the details of the
halting problem proof counter-examples at the much higher level of
abstraction of C/x86.

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

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

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

When simulating halt decider H(P,P) simulates its input we can see that:
(1) Function H() is called from P().
(2) With the same arguments to H().
(3) With no instructions in P preceding its invocation of H(P,P).

The above shows that the simulated P cannot possibly terminate normally.
Because H can see the same (1)(2)(3) that we see H aborts its simulation
of P and rejects P as non-halting.

In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program
and an input, whether the program will finish running, or continue
to run forever. Alan Turing proved in 1936 that a general
algorithm to solve the halting problem for all possible program-
input pairs cannot exist.

For any program H that might determine if programs halt, a
"pathological" program P, called with some input, can pass its own
source and its input to H and then specifically do the opposite of
what H predicts P will do. No H can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem

H and P implement the exact pathological relationship to each other as
described above. Because H(P,P) does handle this case the above halting
problem undecidable input template has been refuted.

*When this halt deciding principle understood to be correct*
A halt decider must compute the mapping from its inputs to an accept or
reject state on the basis of the actual behavior that is actually
specified by these inputs.

*Then (by logical necessity) this implements that principle*
Every simulating halt decider that correctly simulates its input until
it correctly predicts that this simulated input would never terminate
normally, correctly rejects this input as non-halting.

*H is a Pure function*
https://en.wikipedia.org/wiki/Pure_function

thus implements a *Computable function*
https://en.wikipedia.org/wiki/Computable_function

Thus H is Turing computable.

*Halting problem proofs refuted on the basis of software engineering*
https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering

--
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,

Jul 14, 2022, 3:29:02 PM7/14/22

to

You forgot to mention infinite recursion which I suppose is progress.

/Flibble

olcott

unread,

Jul 14, 2022, 4:02:39 PM7/14/22

to

I have proved that H(P,P) == 0 is correct.

I have shown that H/P does implement the HP's "impossible input" template.

Therefore I have refuted all of the halting problem proofs that rely on
this template.

Mr Flibble

unread,

Jul 14, 2022, 4:22:46 PM7/14/22

to

Equating pathological input with non-halting is erroneous: you are only
doing that because your broken solution treats it as "infinite
recursion". There is no recursion in [Strachey 1965] and the HP proofs
based on it.

/Flibble

Chris M. Thomasson

unread,

Jul 14, 2022, 4:27:40 PM7/14/22

to

On 7/14/2022 12:19 PM, olcott wrote:
> This is an explanation of a key new insight into the halting problem
> provided in the language of software engineering. Technical computer
> science terms are explained using software engineering terms. No
> knowledge of the halting problem is required.
>
> It is based on fully operational software executed in the x86utm
> operating system. The x86utm operating system (based on an excellent
> open source x86 emulator) was created to study the details of the
> halting problem proof counter-examples at the much higher level of
> abstraction of C/x86.
>
> typedef void (*ptr)();
> int H(ptr p, ptr i); // simulating halt decider
>
> void P(ptr x)
> {
> int Halt_Status = H(x, x);
> if (Halt_Status)
> HERE: goto HERE;
> return;
> }
>
> int main()
> {
> Output("Input_Halts = ", H(P, P));
> }

Where is the guts of function H?

Richard Harnden

unread,

Jul 14, 2022, 4:53:13 PM7/14/22

to

On 14/07/2022 21:27, Chris M. Thomasson wrote:
> On 7/14/2022 12:19 PM, olcott wrote:
>>
>> int H(ptr p, ptr i); // simulating halt decider
>

> Where is the guts of function H?

This doesn't exist. It never has, it never will.

olcott

unread,

Jul 14, 2022, 5:02:55 PM7/14/22

to

There is no recursion in any of the conventional proofs only because no
one ever previously bothered to fully examine how a simulating halt
decider would address these otherwise "impossible" inputs.

I first addressed this here: comp.theory (more than five years ago)
[Solution to one instance of the Halting Problem]
On 3/14/2017 9:05 AM, peteolcott wrote:

Prior to this I made this discovery:
"It looks like the original specification provided in the Linz text may
be infinitely recursive in that each TM requires its own input."

In this Researchgate paper:
Self Modifying Turing Machine (SMTM) Solution to the Halting Problem
(concrete example) August 2016 (almost six years ago)

This revision that I made today is much simpler than all the rest:

*Halting problem proofs refuted on the basis of software engineering*
https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering

olcott

unread,

Jul 14, 2022, 5:06:50 PM7/14/22

to

I have to refactor about 50 pages of code before I can publish it.
My current paper is so simple that H can be validated as correct without
any need to see its source-code.

olcott

unread,

Jul 14, 2022, 5:09:40 PM7/14/22

to

Try carefully studying the first page of my paper and see if you still
feel the same way. I have revised this paper thousands of times based on
many thousands or reviews. It is finally simple enough that most
everyone here can validate it.

unread,

Jul 14, 2022, 5:32:18 PM7/14/22

to

Slap a copyright on H, and state that it is as it is, and post it?

Say the docs are soon to come?

olcott

unread,

Jul 14, 2022, 5:32:34 PM7/14/22

to

No but you can verify that H(P,P) correctly determines the halt status
of the halting problem's "impossible" input by carefully studying the
first page of the paper.

Example 03 (on another page) has the annotated x86 source-code of P()
and main() the execution trace of main and the execution trace of P()
simulated by H().

In Example 03 I annotated the x86 source-code to make it much easier for
C programmers. I explain how each line of x86 code corresponds to its C
source.

olcott

unread,

Jul 14, 2022, 5:35:29 PM7/14/22

to

I want to hold that back so that academic journals have something brand
new never seen before that they can publish.

It really is very easy to validate my work without seeing the
source-code for H.

>
>>
>>>>
>>>> *Halting problem proofs refuted on the basis of software engineering*
>>>> https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering
>
>
>
>

Chris M. Thomasson

unread,

Jul 14, 2022, 5:40:13 PM7/14/22

to

On 7/14/2022 2:24 PM, olcott wrote:
> On 7/14/2022 4:16 PM, Chris M. Thomasson wrote:
>> On 7/14/2022 2:06 PM, olcott wrote:
>>> On 7/14/2022 3:27 PM, Chris M. Thomasson wrote:
>>>> On 7/14/2022 12:19 PM, olcott wrote:

[...]

>>>> Where is the guts of function H?
>>>>
>>>
>>> I have to refactor about 50 pages of code before I can publish it.
>>> My current paper is so simple that H can be validated as correct
>>> without any need to see its source-code.
>>
>> Well, does refactor mean porting to another language/machine and/or
>> changing the actual logic of function H?
>>
>
> No the actual code for H is clean, correct, complete and finally (after
> nine months of work) Turing computable. It is the 50 pages of the x86utm
> operating system that are still quite messy.

[...]

Humm... I still think I have a new fractal because I posted my ideas and
code about it, and so far... No hits about "I have seen this before".
You should just post your H code, and say the fifty pages of doc's are
well in progress. Fwiw, here is my code for said fractal:

https://fractalforums.org/fractal-mathematics-and-new-theories/28/experimental-tangent-fractal/4817/msg34795#new

read all. Can you get to the link? Also, just because docs are not 100%
in order, it can be interesting to post them anyway. To show progress in
a history, so to speak:

http://funwithfractals.atspace.cc/ct_cipher/

Click here:

http://fractallife247.com/test/hmac_cipher/ver_0_0_0_1?ct_hmac_cipher=b8dfbc29229ce2a681ac17429316ce6e230066676e14f824acc106436f2ae64cd7d2535f41ecfc9aa189a486e568c232061ed41d9e59b015cc30b2f6df5fe99529b96f1c000005e56b839f1299fd3baf4353

;^)

Chris M. Thomasson

unread,

Jul 14, 2022, 5:45:48 PM7/14/22

to

On 7/14/2022 12:19 PM, olcott wrote:

Step by step docs, lol. By me. Why do you sort of seem a bit "afraid" to
post your own "cool" work:

https://github.com/ChrisMThomasson/fractal_cipher/blob/master/FFE/Pre-Alpha%20Rough%20Draft%20FFE%20Tutorial.pdf

olcott

unread,

Jul 14, 2022, 5:46:14 PM7/14/22

to

Another reason that I will not post the code is "Pearls before swine".
It really is easy to see that H(P,P) does correctly determine the halt
status of the halting problem's "impossible" input template on the first
page of my paper. People not willing to do that have not demonstrated
enough sincerity in the desire for an honest dialogue.

olcott

unread,

Jul 14, 2022, 5:57:49 PM7/14/22

to

It loses all patent rights once it is published.

Chris M. Thomasson

unread,

Jul 14, 2022, 6:21:36 PM7/14/22

to

Are you referring to transferring ownership to public domain?

Mr Flibble

unread,

Chris M. Thomasson

unread,

Jul 14, 2022, 8:15:47 PM7/14/22