It is known that a correct halt decider must return false (in this case)[V4](Linz)

[olcott]

The following shows exactly how the Peter Linz H would correctly decide
halting on the Peter Linz Ĥ. This is fully operational code that has
been executed in the x86utm operating system that I wrote.

To make the Linz counter-example conform to the standard halting problem
counter-examples the input is not copied as it is in Linz.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

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

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
The x86 language is computationally equivalent to a UTM for all
computations that do not require more memory than is available.

Recursion can be directly simulated by a UTM that simulates its own
Turing machine Description. Infinite recursion would repeat the same
state transitions every time the UTM simulates its own Turing machine
Description.

// Defined at the bottom of page 319 of Linz
void Ĥ(u32 P)
{
u32 Input_Halts = H(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}


int main()
{
u32 P = (u32)Ĥ;
H(P, P);
HALT;
}


Disassembled x86 machine language of the above pair of C functions.

Ĥ()
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[00000508](03) 83c408 add esp,+08
[0000050b](03) 8945fc mov [ebp-04],eax
[0000050e](04) 837dfc00 cmp dword [ebp-04],+00
[00000512](02) 7403 jz 00000517
[00000514](01) f4 hlt
[00000515](02) eb02 jmp 00000519
[00000517](02) ebfe jmp 00000517
[00000519](02) 8be5 mov esp,ebp
[0000051b](01) 5d pop ebp
[0000051c](01) c3 ret

_main()
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[0000053f](03) 83c408 add esp,+08
[00000542](01) f4 hlt
[00000543](02) 8be5 mov esp,ebp
[00000545](01) 5d pop ebp
[00000546](01) c3 ret



Output_Debug_Trace() [00010abc] size(148) capacity(65536)
[00000527](01) 55 push ebp
[00000528](02) 8bec mov ebp,esp
[0000052a](01) 51 push ecx
[0000052b](07) c745fcf7040000 mov [ebp-04],000004f7
[00000532](03) 8b45fc mov eax,[ebp-04]
[00000535](01) 50 push eax
[00000536](03) 8b4dfc mov ecx,[ebp-04]
[00000539](01) 51 push ecx
[0000053a](05) e838feffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
[000004f7](01) 55 push ebp
[000004f8](02) 8bec mov ebp,esp
[000004fa](01) 51 push ecx
[000004fb](03) 8b4508 mov eax,[ebp+08]
[000004fe](01) 50 push eax
[000004ff](03) 8b4d08 mov ecx,[ebp+08]
[00000502](01) 51 push ecx
[00000503](05) e86ffeffff call 00000377
25 instructions

The above is where the halt decider aborts the whole Ĥ(Ĥ) invocation
sequence because the halt decider detects infinite recursion.

In this case infinite recursion is a function call to the same function
from the same machine address without any conditional branch
instructions that would terminate this recursion.


--
Copyright 2020 Pete Olcott

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

[olcott]

On 11/23/2020 3:02 PM, Mike Terry wrote:

> Hey, you're totally CHEATING here.  There ARE conditional branch
> intstructions, but you've just silently snipped them from the trace
> output you've shown.  There are HUGE gaps in your trace!!
>
>
> Mike.
>

Unless we maintain a line-of-demarcation between the halt decider and
its input pathological self-reference(Olcott 2004) makes the halting
problem have undecidable inputs in the same way that the Liar Paradox is
neither true nor false.

https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

Instead of asking the question: Does the input halt on its input?
that is subject to pathological self-reference.

We ask the question: Does the execution of the input have to be aborted
to prevent its infinite execution?

When we ask this latter question then we can ignore all of the
conditional branch instructions that are in the halt decider and only
pay attention to the ones that are in the input.

The input to H will be the description (encoded in some form)
of M, say WM, as well as the input w. The requirement is then
that, given any (WM, w), the Turing machine H will halt with
either a yes or no answer.

H.q0 wMw ⊢* H.yes if M applied to w halts, and
H.q0 wMw ⊢* H.no if M applied to w does not halt.
(Linz 1990:318)

Any input TMD that would never halt unless a UTM stopped simulating it
expresses behavior that is not halting behavior.

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

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

[olcott]

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 11/27/2020 11:31 AM, Ben Bacarisse wrote:
>>> olcott "Ĥ does not copy its input" <No...@NoWhere.com> writes:
>>>
>>>> On 11/25/2020 8:06 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 11/25/2020 4:16 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 11/24/2020 6:16 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>> <cut>
>>>>>>>>>> 08 bool Halts(u32 P, u32 I)
>>>>>>>>>> 09 {
>>>>>>>>>> 10 bool Halted = false;
>>>>>>>>>> 11 bool Aborted = false;
>>>>>>>>>> 12 while (!Halted && !Aborted)
>>>>>>>>>> 13 {
>>>>>>>>>> 14 Halted = DebugStep(P, I);
>>>>>>>>>> 15 Aborted = Needs_To_Be_Aborted();
>>>>>>>>>> 16 }
>>>>>>>>>> 17 return !Aborted;
>>>>>>>>>> 18 }
>>>>>>>>>
>>>>>>>>> Given
>>>>>>>>>
>>>>>>>>> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>>>>>>>>>
>>>>>>>>> The confounding example for Halts is the computation
>>>>>>>>> Confound_Halts(Confound_Halts) whose halting status is not correctly
>>>>>>>>> determined by the function call Halts(Confound_Halts, Confound_Halts).
>>>>>>>>
>>>>>>>> Halts(Confound_Halts, Confound_Halts) returns false.
>>>>>>>
>>>>>>> But Confound_Halts(Confound_Halts) is a finite computation, so that's
>>>>>>> the wrong answer (as you know perfectly well).
>>>>>>
>>>>>> You start with the assumption: "Pete is wrong".
>>>>>
>>>>> I start with the definition of what a halt decider is (in your model
>>>>> using quasi-C): a function F such that F(P, I) is true iff P(I) is a
>>>>> finite computation and false otherwise.
>>>>
>>>> To actually understand me you have to start with the first step by
>>>> understanding that in the following code DebugTrace() never returns a
>>>> value to to H_Hat().
>>>
>>> Yes, it's obvious, and I've said so on at least two occasions, though
>>> sometimes the function names were different.
> <cut>
>>> I note you declined another opportunity say you know what the halting
>>> problem and you have also never denied the facts that you cut from the
>>> post you are replying to:
>>
>> As you as I encounter your first crucial misunderstanding I igrore all
>> of your words after that and focus on correctly this key
>> misunderstanding.
>
> This is a feeble excuse to avoid answering a few simple questions. Why
> must avoid answering? The trouble is that you don't disagree with me,
> but you dare not say so explicitly or game will be up. Let's see how
> that works:
>
>>> A halt decider is a function F such that F(P, I) is true iff P(I) is a
>>> finite computation and false otherwise.
>>>
>>> Do you agree?
>

I never answer yes or no questions with a yes or no answer.
I always answer yes or no questions with a complete explanation that
derives a yes or no answer. I answered the above question this way in my
next answer.

> Ignored yet again. That's because you know this is what a halt decider
> is (in this context) and that your proposed function isn't one.
>
>>> (a) Halts(Confound_Halts, Confound_Halts) returns false, and
>>> (b) Confound_Halts(Confound_Halts) is a finite computation.
>>
>> Your failure to understand that this is a logical necessity is no
>> actual rebuttal what-so-ever that it is not a logical necessity:
>>
>> Any input (TMD / DATA) that would never halt unless
>> its simulator stopped simulating it expresses behavior

>> that is not halting behavior.
>

> Again an evasion, and for the same reason. You gave (a) so you can't
> retract it, and you know (b) is also a fact.

It is not an evasion it is a step-by-step proof that I am correct and
you always skip these steps and leap to the conclusion that I am incorrect.

> By the way, you are correct. My failure to understand that something is
> a logical necessity is in no way a rebuttal that it is one. But why
> would I?

> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation. But a computation that
> would not halt and one that is halted are different computations.

Yes, that is the exact dichotomy required by the actual halting problem.


void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);

