Source-code of halt decider that decides the halting problem's "impossible" input

2 views
Skip to first unread message

olcott

unread,
Jun 18, 2022, 8:00:38 PMJun 18
to
u32 H(u32 P, u32 I)
{
HERE:
u32 End_Of_Code;
u32 Address_of_H; // 2022-06-17
u32 code_end = get_code_end(P);
Decoded_Line_Of_Code *decoded = (Decoded_Line_Of_Code*)
Allocate(sizeof(Decoded_Line_Of_Code));
Registers* master_state = (Registers*)
Allocate(sizeof(Registers));
Registers* slave_state = (Registers*)
Allocate(sizeof(Registers));
u32* slave_stack = Allocate(0x10000); // 64k;
u32 execution_trace = (u32)Allocate(sizeof(Decoded_Line_Of_Code) *
1000); // 1000 lines of x86 code

__asm lea eax, HERE // 2022-06-18
__asm sub eax, 6 // 2022-06-18
__asm mov Address_of_H, eax // 2022-06-18
__asm mov eax, END_OF_CODE
__asm mov End_Of_Code, eax

Output("Address_of_H:", Address_of_H); // 2022-06-11
Init_slave_state(P, I, End_Of_Code, slave_state, slave_stack);
Output("\nBegin Simulation Execution Trace Stored at:",
execution_trace);
if (Decide_Halting(&execution_trace, &decoded, code_end, &master_state,
&slave_state, &slave_stack, Address_of_H, P, I))
goto END_OF_CODE;
return 0; // Does not halt
END_OF_CODE:
return 1; // Input has normally terminated
}


THIS IS THE BASIC PRINCIPLE OF A HALT DECIDER THAT REFUTES THE HALTING
PROBLEM PROOFS:
When a simulating halt decider rejects all inputs as non-halting
whenever it correctly detects (in a finite number of steps) that its
correct and complete simulation of its input would never reach a final
state of this input that all [these] inputs (including pathological
inputs) are decided correctly.

computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)



This paper has not been updated since I converted H into a pure function
of its inputs. https://en.wikipedia.org/wiki/Pure_function
H no longer recursively calls itself, thus local memory is sufficient.

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

olcott