if (!Input_Halts)
HALT
else
HERE: goto HERE;
}

Halts(H_Hat, H_Hat) does correctly decide that its input would not halt
unless Halts stopped simulating it, then Halts(H_Hat, H_Hat) itself halts.

> Confound_Halts(Confound_Halts) is a computation that does halt. It's
> just a word game to say that it only halts because it's simulation had
> to be halted in the course of determining the return value from Halts.

Not so much. In this case H_Hat never gets any return value from Halts
so it can't possibly do the opposite of whatever Halts decides and Halts
does have to stop simulating H_Hat or H_Hat would have never halted.

> The halting status (and therefore the correct halting decision) is not
> dependent on why a computation is finite, only that it is.
>
>> When Halts simulates Confound_Halts(Confound_Halts) Halts it decides
>> that Confound_Halts(Confound_Halts) would never halt unless Halts
>> stopped simulating it.
>
> Halts(Confound_Halts, Confound_Halts) returns false, according to you,
> making Confound_Halts(Confound_Halts) a finite computation.

No not at all. Halts is a finite computation. The input to Halts is only
finite because Halts forced it to be finite, otherwise it is infinite.

> How this
> determination is made by Halts makes no difference. The determination

The input to Halts is only finite because Halts forced it to be finite,
otherwise it is infinite.

> was made and false returned (again, according to you). You would love
> it if readers took the fact that Halts has a particular /reason/ for
> returning false, namely that the execution would not otherwise
> terminate, as excusing the fact that false is the wrong answer.

The input to Halts is only finite because Halts forced it to be finite,
otherwise it is infinite.

>>> Therefore Halts is not a halt decider. Which of the these do you
>>> disagree with?
>
> No answer? What a surprise!

I just proved that Halts does decide (H_Hat, H_Hat) correctly because
the input to Halts is only finite because Halts forced it to be finite,
otherwise it is infinite.

>>>> int DebugTrace(u32 P, u32 I)
>>>> {
>>>> ((int(*)(int))P)(I);
>>>> return 1;
>>>> }
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Aborted = DebugTrace(P, P);
>>>> if (Aborted)

>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {

>>>> u32 P = (u32)H_Hat;
>>>> DebugTrace(P, P);
>>>> HALT;
>>>> }
>>>
>>> In case you missed it the previous times I told you, yes, this code is
>>> non-halting. See the difference between an honest interlocutor and
>>> yourself? If your question is clear, I will answer it. You, on the
>>> other hand, duck and dive, evade and distract. Maybe you will change
>>> and ANSWER THE QUESTIONS ABOVE.
>
> Not a single one of my questions answered.
>

I answer yes or no questions with a complete explanation.

If you can have the discipline to very very carefully analyze my answers
as if there was a real chance that I am correct then it should be quite
easy to verify in your own mind that I am actually correct.

This is the key to understanding that I am correct.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

When the simulator stops simulating H_Hat before H_Hat ever gets any
return value from Halts this makes it impossible for H_Hat to do the
opposite of whatever Halts decides, thus making all the conventional HP
proofs lose their entire basis.