unread,
Jun 19, 2022, 10:33:25 AMJun 19
to
On 6/19/2022 5:59 AM, Richard Damon wrote:
> On 6/19/22 12:47 AM, olcott wrote:
>> On 6/18/2022 11:37 PM, Dennis Bush wrote:
>>> On Sunday, June 19, 2022 at 12:28:11 AM UTC-4, richar...@gmail.com
>>> wrote:
>>>> And again, you haven't actually proven that it does this.
>>>>
>>>> Note, since H(P,P) is defined to abort its emulation, it doesn't itself
>>>> do a correct emulation, so the test isn't that H didn't reach a final
>>>> halt state, but would an actual emulator, using the same input
>>>> (including that input calling the above H, and not this emulator) be
>>>> able to reach a finl state.
>>>>>
>>>>> computation that halts … the Turing machine will halt whenever it
>>>>> enters
>>>>> a final state. (Linz:1990:234)
>>>>>
>>>>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>>>>> Lexington/Toronto: D. C. Heath and Company. (317-320)
>>>>>
>>>>>
>>>>>
>>>>> This paper has not been updated since I converted H into a pure
>>>>> function
>>>>> of its inputs. https://en.wikipedia.org/wiki/Pure_function
>>>>> H no longer recursively calls itself, thus local memory is sufficient.
>>>>>
>>>>> Halting problem undecidability and infinitely nested simulation (V5)
>>>>> https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
>>>>>
>>>>>
>>>>>
>>>> One issue with this code is that it DOES have a hidden input, that
>>>> address that the code has been loaded at, so copies of H can behave
>>>> differently. I will leave it to someone with more expertise in this
>>>> area
>>>> to indicate how fatal that error is to your argument. This does say
>>>> that
>>>> if you DID implement this per the actual instructions of Linz, and
>>>> put a
>>>> COPY of H into P, this difference would be enough to be a problem, as
>>>> well as breaking your H.
>>>>
>>>> Note, you H only works in your broken computation model where H and the
>>>> program it tests are tied up into the same address space, and thus you
>>>> can not actually decide on an arbitrary program.
>>>>
>>>> Also, from this code, the subroutines Init_slave_state, and
>>>> Decide_Halting must also be 'pure' functions of there inputs (which
>>>> does
>>>> allow them to store information in the buffers provided, but not
>>>> anywhere else that might influence behavior.
>>>>
>>>> In particular, those functions need to behave exactly the same when
>>>> they
>>>> are evaluatd in the emulated context as when they are directly
>>>> executed.
>>>>
>>>> The the correct emuluation of H(P,P) by the actual correct and complete
>>>> emulator that is checking the truth that H claims, see the same results
>>>> as the direct execution.
>>>
>>> Did you mean "the correct emulation of P(P) / the input to H(P,P)"
>>> here, as well as below?
>>
>> That is just not the way it works.
>>
>> When a simulating halt decider rejects all inputs as non-halting
>> whenever it correctly detects (in a finite number of steps) that its
>> correct and complete simulation of its input would never reach a final
>> state of this input that all [these] inputs (including pathological
>> inputs) are decided correctly.
>
> Right, so H's answer must match what a CORRECT emulation if the TURING
> MACHINE (or PROGRAM) that its input represents would do.
Yes and in the same way when a person that represents them (their
lawyer) commits a crime then the person must go to jail because we must
always maintain the indirect relationship.

The direct relationship where the person did not commit the crime so
they don't go to jail must always be superseded by the indirect
relationship.

A halt decider must compute the mapping from its inputs to an accept or
reject state on the basis of the actual behavior of the actual inputs,
not the behavior of some mere proxy representative.

André G. Isaak

unread,
Jun 19, 2022, 10:50:04 AMJun 19
to
You do realize that the verb 'represent' means something entirely
different in legal contexts than it does in computer science?

André

--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.

olcott

unread,
Jun 19, 2022, 10:55:00 AMJun 19
to
On 6/19/2022 9:50 AM, André G. Isaak wrote:
> On 2022-06-19 08:33, olcott wrote:
>> On 6/19/2022 5:59 AM, Richard Damon wrote:
>>> On 6/19/22 12:47 AM, olcott wrote:
>
>>> Right, so H's answer must match what a CORRECT emulation if the
>>> TURING MACHINE (or PROGRAM) that its input represents would do.
>> Yes and in the same way when a person that represents them (their
>> lawyer) commits a crime then the person must go to jail because we
>> must always maintain the indirect relationship.
>>
>> The direct relationship where the person did not commit the crime so
>> they don't go to jail must always be superseded by the indirect
>> relationship.
>
> You do realize that the verb 'represent' means something entirely
> different in legal contexts than it does in computer science?
>
> André
>

It is the "indirect reference" proxy relationship that is the same that
I am referring to. When the judge orders the client to appear in court
often his proxy will suffice.

Richard Damon

unread,
Jun 19, 2022, 12:40:54 PMJun 19
to
And if H(P,P) doesn't ask about what P(P) does, then YOU have committed
perjury that you swear is following the Linz formula.

Remember, H needs to answer about the PROGRAM and INPUT it is given.

P needs to be given the input so that it asks about P applied to that input.

So, if H(P,P) doesn't ask that question, you hace LIED that your P is
the equivalent of Linz H^. Plain and simple.

>
> The direct relationship where the person did not commit the crime so
> they don't go to jail must always be superseded by the indirect
> relationship.

So, which way are you lying?

Does H(P,P) lie about what its input does since H(P,P) returns 0 and
P(P) Halts, or

Do you lie that you built P wrong, because H(P,P) isn't asking about P(P)?

>
> A halt decider must compute the mapping from its inputs to an accept or
> reject state on the basis of the actual behavior of the actual inputs,
> not the behavior of some mere proxy representative.
>
>

Right, and the actual behavior of the input that P gives must be the
behavior of the computation P(P), or your P isn't built right.

If you can't ask H about the P(P) for the P built on it, the H just
plain fails the universal requirement of a Halt Decider.

DEFINITIONS.
Reply all
Reply to author
Forward
0 new messages