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

[olcott]

(1) It is known that the UTM simulation of a machine's Turing machine
description is equivalent to directly executing it.


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


int main()
{
u32 P = (u32)H_Hat;
Halts(P, P);
HALT;
}

(2) It is known that the above code is infinitely recursive if Halts()
acts like a UTM and simulates its input returning true if and only if
its input halts.

(3) On the basis of (1) and (2) It is known that a correct halt decider
must return false.

--
Copyright 2020 Pete Olcott

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

[Richard Damon]

On 11/20/20 9:45 PM, olcott wrote:
> (1) It is known that the UTM simulation of a machine's Turing machine
> description is equivalent to directly executing it.
>
>
> void H_Hat(u32 P)
> {
>   u32 Aborted = Halts(P, P);
>   if (Aborted)
>     HALT
>   else
>     HERE: goto HERE;
> }
>
>
> int main()
> {
>   u32 P = (u32)H_Hat;
>   Halts(P, P);
>   HALT;
> }
>
> (2) It is known that the above code is infinitely recursive if Halts()
> acts like a UTM and simulates its input returning true if and only if
> its input halts.

But then you have broken Halts. The test is to change Halts ONLY for the
top level that is in the ACTUAL machine, but leave the version that is
on the 'tape' then, the UTM trace is:

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

Thus, H_Hat(H_Hat) has halting behaivor. Halts was WRONG.

[olcott]

On 11/20/2020 9:14 PM, Richard Damon wrote:
> On 11/20/20 9:45 PM, olcott wrote:
>> (1) It is known that the UTM simulation of a machine's Turing machine
>> description is equivalent to directly executing it.
>>
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = Halts(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   Halts(P, P);
>>   HALT;
>> }
>>
>> (2) It is known that the above code is infinitely recursive if Halts()
>> acts like a UTM and simulates its input returning true if and only if
>> its input halts.
>
> But then you have broken Halts. The test is to change Halts ONLY for the
> top level that is in the ACTUAL machine, but leave the version that is
> on the 'tape'

Where the Hell did you get that total bullshit from?
Justify your freaking reasoning, it seems nuts to me.

[olcott]

On 11/20/2020 9:14 PM, Richard Damon wrote:

> On 11/20/20 9:45 PM, olcott wrote:
>> (1) It is known that the UTM simulation of a machine's Turing machine
>> description is equivalent to directly executing it.
>>
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = Halts(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   Halts(P, P);
>>   HALT;
>> }
>>
>> (2) It is known that the above code is infinitely recursive if Halts()
>> acts like a UTM and simulates its input returning true if and only if
>> its input halts.
>
> But then you have broken Halts. The test is to change Halts ONLY for the
> top level that is in the ACTUAL machine, but leave the version that is
> on the 'tape' then,

H_Hat does not stop unless Halts() stops it therefore Halts() is
impossibly incorrect.

I bet you believe that Donald Trump got 250% of all the votes in the
universe.

[Mike Terry]

On 21/11/2020 02:45, olcott wrote:
> (1) It is known that the UTM simulation of a machine's Turing machine
> description is equivalent to directly executing it.

UTM simulation enumerates the steps of the TM calculation.
So, yes, in that sense.

>
>
> void H_Hat(u32 P)
> {
> u32 Aborted = Halts(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
>
> int main()
> {
> u32 P = (u32)H_Hat;
> Halts(P, P);
> HALT;
> }
>
> (2) It is known that the above code is infinitely recursive if Halts()
> acts like a UTM and simulates its input returning true if and only if
> its input halts.

Yes, we have infinite "recursive emulation".

>
> (3) On the basis of (1) and (2) It is known that a correct halt decider
> must return false.

There is no such thing as a "correct halt decider" for all inputs, but
input (H_Hat,H_Hat) is non-halting, assuming your Halts() is as
described. This is all baby stuff. [So the correct halting decision
for the input is non-halting].

[Just in case you're considering this - of course if you change your
spec for Halts to make a new function Halts2, then that also changes the
H_Hat machine to H_Hat2, and the *new* input (H_Hat2,H_Hat2) might be
halting or non-halting, depending on the change. This is also baby
stuff...]


Regards,
Mike.

[olcott]

Yeah, finally someone that is not dishonest.

Did you notice that this "baby stuff" did correctly decide the key
counter-example that had previously been accepted as proof that halting
is undecidable?

> [Just in case you're considering this - of course if you change your
> spec for Halts to make a new function Halts2, then that also changes the
> H_Hat machine to H_Hat2, and the *new* input (H_Hat2,H_Hat2) might be
> halting or non-halting, depending on the change.  This is also baby
> stuff...]
> Regards,
> Mike.
>

[Richard Damon]

On 11/20/20 10:22 PM, olcott wrote:
> On 11/20/2020 9:14 PM, Richard Damon wrote:
>> On 11/20/20 9:45 PM, olcott wrote:
>>> (1) It is known that the UTM simulation of a machine's Turing machine
>>> description is equivalent to directly executing it.
>>>
>>>
>>> void H_Hat(u32 P)
>>> {
>>>    u32 Aborted = Halts(P, P);
>>>    if (Aborted)
>>>      HALT
>>>    else
>>>      HERE: goto HERE;
>>> }
>>>
>>>
>>> int main()
>>> {
>>>    u32 P = (u32)H_Hat;
>>>    Halts(P, P);
>>>    HALT;
>>> }
>>>
>>> (2) It is known that the above code is infinitely recursive if Halts()
>>> acts like a UTM and simulates its input returning true if and only if
>>> its input halts.
>>
>> But then you have broken Halts. The test is to change Halts ONLY for the
>> top level that is in the ACTUAL machine, but leave the version that is
>> on the 'tape'
>
> Where the Hell did you get that total bullshit from?
> Justify your freaking reasoning, it seems nuts to me.
>

Because, when I run it with the trace you keep on removing, and using
your definition of what Halts does, it Halts

When H_Hat(H_Hat) is run as a Turing Machine the trace is:

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

Thus, the answer to does H_Hat halt must be TRUE.

The test, would be to look at your above machine and input, and change
the Halts in the machine, but NOT in the input (as we need to be asking
the same question).

Because the original problem is stated in the Turing Machine Domain,
this is a clearly defined operation. You change the definition of Halts
in the actual machine (or if run via a UTM, on the part of the tape that
represents the Turing Machine), but you keep the tape (or the part that
represents the tape) the same.

A simple proof that this is the right way to do it is the above trace.
If you don't get that trace, you aren't working with a proper mapping of
the problem. Yes, your program will be the equivalent of SOME Turing
Machine, but not the right one.

Your 'trick' of changing both machine and tape, is basically a cheat
that makes it so that you break the halt detector in a way you can try
to hide it.

[olcott]

Yes you can screw up my correct halt decider to force it to decide
halting incorrectly.

H_Hat does not stop unless Halts() stops it therefore Halts() is
impossibly incorrect.

I am convinced that you are insincere about wanting to have any mutual
understanding.

[Richard Damon]

Again, you remove without comment the trace that shows that your decider
is flawed. Let me give it again:

When H_Hat(H_Hat) is run as a Turing Machine the trace is:


1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

Thus, the answer to does H_Hat halt must be TRUE, and Halts wrong.


I do NOT 'screw up' your alleged halt decider. I use it as designed. I
just remove any interference of it from the UTM running my actual
machine. I can also test the 'needed to abort' statement by removing
that one abort decision in the top level machine (leaving the program
under tewt alone) and see that your halts function WOULD have completed,
thus 'needed' is fale.

>
> H_Hat does not stop unless Halts() stops it therefore Halts() is
> impossibly incorrect.

But the non-halting behavior is a problem with Halts, not H_Hat. A key
point is that H_Hat(H_Hat) is not in itself recursive. There is NO
actual recursion in the definition. It is only Halts 'mistaken'
implementation to mostly blindly running the input that creates the
recursion. Since there is a requirement on Halts that it have finite
execution, the requirement is on IT to limit that recursion. The thing
it finds it needs to abort is the mistake in Halts, not a 'recursion' in
H_Hat.

In one sense you are sort of right, your Halts is imposssible, and

incorrect.
>
> I am convinced that you are insincere about wanting to have any mutual
> understanding.
>

And I am convinced that you seem incapable of actually facing the truth.

[olcott]

You know full well that what you are saying is pure bullshit.
There is no justifiable reason for enabling and disabling the halt
decider here and there.

[Mike Terry]

That makes no sense at whatsoever. (Seriously, I can't even guess what
you're thinking, even after rereading what's been said so far...)

What "baby stuff" exactly? You use "baby stuff" like it's an actual
halt decider, but all that's been agreed is

(3) It is known that a correct halt decider must return false.

Well, the (H_Hat,H_Hat) you described was non-halting, and a "correct
halt decider" would need to return return false for that calculation,
but SO WHAT? This has nothing to do with the Linz proof and "key
counter-example". (Or at least you will have to give some kind of clue
to what you're thinking!)

Look, /EVERY/ input (P,I) is either halting or non-halting, so for
/every/ (P,I) there is of course a value that a "correct halting
decider" must return. And equally obviously, for every (P,I) there are
many deciders which return the correct decision for that input...

I think perhaps you're reading stuff into your choice of function names
like Halts(), H_Hat() that is not there. Perhaps your "baby stuff" mean
"Halts()"? That makes no sense either - as you've described it Halts()
does NOT make a correct halting decision for (H_Hat,H_Hat)! [You said
it yourself - your Halts() never returns for input (H_Hat,H_Hat)!
Halts() is not even a decider...]


Mike.

[Richard Damon]

Please note, the ONLY time I have ever mention altering is as a method
to test 'needs to abort or else'. These words by their nature say the
test is to make a change a do otherwise. You make the claim that if you
did not abort the execution HERE, in this stream of execution, that the
Machine would run forever. The natural test of that is to make the
system not abort THERE (and only not abort THERE).

Of course, that argument doesn't really matter, because shown above,
which doesn't do any of that, and which you seem to ignore, shows that
when we check the results against the REAL definition, your machine fails.

[Ben Bacarisse]

olcott <No...@NoWhere.com> writes:

> (1) It is known that the UTM simulation of a machine's Turing machine
> description is equivalent to directly executing it.
>
>
> void H_Hat(u32 P)
> {
> u32 Aborted = Halts(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
>
> int main()
> {
> u32 P = (u32)H_Hat;
> Halts(P, P);
> HALT;
> }
>
> (2) It is known that the above code is infinitely recursive if Halts()
> acts like a UTM and simulates its input returning true if and only if
> its input halts.

Right, but then Halts would not be a decider at all. Previously you
have show code for a function named H that always returns. That code
gets a case similar to the one shown wrong. Does Halts always return?

By the way, why do you call the returned value "Aborted" if it indicates
that the emulated computation is finite? And why is H_Hat named that
when it calls Halts and not a function named H? And why does it not use
the returned value in the way the usual xxx_Hat construction would?

> (3) On the basis of (1) and (2) It is known that a correct halt
> decider must return false.

Yes, you can show a function that gets the right answer for the case
your describe. That is /always/ possible. But as soon as you provide
it, I will provide you with a case that that function will get wrong.

Are you deliberately not showing Halts (even in outline)?

Are you deliberately saying "a correct halt decider" and not actually
showing it because you know that showing it (even in outline) will allow
a confounding example to be given?

Are you deliberately the getting construction of H_Hat wrong?

Why can't you get the details right, even after twenty years?

--
Ben.

[olcott]

H_Hat() is the Linz version minus the unconventional copying of its
input and adapted to be executed as an x86utm equivalent computation.

When we transform this back to Turing Machines from x86 virtual machines
H is the Turing machine description of a Universal Turing Machine that
has been adapted to be a decider and H_Hat is also the Turing machine
description a universal Turing machine. All of these machine
descriptions are executed in a master UTM.

Think of the first ⊢ as copying an integer reference to its input.
Halts() indicates that H_Hat would start simulating the halt decider
with references to inputs wM wM. A reference to an input would be a
specific location on the tape (perhaps indexed by an integer subscript).

Ĥ.q0 wM ⊢ Ĥ.qx wM wM Halts() Ĥ.qy ∞
Ĥ.q0 wM ⊢ Ĥ.qx wM wM Halts() Ĥ.qn

H simulates its input until it detects the infinite recursion:
H simulates H_Hat that simulates H that simulates H_Hat that simulates
H. (see attached x86utm execution trace)

> Look, /EVERY/ input (P,I) is either halting or non-halting, so for
> /every/ (P,I) there is of course a value that a "correct halting
> decider" must return.  And equally obviously, for every (P,I) there are
> many deciders which return the correct decision for that input...
>
> I think perhaps you're reading stuff into your choice of function names
> like Halts(), H_Hat() that is not there.

H_Hat() does implement the conventional "do the opposite of whatever the
halt decide decides" of the conventional halting problem undecidability
proofs.

D = "On input <M>, where M is a TM:
1. Run H on input <M, <M>>.
2. Output the opposite of what H outputs;
that is if H accepts, reject and if H rejects, accept."

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

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)

H_Hat() is in the proper Linz relation to Halts.

> Perhaps your "baby stuff" mean
> "Halts()"?  That makes no sense either - as you've described it Halts()
> does NOT make a correct halting decision for (H_Hat,H_Hat)!  [You said
> it yourself - your Halts() never returns for input (H_Hat,H_Hat)!
> Halts() is not even a decider...]

01 void H_Hat(u32 P)
02 {
03 if (Halts(P, P))
04 HERE: goto HERE;
05 else
06 HALT
07 }


When Halts() detects that H_Hat() is infinitely recursive it makes the
decision to stop simulating H_Hat at the first point in the execution
trace where it has enough information to do this. In the otherwise
infinitely recursive execution sequence it aborts the execution of the
whole sequence at line 03 of H_H_Hat.

A correct halt decider: Halt(H_Hat, H_Hat) must abort its input before
its input ever returns a value so that it can return a value. I have the
execution trace to prove it. It will be appended to this message.

>
> Mike.
>
>>
>>> [Just in case you're considering this - of course if you change your
>>> spec for Halts to make a new function Halts2, then that also changes
>>> the H_Hat machine to H_Hat2, and the *new* input (H_Hat2,H_Hat2) might
>>> be halting or non-halting, depending on the change.  This is also baby
>>> stuff...]
>>> Regards,
>>> Mike.
>>>
>>
>>

[olcott]

_H_Hat()
[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

Number of Instructions Executed(10671)

[olcott]

On 11/20/2020 8:45 PM, olcott wrote:
> (1) It is known that the UTM simulation of a machine's Turing machine
> description is equivalent to directly executing it.
>
>
> void H_Hat(u32 P)
> {
>   u32 Aborted = Halts(P, P);
>   if (Aborted)
>     HALT
>   else
>     HERE: goto HERE;
> }
>
>
> int main()
> {
>   u32 P = (u32)H_Hat;
>   Halts(P, P);
>   HALT;
> }
>
> (2) It is known that the above code is infinitely recursive if Halts()
> acts like a UTM and simulates its input returning true if and only if
> its input halts.
>
> (3) On the basis of (1) and (2) It is known that a correct halt
> decider must return false.
>

The following execution trace of the above code proves this point:

[olcott]

On 11/21/2020 10:18 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> (1) It is known that the UTM simulation of a machine's Turing machine
>> description is equivalent to directly executing it.
>>
>>
>> void H_Hat(u32 P)
>> {
>> u32 Aborted = Halts(P, P);
>> if (Aborted)
>> HALT
>> else
>> HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>> u32 P = (u32)H_Hat;
>> Halts(P, P);
>> HALT;
>> }
>>
>> (2) It is known that the above code is infinitely recursive if Halts()
>> acts like a UTM and simulates its input returning true if and only if
>> its input halts.
>
> Right, but then Halts would not be a decider at all.

That is the point of point(2)

> Previously you
> have show code for a function named H that always returns.

Yes this is not that case. This alternative case is to be contrasted
with the other case proving that the other case does decide not halting
correctly.

> That code
> gets a case similar to the one shown wrong. Does Halts always return?

Here Halts() merely invokes an ordinary UTM that itself never halts when
its simulated input never halts. It is for the purpose of showing that
the actual behavior of H_Hat really is infinitely recursive.

> By the way, why do you call the returned value "Aborted" if it indicates
> that the emulated computation is finite?

I aim for people to get the gist of the idea before I delve into details
that could be overwhelming. The original idea was to comment out a
single line of the halt decider to transform it into an ordinary UTM.

08 bool H(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 }

> And why is H_Hat named that
> when it calls Halts and not a function named H?

In the x86utm code Halts(main, NULL) is always automatically invoked
thus giving is a global scope.

We need this extra feature only on the x86utm side so that the halt
decider can see that H_Hat(H_Hat) is itself directly infinitely recursive.

When this is implemented as Turing machines all code is only simulated
inside the halt decider adapted UTM, thus H_Hat(H_Hat) is itself also
directly infinitely recursive.

> And why does it not use
> the returned value in the way the usual xxx_Hat construction would?

I can only estimate what you mean here. The simulation of H_Hat never
gets past its infinitely recursive call to Halts because this is the
point where its execution is aborted.

>> (3) On the basis of (1) and (2) It is known that a correct halt
>> decider must return false.
>
> Yes, you can show a function that gets the right answer for the case
> your describe. That is /always/ possible. But as soon as you provide
> it, I will provide you with a case that that function will get wrong.

Go ahead and try to do this.

> Are you deliberately not showing Halts (even in outline)?

I have already explained all the details of exactly how this works in
this specific case hundreds of times. These details were my 2018-12-13
solution.

This is the generic halt deciding algorithm:

When-so-ever decider H (adapted from a UTM) decides that:
(a) its input (<P>,I) would never halt unless H stopped simulating it
and it is the case that
(b) its input (<P>,I) would never halt unless H stopped simulating it
then H has made a correct not-halting decision on this input.

I have not yet fully implemented my 2018-12-13 partial halt decider.
At this point it is very doubtful that this will take longer than a week
to complete.

This biggest sub-task of this task is to decode all of the control flow
instructions. This is much more than what is needed to implement the
2018-12-13 solution, yet enables the halt decider to be easily augmented
to detect an infinite set of inputs with infinite execution.

> Are you deliberately saying "a correct halt decider" and not actually
> showing it because you know that showing it (even in outline) will allow
> a confounding example to be given?

As I say in the thread heading (in this case) it is very obviously
self-evident that the halt decider must return false.

> Are you deliberately the getting construction of H_Hat wrong?

No and I believe that you know that it is not wrong.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine

I did eliminate the copying of the input because this diverges from, the
general pattern of halting problem proof counter-examples, none of the
main textbook examples ever copy their input.

Other than this minor simplification my H_Hat is as close to the Peter
Linz H_Hat as any x86utm (x86 based) equivalent computation can possibly
be.

> Why can't you get the details right, even after twenty years?
>


--

[olcott]

When we abort the execution at the very first point where infinite
execution is detected it makes following the execution trace much easier.

We could just as well wait for the 99th time that infinite execution is
detected before we actually abort the execution and the halt decider
would still be correct.

What we cannot do is wait for some future point in the execution trace
where one of the deeper recursive calls aborts the execution of it
input, because that never ever occurs. I thought all these things
through for very many months before first presenting them here.

> Of course, that argument doesn't really matter, because shown above,
> which doesn't do any of that, and which you seem to ignore, shows that
> when we check the results against the REAL definition, your machine fails.

Not at all. Not in the least little bit

When-so-ever decider H (adapted from a UTM) decides that:
(a) its input (<P>,I) would never halt unless H stopped simulating it
and it is the case that
(b) its input (<P>,I) would never halt unless H stopped simulating it
then H has made a correct not-halting decision on this input.

19 int main()
20 {
21 H_Hat(H_Hat);
22 }


Halts(main, NULL) aborts its input because it decides that line 21
specifies infinite recursion.

The exact same decision is made for a computationally equivalent reason
when Halts is adapted from a UTM to become a decider that simulates the
Turing machine description of H_Hat(H_Hat). H_Hat is the Turing machine
description of a UTM thus providing the means for the computational
equivalent of recursively calling itself.

[Mike Terry]

<.. snip ..>

ok, I started trying to reply to your response, but it seems that your
original post is SOOOOOOO full of silly errors and silly wordings etc..
that I would be wasting my time.

I think the gist of what your reply is that you mean your Halts() to be
Linz's H, and your H_Hat to be Linz's H^.

The problem with this is that your Halts, by your own description in (2)
never returns for input (H_Hat,H_Hat), so is not a decider, let alone a
halt decider.

So saying that /anything/ we agreed above "did correctly decide the key

counter-example that had previously been accepted as proof that halting

is undecidable" is wrong, in a silly way.

I suspect that you wish to say that Halts /isn't/ as you describe in
your (2), because you started your (2) with a big /IF/. Well, the only
stuff I agreed to was the /IF/ stuff. I even added an anticipatory note
about what would happen if you were thinking of changing Halts().
Basically, I can't see anything new here after all - just an
inadequately worded summary of stuff that has all been properly
addressed elsewhere.

Mike.

[olcott]

Not precisely. When we execute H_Hat(H_Hat) it is the halt decider that
has been adapted from a UTM that performs this simulated execution.

> The problem with this is that your Halts, by your own description in (2)
> never returns for input (H_Hat,H_Hat), so is not a decider, let alone a
> halt decider.

(2) Is this example of Halts() with halt deciding disabled on line 15.

08 bool H(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 }

(3) is the same as (2) yet with line 15 enabled.

> So saying that /anything/ we agreed above "did correctly decide the key
> counter-example that had previously been accepted as proof that halting
> is undecidable" is wrong, in a silly way.
>
> I suspect that you wish to say that Halts /isn't/ as you describe in
> your (2), because you started your (2) with a big /IF/.  Well, the only
> stuff I agreed to was the /IF/ stuff.  I even added an anticipatory note
> about what would happen if you were thinking of changing Halts().
> Basically, I can't see anything new here after all - just an
> inadequately worded summary of stuff that has all been properly
> addressed elsewhere.
>
> Mike.
>

[Richard Damon]

On 11/21/20 1:54 PM, olcott wrote:
> On 11/21/2020 10:03 AM, Richard Damon wrote:
>>
>> Please note, the ONLY time I have ever mention altering is as a method
>> to test 'needs to abort or else'. These words by their nature say the
>> test is to make a change a do otherwise. You make the claim that if you
>> did not abort the execution HERE, in this stream of execution, that the
>> Machine would run forever. The natural test of that is to make the
>> system not abort THERE (and only not abort THERE).
>
> When we abort the execution at the very first point where infinite
> execution is detected it makes following the execution trace much easier.

That fine, just make sure when we use your UTM it doesn't erroneously
'abort' executions.

>
> We could just as well wait for the 99th time that infinite execution is
> detected before we actually abort the execution and the halt decider
> would still be correct.
>
> What we cannot do is wait for some future point in the execution trace
> where one of the deeper recursive calls aborts the execution of it
> input, because that never ever occurs. I thought all these things
> through for very many months before first presenting them here.

Again. you don't seem to understand how to do a neccessity test.

We have a call into Halts which claims that by 'neccesity' it has to
abort the operation or it will never complete.

We can test that decision, by in that EXACT invocation (and no others)
disable the halting decision, and see what happens. (Note, this means
that we let it do the aborts that it thought were needed in nested
decisions). If the abort was REALLY needed, then this program will loop
infinitely. If the program actually comes to a halt, then the fact that
it did complete means that the decision to abort was in fact wrong.

So, since at the top level Halts(H_Hat, H_Hat) says it needs to abort,
we could test that decision by runnng something like
Halts_with_no_aborting(H_Hat, H_Hat), and see what it does, Note, that
H_Hat itself hasn't been changed, it still calls the Halts which
actually does abort. After all, we need to verify the aborting decision
on the same question.

It turns out that way you have defined how your Halts works, the
function Halts_with_no_aborting() is just the original UTM, un modified
with the aborting code. Which actually makes sense, as the verification
SHOULD be to just run the program and see if it halts.

When we do this, H_Hat(H_Hat) does halt, so Halts was wrong in its
assertion that it would run forever.

>
>> Of course, that argument doesn't really matter, because shown above,
>> which doesn't do any of that, and which you seem to ignore, shows that
>> when we check the results against the REAL definition, your machine
>> fails.
>
> Not at all. Not in the least little bit
>
> When-so-ever decider H (adapted from a UTM) decides that:
> (a) its input (<P>,I) would never halt unless H stopped simulating it
> and it is the case that
> (b) its input (<P>,I) would never halt unless H stopped simulating it
> then H has made a correct not-halting decision on this input.

The TRUE definition of a Halt Decider is a Machine that will decide
whether another Machine/Input combinaition, when it is actually run,
will Halt or run forever. A discription of this Machine/Input will be
provided to the decider for it to make its decision.

>
> 19 int main()
> 20 {
> 21   H_Hat(H_Hat);
> 22 }
>
>
> Halts(main, NULL) aborts its input because it decides that line 21
> specifies infinite recursion.

Ego, Your Universe has no UTM capable of running Turing Machines, so it
is broken.

To preform a valid test, we need to be able to actually run the machine.

Wait, we can do this!!! As the operation of a Turning Machine is fully
defined. The run trace of H_Hat(H_Hat) is:

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

As has been posted many times, the results of your broken 'UTM' not
withstanding. Thus it is proved that H_Hat(H_Hat) will halt in finite
time given that Halts(H_Hat, H_Hat) has been deterined to say not halting.

>
> The exact same decision is made for a computationally equivalent reason
> when Halts is adapted from a UTM to become a decider that simulates the
> Turing machine description of H_Hat(H_Hat). H_Hat is the Turing machine
> description of a UTM thus providing the means for the computational
> equivalent of recursively calling itself.
>
>

I will note, you still haven't made any comments to disagree with my
execution trace of the run of H_Hat(H_Hat) so I presume you agree with it.

All you have said is that when Halts runs it, that it makes the
(incorrect) decision that it needs to abort it.

[olcott]

On 11/21/2020 1:45 PM, Richard Damon wrote:
> On 11/21/20 1:54 PM, olcott wrote:
>> On 11/21/2020 10:03 AM, Richard Damon wrote:
>>>
>>> Please note, the ONLY time I have ever mention altering is as a method
>>> to test 'needs to abort or else'. These words by their nature say the
>>> test is to make a change a do otherwise. You make the claim that if you
>>> did not abort the execution HERE, in this stream of execution, that the
>>> Machine would run forever. The natural test of that is to make the
>>> system not abort THERE (and only not abort THERE).
>>
>> When we abort the execution at the very first point where infinite
>> execution is detected it makes following the execution trace much easier.
>
> That fine, just make sure when we use your UTM it doesn't erroneously
> 'abort' executions.
>>
>> We could just as well wait for the 99th time that infinite execution is
>> detected before we actually abort the execution and the halt decider
>> would still be correct.
>>
>> What we cannot do is wait for some future point in the execution trace
>> where one of the deeper recursive calls aborts the execution of it
>> input, because that never ever occurs. I thought all these things
>> through for very many months before first presenting them here.
>
> Again. you don't seem to understand how to do a neccessity test.
>
> We have a call into Halts which claims that by 'neccesity' it has to
> abort the operation or it will never complete.

When the halt decider is defined to abort the simulations of all of its
inputs that would never halt if these simulations were never aborted
then the halt decider has made a correct not halting decision BY
FREAKING DEFINITION.

DO YOU FREAKING COMPREHEND THAT ANY STATEMENT THAT IS TRUE BY DEFINITION
IS NECESSARILY TRUE AND IMPOSSIBLY FALSE OR IS THIS OVER YOUR HEAD?

[Richard Damon]

Yes, If the halt decider desided that the input would not halt unless
aborted, and then when that copy of the halt decider is changed to not
abort, but the input question remains the same (using the old halt
decider) and that case does not stop, then Yes, it has made the right
decision.

But when that copy of the halt decider is changed, but the input is not
changed, and we actually do run that case, the halt decider does return,
showing that the halt decider made an incorrect decision.

your logic,
A and B implies i am correct.
C
Yeh, I must be correct, but
not B
I guess you aren't

By changing the tape contents (i.e. the code in the halt decider the
tape program uses) you are changing the question to the halt decider.

Note also, the ability to change one and not the other is clearly
possible, at least in the Turing Space that the problem is stated, as
there is one copy of the Halt Decider as the code for the machine to be
executed, and a second copy, in representation form, on the input tape.
We are clearly allowed to change the one in the machine and not change
the tape.

If your machine is unable to do this, then you have made an improper
'equivalent' machine.

[dklei...@gmail.com]

On Saturday, November 21, 2020 at 10:59:03 AM UTC-8, Mike Terry wrote:

> ok, I started trying to reply to your response, but it seems that your
> original post is SOOOOOOO full of silly errors and silly wordings etc..
> that I would be wasting my time.

Back when PO was messing up linguistics as badly as he is now messing
up logic I took to replying to his posts up to the first error and ignoring
everything else. Didn't phase PO but saved my time.

[olcott]

The only basis for any current rebuttal is rhetoric utterly bereft of
sound reasoning.

[olcott]

I give up on you. You are simply a liar.

[olcott]

I present a very specific case where the not halting decision of a halt
decider on a specific input can be known to be correct on the basis of
logical necessity and you continue to use the dishonest dodge of the
straw-man error of reasoning. https://en.wikipedia.org/wiki/Straw_man

It is true by logical necessity that any decider that decides to abort
the simulation of any input that would never otherwise halt has made a
correct not halting decision.

Anyone that denies this that understands the technical details is
necessarily a liar.

Anyone that tries to obscure the truth of this by using a dishonest
dodge of the the straw-man error of reasoning is also a liar.

[Richard Damon]

On 11/21/20 4:18 PM, olcott wrote:
> On 11/21/2020 2:45 PM, Richard Damon wrote:

>> Yes, If the halt decider desided that the input would not halt unless
>> aborted, and then when that copy of the halt decider is changed to not
>> abort, but the input question remains the same (using the old halt
>> decider) and that case does not stop, then Yes, it has made the right
>> decision.
>>
>> But when that copy of the halt decider is changed, but the input is not
>> changed, and we actually do run that case, the halt decider does return,
>> showing that the halt decider made an incorrect decision.
> I present a very specific case where the not halting decision of a halt
> decider on a specific input can be known to be correct on the basis of
> logical necessity and you continue to use the dishonest dodge of the
> straw-man error of reasoning. https://en.wikipedia.org/wiki/Straw_man
>
> It is true by logical necessity that any decider that decides to abort
> the simulation of any input that would never otherwise halt has made a
> correct not halting decision.

You *CLAIM* it is a logical necessity, but the logic that says it is a
necessity is flawed.

The fact that a simple test of what happens shows different results is
proof that the logc is flawed.

If you are pulled over for running a red light, and try to show a
logical proof that you couldn't of, but they pull out the stop light
camera photo of you running the light, you WILL be found guilty.

>
> Anyone that denies this that understands the technical details is
> necessarily a liar.
>
> Anyone that tries to obscure the truth of this by using a dishonest
> dodge of the the straw-man error of reasoning is also a liar.
>
>

Showing what the machine actually does is a 'dishonest dodge'?

Let me try to explain the falicy in your logically necessity.

Yes, if you find a recursive loop with NO conditionals in it (and no
external force that can break it) then yes, you can prove that the
behavior will be an infinite loop.

But that ISN'T the case we have here. When you trace through the loop
there IS a conditional in it. That conditional is the halt detection
code added to you emulator. Because there IS a conditional, you can no
longer use the property of unconditional looping.

You have some how gotten into your mind that this conditional doesn't
count, because it is part of the halt detection code, but it does. In
fact that code is very much needed to be in there to keep your decider
from having non-halting behavior itself (which is a requirement on it).

The problem is that you seem so intent on trying to 'prove' Linz wrong,
that you are being blinded to the actual facts.

You seem to thnk that the ONLY way to solve this halting problem is with
brute force emulation and adding code to detect non-halting behavior.
Not only is it not the only way, it is well known to be a BAD way to do it.

There are many other ways to solve this problem (of course none work in
all cases). One method that handles this sort of issue is to detect the
recusrion like you are doing, and when you detect recursive identical
use of the halt detector, rather than just assuming this means
non-halting behavior (because is doesn't) is to fork the execution into
trying two paths, one assuming you return true, and one assuming you
return false. If the True path ends up actually halting, then you can
just assume your answer is true. If it doesn't, and the false path also
gets into infinite execution, then you can answer false.

If the true path goes non-halting and the false path halting, then you
have a machine that is like Linz. This situation has no valid answer by
the classical halting problem, but you could define an alternate problem
of halting-or-contradiction decider, and let it answer contradiction.

This method still needs to solve other forms of non-halting behavior (so
some of the other proofs of its non-existence may still apply), and you
would also need to see if this modified halting-or-contradictor decider
is actually useful for anything.

I suspect that some of the other proof will likely also provide some
conditions that are not decidable, but it also may be possible to come
up with a machine with a tri-nary answer: Halt, Non-Halting, or
Undecidable. Again, it comes down to seeing if such a machine has any
practical uses. It doesn't directly affect most of things based on the
halting problem, but maybe someone with more background in the field
might be able to tell. I also would expect that someone has already done
a lot of this work, I am just not familiar with it.

[olcott]

On 11/21/2020 4:27 PM, Richard Damon wrote:
> On 11/21/20 4:18 PM, olcott wrote:
>> On 11/21/2020 2:45 PM, Richard Damon wrote:
>
>>> Yes, If the halt decider desided that the input would not halt unless
>>> aborted, and then when that copy of the halt decider is changed to not
>>> abort, but the input question remains the same (using the old halt
>>> decider) and that case does not stop, then Yes, it has made the right
>>> decision.
>>>
>>> But when that copy of the halt decider is changed, but the input is not
>>> changed, and we actually do run that case, the halt decider does return,
>>> showing that the halt decider made an incorrect decision.
>> I present a very specific case where the not halting decision of a halt
>> decider on a specific input can be known to be correct on the basis of
>> logical necessity and you continue to use the dishonest dodge of the
>> straw-man error of reasoning. https://en.wikipedia.org/wiki/Straw_man
>>
>> It is true by logical necessity that any decider that decides to abort
>> the simulation of any input that would never otherwise halt has made a
>> correct not halting decision.
>
> You *CLAIM* it is a logical necessity, but the logic that says it is a
> necessity is flawed.
>
> The fact that a simple test of what happens shows different results is
> proof that the logc is flawed.

When the halt decider sees all of the execution of all of the code then
it can make a correct and consistent halting decision. Your scam is to
hide some of the execution from it and then claim an inconsistency.

The ruse basis of the scam is to see what H_Hat would actually do when
run directly we have to partially disable the halt decider.

That is very obviously proven to be pure bullshit** by the fact that we
can see exactly what H_Hat would actually do by simulating its Turing
machine description on an actual UTM that is not a halt decider.

** To anyone understanding that simulating the Turing machine
description of a TM by a UTM is computationally equivalent to executing
this TM directly.

When the exact same TMD of a TM is simulated by a UTM that is not a halt
decider never halts yet when this exact same TMD of a TM that is
simulated by a halt decider halts when the halt decider decides to stop
simulating it then we know with 100% perfectly logically justified
complete certainty that the decider decided correctly.

[Richard Damon]

I am using the results from what you claim is the halt decider running
fully and properly. Do you want to say that it return that H_Hat halted now?

>
> The ruse basis of the scam is to see what H_Hat would actually do when
> run directly we have to partially disable the halt decider.

HOW have I disabled the halt decider? I have used the exact result from
the halt decider that you have provided. (Since you haven't provided the
full code for the Halt Decider, I just abbreviate the trace through it,
but since I know the final outcome of it, that doesn't really matter.

What is your claim?

That the halt decider will give different answers to the same input
based on being called from different places?

That the halt decider might decide to NOT answer the question, and end
up in a state besides q.yes or q.no?

You have clearly stated many times that the result from your halt
decider is that Halts(H_Hat, H_Hat) is false.

>
> That is very obviously proven to be pure bullshit** by the fact that we
> can see exactly what H_Hat would actually do by simulating its Turing
> machine description on an actual UTM that is not a halt decider.

Which is exactly what I did. What part of the following trace do you
disagree with?

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

>

> ** To anyone understanding that simulating the Turing machine
> description of a TM by a UTM is computationally equivalent to executing
> this TM directly.

Yes, assuming the UTM is a correct UTM

>
> When the exact same TMD of a TM is simulated by a UTM that is not a halt
> decider never halts yet when this exact same TMD of a TM that is
> simulated by a halt decider halts when the halt decider decides to stop
> simulating it then we know with 100% perfectly logically justified
> complete certainty that the decider decided correctly.
>

Wait a minute, is this your UTM that is not a halt decider that if we
run Halts(H_Hat, H_Hat) in that the Halts calls will never return?

I.E. the one that shows that your Halt Decider can't exist in the world
of Turing Machines?

It appears that the world you have tried to create has a few logical
consistancy issues.

[Ben Bacarisse]

olcott <No...@NoWhere.com> writes:

> On 11/21/2020 10:18 AM, Ben Bacarisse wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> (1) It is known that the UTM simulation of a machine's Turing machine
>>> description is equivalent to directly executing it.
>>>
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Aborted = Halts(P, P);
>>> if (Aborted)
>>> HALT
>>> else
>>> HERE: goto HERE;
>>> }
>>>
>>>
>>> int main()
>>> {
>>> u32 P = (u32)H_Hat;
>>> Halts(P, P);
>>> HALT;
>>> }
>>>
>>> (2) It is known that the above code is infinitely recursive if Halts()
>>> acts like a UTM and simulates its input returning true if and only if
>>> its input halts.
>>
>> Right, but then Halts would not be a decider at all.
>
> That is the point of point(2)

So no claimed halt decider in sight yet. But you really should write
more clearly. (2) reads like a hypothetical when in fact it is the
description of what a function with a bad name does.

It should not be called Halts. It should be called something like
"Simulate" and it should not have a return value since the return value
can't convey any information (it either never returns of it returns
true).

I really hope you are not a programmer.

> Here Halts() merely invokes an ordinary UTM that itself never halts
> when its simulated input never halts. It is for the purpose of showing
> that the actual behavior of H_Hat really is infinitely recursive.


>
>> By the way, why do you call the returned value "Aborted" if it indicates
>> that the emulated computation is finite?
>
> I aim for people to get the gist of the idea before I delve into
> details that could be overwhelming.

Translation: you can't do the details so you just spray nonsense around
and wait for other people to wade throught it all tidying it up for you.

> The original idea was to comment out a single line of the halt decider
> to transform it into an ordinary UTM.
>
> 08 bool H(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 }

You should not leave code unposted.

>> And why is H_Hat named that
>> when it calls Halts and not a function named H?
>
> In the x86utm code Halts(main, NULL) is always automatically invoked
> thus giving is a global scope.

No answer.

> We need this extra feature only on the x86utm side so that the halt
> decider can see that H_Hat(H_Hat) is itself directly infinitely
> recursive.

No answer.

> When this is implemented as Turing machines all code is only simulated
> inside the halt decider adapted UTM, thus H_Hat(H_Hat) is itself also
> directly infinitely recursive.

No answer. I'll answer. You only have time to cut and paste so your
posts involve almost no thought. The details will be all over the
place.

>> And why does it not use
>> the returned value in the way the usual xxx_Hat construction would?
>
> I can only estimate what you mean here.

Amazing. You can't see you've flipped the way the xxx_Hat construction
works in Linz? Not that it matters because your point is trivial one
based on the badly named "Halts" never halting.

>> Yes, you can show a function that gets the right answer for the case
>> your describe. That is /always/ possible. But as soon as you provide
>> it, I will provide you with a case that that function will get wrong.
>
> Go ahead and try to do this.

There is no claimed halt decider here for me to do it with.

>> Are you deliberately saying "a correct halt decider" and not actually
>> showing it because you know that showing it (even in outline) will allow
>> a confounding example to be given?
>
> As I say in the thread heading (in this case) it is very obviously
> self-evident that the halt decider must return false.

No answer. For every single case, there is a decider. You should know
that. There is no single decider that works for every case. You should
know that too.

>> Are you deliberately the getting construction of H_Hat wrong?
>
> No and I believe that you know that it is not wrong.

You've got the clauses of the "if" the wrong way round. Mind you,
you've posted claimed "halting deciders" and claimed "non-halting"
deciders" so maybe you just cut and pasted the wrong thing. As I've
said before, you don't do details.

--
Ben.

[olcott]

On 11/21/2020 5:27 PM, Richard Damon wrote:
> On 11/21/20 5:49 PM, olcott wrote:
>> On 11/21/2020 4:27 PM, Richard Damon wrote:
>>> On 11/21/20 4:18 PM, olcott wrote:
>>>> On 11/21/2020 2:45 PM, Richard Damon wrote:
>>>
>>>>> Yes, If the halt decider desided that the input would not halt unless
>>>>> aborted, and then

This is where you say to partially disable the halt decider:

See your quote marked above

[Richard Damon]

On 11/21/20 6:35 PM, olcott wrote:
> On 11/21/2020 5:27 PM, Richard Damon wrote:
>> On 11/21/20 5:49 PM, olcott wrote:
>>> On 11/21/2020 4:27 PM, Richard Damon wrote:
>>>> On 11/21/20 4:18 PM, olcott wrote:
>>>>> On 11/21/2020 2:45 PM, Richard Damon wrote:
>>>>
>>>>>> Yes, If the halt decider desided that the input would not halt unless
>>>>>> aborted, and then
>
> This is where you say to partially disable the halt decider:
>
>>>>>> when that copy of the halt decider is changed to not
>>>>>> abort,
>
>

And if you look at that context, it is to perform the test by your
altered criteria, by first running it to get the answer, and then
running it again where it doesn't abort. It turns out, this is exactly
the same as running the machine under inspection as a real machine,

So in clear words. There are two tests to verify the results of

Halts(P, I)

the simplest is to just run P(I), which is basically running the same
tape into a working UTM.

The second method, to try to show if the 'needs' term was met, is to
make a modified version of the Halts program, which we will call
Halts_no_abort(), which is now admittedly a 'broken' halt detecter, as
it should halt if the program under test does halt, and will loop
forever if the program under test loop forever.

Given this function we can run Halts_no_abort(P, I) to test it.

The interesting thing is, Halts_no_abort is really just a UTM by a
different name, so this test is identical to the first test, which
actually makes sense.

Your alternative is to want to not only modify the Halts program making
this top level decision, but also to change anything that you think is a
version of it in P or I, which basically invaldates the test.

See my reply and actually READ what I said. The follow execution trace
is what we will get if we actually run H_Hat(H_Hat) either as a real
machine or in a working UTM. This is a valid test, You keep on snipping
this code without comment, which I take is an admission that you have no
defense for its claims:

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

Thus, Halts was wrong.

[olcott]

On 11/21/2020 5:30 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 11/21/2020 10:18 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> (1) It is known that the UTM simulation of a machine's Turing machine
>>>> description is equivalent to directly executing it.
>>>>
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Aborted = Halts(P, P);
>>>> if (Aborted)
>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>>
>>>> int main()
>>>> {
>>>> u32 P = (u32)H_Hat;
>>>> Halts(P, P);
>>>> HALT;
>>>> }
>>>>
>>>> (2) It is known that the above code is infinitely recursive if Halts()
>>>> acts like a UTM and simulates its input returning true if and only if
>>>> its input halts.
>>>
>>> Right, but then Halts would not be a decider at all.
>>
>> That is the point of point(2)
>
> So no claimed halt decider in sight yet. But you really should write
> more clearly.

The only way that I can improve the quality of my writing is to test to
see what things are understood and what things are not understood. All
of these same things have been totally obvious to me.

The reason that I went to V2 is to post this code.

>>> And why is H_Hat named that
>>> when it calls Halts and not a function named H?
>>
>> In the x86utm code Halts(main, NULL) is always automatically invoked
>> thus giving is a global scope.
>
> No answer.

H_Hat calls Halts and no longer calls H because as I have just said I
redefined H to have different functionality so it can no longer be
called H.

Halts has global scope and is invoked even when it is not called.
H was only invoked when it was called.

When we run H_Hat(H_Hat) in a UTM that has been adapted to become a
decider this decider aborts H_Hat(H_Hat) as infinitely recursive.

Halts also aborts H_Hat(H_Hat) invoked from main().

>> We need this extra feature only on the x86utm side so that the halt
>> decider can see that H_Hat(H_Hat) is itself directly infinitely
>> recursive.
>
> No answer.

ANSWER: H has different functionality than Halts so it has a new name.
ANSWER: H has different functionality than Halts so it has a new name.
ANSWER: H has different functionality than Halts so it has a new name.
ANSWER: H has different functionality than Halts so it has a new name.
ANSWER: H has different functionality than Halts so it has a new name.

>> When this is implemented as Turing machines all code is only simulated
>> inside the halt decider adapted UTM, thus H_Hat(H_Hat) is itself also
>> directly infinitely recursive.
>
> No answer. I'll answer. You only have time to cut and paste so your
> posts involve almost no thought. The details will be all over the
> place.
>
>>> And why does it not use
>>> the returned value in the way the usual xxx_Hat construction would?
>>
>> I can only estimate what you mean here.
>
> Amazing. You can't see you've flipped the way the xxx_Hat construction
> works in Linz?
> Not that it matters because your point is trivial one
> based on the badly named "Halts" never halting.

Did you already forget that you just read this:

08 bool H(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 }

>>> Yes, you can show a function that gets the right answer for the case
>>> your describe. That is /always/ possible. But as soon as you provide
>>> it, I will provide you with a case that that function will get wrong.
>>
>> Go ahead and try to do this.
>
> There is no claimed halt decider here for me to do it with.
>
>>> Are you deliberately saying "a correct halt decider" and not actually
>>> showing it because you know that showing it (even in outline) will allow
>>> a confounding example to be given?
>>
>> As I say in the thread heading (in this case) it is very obviously
>> self-evident that the halt decider must return false.
>
> No answer. For every single case, there is a decider. You should know
> that. There is no single decider that works for every case. You should
> know that too.

The point is that the above decider decides the above H_Hat correctly
The point is that the above decider decides the above H_Hat correctly
The point is that the above decider decides the above H_Hat correctly
The point is that the above decider decides the above H_Hat correctly
The point is that the above decider decides the above H_Hat correctly

>>> Are you deliberately the getting construction of H_Hat wrong?
>>
>> No and I believe that you know that it is not wrong.
>
> You've got the clauses of the "if" the wrong way round. Mind you,
> you've posted claimed "halting deciders" and claimed "non-halting"
> deciders" so maybe you just cut and pasted the wrong thing. As I've
> said before, you don't do details.
>

AH yes you are correct on this point after all.
AH yes you are correct on this point after all.
AH yes you are correct on this point after all.
AH yes you are correct on this point after all.
AH yes you are correct on this point after all.

[olcott]

On 11/21/2020 5:54 PM, Richard Damon wrote:
> On 11/21/20 6:35 PM, olcott wrote:
>> On 11/21/2020 5:27 PM, Richard Damon wrote:
>>> On 11/21/20 5:49 PM, olcott wrote:
>>>> On 11/21/2020 4:27 PM, Richard Damon wrote:
>>>>> On 11/21/20 4:18 PM, olcott wrote:
>>>>>> On 11/21/2020 2:45 PM, Richard Damon wrote:
>>>>>
>>>>>>> Yes, If the halt decider desided that the input would not halt unless
>>>>>>> aborted, and then
>>
>> This is where you say to partially disable the halt decider:
>>
>>>>>>> when that copy of the halt decider is changed to not
>>>>>>> abort,
>>
>>
> And if you look at that context, it is to perform the test by your
> altered criteria, by first running it to get the answer, and then
> running it again where it doesn't abort. It turns out, this is exactly
> the same as running the machine under inspection as a real machine,

copies are forbidden they diverge from the standard proofs
copies are forbidden they diverge from the standard proofs
copies are forbidden they diverge from the standard proofs
copies are forbidden they diverge from the standard proofs
copies are forbidden they diverge from the standard proofs

[Richard Damon]

So is changing the condition from the resutls of the actual machine to
be that the decider 'had to abort' the input.

By the test of running H_Hat(H_Hat) as an ACTUAL Turing Machine, or on a
WORKING UTM (where your Halts also works as described) we get the
following trace:

1) Enter H_Hat(H_Hat)
2) duplicate H_Hat
3) Enter Halts(H_Hat, H_Hat)
4) Halts does its decision and decides tht H_Hat is non-halting
5) Halts returns false to indicate non-halting
6) H_Hat goes to the else clause
7) H_Hat Halts.

Which shows that H_Hat(H_Hat) is a halting computation, and thus Halts
got it wrong.

PERIOD.

[Mike Terry]

I at least try to not repeat the same arguments over and over. :)

I was initially curious about what PO's argument would be, where exactly
he was going wrong etc., since on the face of it the HP proof in Linz (+
similar elsewhere) seems so simple that it's hard to imagine where it
might be challenged. After all, it amounts to just three or four key
points that need to be checked off to identify where the problem in an
H/H^ counter-example lies.

It's been clear now for a couple of weeks or so what's going on. From
my perspective, once PO admitted that the two Halts() functions (one in
H and one in H_Hat) return the same result when given the same input,
(and that result was "never halts",) it was all over bar the shouting.
All PO's subsequent repetitions about changing the question, redefining
halting, deleting lines out of Halts() etc. etc. etc. etc. are just the
flappings of a fish that's already in the net laying on the bottom of
the boat.

Others are continuing to debate with PO /why/ he is wrong, as though
they aim to /convince/ him and get him to admit that he made a mistake.
I consider that a total waste of time, and don't believe he will ever do
that. In the course of those debates it seems the same arguments are
repeated over and over and over, as though PO will suddenly say "ah,
yes! I get it now" on the 73rd repetition. :) Well, he won't. (And
vice versa, PO repeats his same claims over and over in response, but
here I think it is more his strategy of "always having the last post" in
a subthread, because he thinks that means he's "won the thread"!)

So the threads go on and on to no purpose that I can see - already
everybody but PO understands where his claims fail, and PO will never
admit any mistakes, so what's left to "argue" about?

It's not like anything here in Usenet has any consequence elsewhere - on
a scale of 1 to 100, PO's closeness to achieving his wider aims are
/still/ stuck on 1. At some point he must send his argument to a
reputed peer-reviewed publisher, at which point it will be thrown in the
bin, even if everybody here wrote him a letter of recommendation saying
he was a genius. The basic problem for him is that his arguments
themselves (based on his child-like first intuitions) are worthless.
It's really nothing to do with the way he /presents/ his ideas, which is
what /he/ believes is the problem.


Mike.

[olcott]

You are a liar.

[olcott]

You are glossing over key details:
(1) There is no H its functionality has been changed and it is now
called Halts. Halts() is the operating environment of every program
under test.

19 int main()
20 {
21 u32 P = (u32)H_Hat;
22 H_Hat(P, P);
23 HALT;
24 }

Line 22 is aborted by its operating environment halt decider.

01 void H_Hat(u32 P)
02 {
03 if (Halts(P, P))
04 HERE: goto HERE;
05 else
06 HALT
07 }

(2) The invocation of Halts() from H_Hat() never returns because H_Hat()
is either infinitely recursive or aborted because it is infinitely
recursive at its line 03.

> Others are continuing to debate with PO /why/ he is wrong, as though

Without bothering to pay attention to what he says, thereby making fools
of themselves.

> they aim to /convince/ him and get him to admit that he made a mistake.
> I consider that a total waste of time, and don't believe he will ever do
> that.  In the course of those debates it seems the same arguments are
> repeated over and over and over, as though PO will suddenly say "ah,
> yes!  I get it now" on the 73rd repetition.  :)  Well, he won't.  (And

The ONLY actual mistake that anyone ever caught were typos and using
terminology in a less than precisely accurate way.

APPARENTLY YOU DID NOT BOTHER TO NOTICE THAT THE HALT DECIDER WAS GIVEN
GLOBAL SCOPE.

When none of the execution of any of the user specified code is hidden
from the decider it can decide the not halting of line 22.

[Richard Damon]

Are you saying thet the Turing Machine for H_Hat, as describe by Linz
does NOT duplicate its input tape as its first step?

Now, in your x86 'equivalent' this is a fairly trivial operation, of
copying the value of the parameter P to the parameter I

Which actually is not technically a correct action if the machine Halts
is allowed to actually write back anything onto it input tapes.

Your whole 'equivalent' structure crumbles if any of the machines under
test use their tape for anything other than passing programs.

[Ben Bacarisse]

olcott <No...@NoWhere.com> writes:

> On 11/21/2020 5:30 PM, Ben Bacarisse wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 11/21/2020 10:18 AM, Ben Bacarisse wrote:

<cut>

>>>> And why is H_Hat named that
>>>> when it calls Halts and not a function named H?
>>>
>>> In the x86utm code Halts(main, NULL) is always automatically invoked
>>> thus giving is a global scope.
>>
>> No answer.
>
> H_Hat calls Halts and no longer calls H because as I have just said I
> redefined H to have different functionality so it can no longer be
> called H.
>
> Halts has global scope and is invoked even when it is not called. H
> was only invoked when it was called.
>
> When we run H_Hat(H_Hat) in a UTM that has been adapted to become a
> decider this decider aborts H_Hat(H_Hat) as infinitely recursive.
>
> Halts also aborts H_Hat(H_Hat) invoked from main().
>
>>> We need this extra feature only on the x86utm side so that the halt
>>> decider can see that H_Hat(H_Hat) is itself directly infinitely
>>> recursive.
>>
>> No answer.
>
> ANSWER: H has different functionality than Halts so it has a new name.
> ANSWER: H has different functionality than Halts so it has a new name.
> ANSWER: H has different functionality than Halts so it has a new name.
> ANSWER: H has different functionality than Halts so it has a new name.
> ANSWER: H has different functionality than Halts so it has a new name.

Amazingly, even written out lots of times, it is still not an answer!

Think I'm mad? Think I'm lying. Just go back and read the question
very carefully. It's a tiny point, but it's all part of your taking
shortcuts and not bothering about details.

And the you've posted yet another version, I see, so I won't pursue
this.

--
Ben.

[Richard Damon]

On 11/21/20 8:12 PM, olcott wrote:

> You are glossing over key details:
> (1) There is no H its functionality has been changed and it is now
> called Halts. Halts() is the operating environment of every program
> under test.
>

Which means that you are no longer anywhere near having an 'equivalent'
to the Turing Machines in Linz, or as described in the Halting Problem


Fine, just admit you are working on a different problem.

What you have made is NOT a Turing Machine that is a Halting Detector,
since if Halts is the operating environment it isn't available to be
embedded into Turing Machnes (or there true equivalent) and especially
not edited in the manner described in Linz.

You have somehow created a non-Turing method to let us seemingly call
this functionality.

Even more importantly, since your OS is the halt detector, your
environment no longer seems to support itself as at UTM, or at least
from your description, a UTM that can have your halt detector available
inside of it.

My key point here is from all you have said, your machine won't let me
run a program that runs forever, at least not in a program that want to
use a working Halt Detector.

[Mike Terry]

Those are just words you say without thinking through what they actually
mean for your argument. It's like when you discuss FOL and "say words"
like "I have enhanced the language by including a '|-' operator" without
having a clue what it would genuinely take to make that into a sensible
statement. It is literally just you trying out words that sound good
(to you) to see how people respond. (Part of your "fitness" algorithm,
I suppose.)

I could try to clarify with you what you are trying to say, becomming
part of your fitness filter, but to me your "key detail" is just more
fish flapping on the bottom of the boat, which is clearly not going to
have ANY effect on the fate of the fish. It really is just you "saying
words" to see what happens, and deserves no more response than that.

>
<.. snip ..>

>> Others are continuing to debate with PO /why/ he is wrong, as though
>
> Without bothering to pay attention to what he says, thereby making fools
> of themselves.

You are in no position to judge whether anyone is making a fool of
themselves. To do that, you would need to be on a similar or higher
intellectual level to those people.

>
>> they aim to /convince/ him and get him to admit that he made a
>> mistake. I consider that a total waste of time, and don't believe he
>> will ever do that. In the course of those debates it seems the same
>> arguments are repeated over and over and over, as though PO will
>> suddenly say "ah, yes! I get it now" on the 73rd repetition. :)
>> Well, he won't. (And
>
> The ONLY actual mistake that anyone ever caught were typos and using
> terminology in a less than precisely accurate way.

Hehe, that's what I was saying - you are not going to suddenly admit, or
even understand why you are wrong, just because the reason is repeated
to you 73 times. I don't think I've EVER seen you admit one of your
child-like intuitions was wrong. (Compare with the behaviour of actual
children, who come to see that their first intuitions missed all sorts
of important nuances, or were just plain wrong, and move on as they
develop and /learn/ more about the world.)

So maybe this seems like a stand-off to you?
- you believe you are right, and everybody else explaining
why you are wrong is a fool.
- everybody else (Malcolm possibly excepted) believes /you/
are a Deluded Dumbo - an obvious fool who also, for whatever
psychological reason, is unable to /see/ that he's fool.

The problem is it's YOU who wants to get something out of this, so such
a standoff is a TOTAL FAILURE for you. Nobody here /needs/ to convince
you that you're a fool or to get you to understand your mistakes,
whereas you /need/ to convince people that you're a genius. [So that
Doug Lenat will give you the job you want etc..]


Mike.

[olcott]

It is all explained in great depth here:
How does a halt decider with global scope decide H_Hat(H_Hat) correctly?

[olcott]

It would have been more clear if you asked the question this way:
Why did you not rename H_Hat when you changed the functionality of H?

I did not rename H_Hat because its functionality has not changed.

[olcott]

I am saying that is not the computation that I specified.

> Now, in your x86 'equivalent' this is a fairly trivial operation, of
> copying the value of the parameter P to the parameter I

It makes my proof diverge from its the stadard conventional form.

> Which actually is not technically a correct action if the machine Halts
> is allowed to actually write back anything onto it input tapes.

Where the Hell did you get that screwy bullshit from ?

> Your whole 'equivalent' structure crumbles if any of the machines under
> test use their tape for anything other than passing programs.

Where the Hell did you get that screwy bullshit from ?

You keep stating things like this dogmatically without any logical basis.

All the machines including H_Hat must be UTMs otherwise there is no such
thing as recursion.

[Richard Damon]

If you aren't doing that computation, how is the results of your
computation applicable to it?

>
>> Now, in your x86 'equivalent' this is a fairly trivial operation, of
>> copying the value of the parameter P to the parameter I
>
> It makes my proof diverge from its the stadard conventional form.

Since H^ in Linz begins with the copying, it sounds like YOUR system
diverges from the standard convential form.

>
>> Which actually is not technically a correct action if the machine Halts
>> is allowed to actually write back anything onto it input tapes.
>
> Where the Hell did you get that screwy bullshit from ?

The ONLY requirements put on the halt decider H are:
1) That it is a Turing Machine
2) That it meets the requirments of a decider (halts in one of the
defined answer states in finite time)
3) That its answer is correct, for ALL possible inputs.
4) That its input tape is the necessary and sufficent information for
the decision, namely a representation of the Turing Machine being
decided and a copy of the input for that machine.

Turing Machines are allowed to modify the tape they are given, therefore
it is allowed that H modify the tape it is provided. It doesn't need to,
but it is allowed to. Your proposed implementation happens to not do
this (as far as you have described) but that doesn't mean that other
proposed implementations can't do it.

>
>> Your whole 'equivalent' structure crumbles if any of the machines under
>> test use their tape for anything other than passing programs.
>
> Where the Hell did you get that screwy bullshit from ?

The basic definition of a Turing Machine. Your input tapes in your model
are only programs and read only. That just happens to remove a large
part of the functionality of a Turing Machine.

>
> You keep stating things like this dogmatically without any logical basis.
>
> All the machines including H_Hat must be UTMs otherwise there is no such
> thing as recursion.
>

Turing Machines don't directly support recursion of code, because they
don't directly support the concept of a general 'call' (How would you
express a call/return in a Turing State Machine). Turing Machines CAN
represent recursive computations by using their tape.

Yes, using a UTM, you can simulate recursion by having your UTM run
another program with a UTM, but then all that operation is actually
running on the tape, not in the machine itself, the actual machine
running is just the first UTM.

[olcott]

I have three other textbook proofs and none of them specify copying the
input.

>>
>>> Which actually is not technically a correct action if the machine Halts
>>> is allowed to actually write back anything onto it input tapes.
>>
>> Where the Hell did you get that screwy bullshit from ?
>
> The ONLY requirements put on the halt decider H are:
> 1) That it is a Turing Machine
> 2) That it meets the requirments of a decider (halts in one of the
> defined answer states in finite time)
> 3) That its answer is correct, for ALL possible inputs.
> 4) That its input tape is the necessary and sufficent information for
> the decision, namely a representation of the Turing Machine being
> decided and a copy of the input for that machine.

Good all of those seem OK.

> Turing Machines are allowed to modify the tape they are given, therefore
> it is allowed that H modify the tape it is provided. It doesn't need to,

There is no H, there is only Halts that is automatically invoked on
every input that it simulated.

> but it is allowed to. Your proposed implementation happens to not do
> this (as far as you have described) but that doesn't mean that other
> proposed implementations can't do it.
>
>>
>>> Your whole 'equivalent' structure crumbles if any of the machines under
>>> test use their tape for anything other than passing programs.
>>
>> Where the Hell did you get that screwy bullshit from ?
>
> The basic definition of a Turing Machine. Your input tapes in your model
> are only programs and read only. That just happens to remove a large
> part of the functionality of a Turing Machine.

There is no actual read only input only tape in any Turing Machine model.

>>
>> You keep stating things like this dogmatically without any logical basis.
>>
>> All the machines including H_Hat must be UTMs otherwise there is no such
>> thing as recursion.
>>
>
> Turing Machines don't directly support recursion of code, because they
> don't directly support the concept of a general 'call' (How would you
> express a call/return in a Turing State Machine). Turing Machines CAN
> represent recursive computations by using their tape.
>
> Yes, using a UTM, you can simulate recursion by having your UTM run
> another program with a UTM, but then all that operation is actually
> running on the tape, not in the machine itself, the actual machine
> running is just the first UTM.
>

None-the-less it is common knowledge in computer science that the
simulation of the TMD of a TM is computationally equivalent to the
direct execution of this TM.

Also to maintain equivalent computations between the x86utm version and
the Turing machine version H_Hat must be defined as a UTM that simulates
its own TMD.

[Richard Damon]

From the web page you like to quote:
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

From H' we construct another Turing machine II. This new machine
takes as input WM, copies it, and then behaves exactly like H'.

This is near the bottom of page 319.

>
>>>
>>>> Which actually is not technically a correct action if the machine Halts
>>>> is allowed to actually write back anything onto it input tapes.
>>>
>>> Where the Hell did you get that screwy bullshit from ?
>>
>> The ONLY requirements put on the halt decider H are:
>> 1) That it is a Turing Machine
>> 2) That it meets the requirments of a decider (halts in one of the
>> defined answer states in finite time)
>> 3) That its answer is correct, for ALL possible inputs.
>> 4) That its input tape is the necessary and sufficent information for
>> the decision, namely a representation of the Turing Machine being
>> decided and a copy of the input for that machine.
>
> Good all of those seem OK.
>
>> Turing Machines are allowed to modify the tape they are given, therefore
>> it is allowed that H modify the tape it is provided. It doesn't need to,
>
> There is no H, there is only Halts that is automatically invoked on
> every input that it simulated.

I will admit some typos here, in the Linz proof it is called H.

>
>> but it is allowed to. Your proposed implementation happens to not do
>> this (as far as you have described) but that doesn't mean that other
>> proposed implementations can't do it.
>>
>>>
>>>> Your whole 'equivalent' structure crumbles if any of the machines under
>>>> test use their tape for anything other than passing programs.
>>>
>>> Where the Hell did you get that screwy bullshit from ?
>>
>> The basic definition of a Turing Machine. Your input tapes in your model
>> are only programs and read only. That just happens to remove a large
>> part of the functionality of a Turing Machine.
>
> There is no actual read only input only tape in any Turing Machine model.

BUT, your model of passing the address of memory, and letting the copy
of the tape share the same actual memory as the original code is only
valid if the tape is never written to, or else any write to the tape
would change the machine being executed, not just the tape.

>
>>>
>>> You keep stating things like this dogmatically without any logical
>>> basis.
>>>
>>> All the machines including H_Hat must be UTMs otherwise there is no such
>>> thing as recursion.
>>>
>>
>> Turing Machines don't directly support recursion of code, because they
>> don't directly support the concept of a general 'call' (How would you
>> express a call/return in a Turing State Machine). Turing Machines CAN
>> represent recursive computations by using their tape.
>>
>> Yes, using a UTM, you can simulate recursion by having your UTM run
>> another program with a UTM, but then all that operation is actually
>> running on the tape, not in the machine itself, the actual machine
>> running is just the first UTM.
>>
>
> None-the-less it is common knowledge in computer science that the
> simulation of the TMD of a TM is computationally equivalent to the
> direct execution of this TM.

Yes, if you have a PROPER equivalence

>
> Also to maintain equivalent computations between the x86utm version and
> the Turing machine version H_Hat must be defined as a UTM that simulates
> its own TMD.
>

That is nonsense. H_Hat has NO need to actualy simulate its input. The
decision to do this is a possible implementation of the Halt Decider, in
which case it is the responsibility of the Halting Decider to limit the
execution of the UTM to finite time. The infinite execution you seem to
be detecting isn't an issue of H_Hat, it is a failure of the Halting
Detector to meet its requirements.

Somehow you have the idea that Halt Decidign REQUIRES being based on
brute force emulation with a UTM.

[olcott]

On 11/20/2020 9:30 PM, Mike Terry wrote:

> On 21/11/2020 02:45, olcott wrote:
>> (1) It is known that the UTM simulation of a machine's Turing machine
>> description is equivalent to directly executing it.
>

> UTM simulation enumerates the steps of the TM calculation.
> So, yes, in that sense.

>
>>
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Aborted = Halts(P, P);
>>   if (Aborted)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>   u32 P = (u32)H_Hat;
>>   Halts(P, P);
>>   HALT;
>> }
>>
>> (2) It is known that the above code is infinitely recursive if Halts()
>> acts like a UTM and simulates its input returning true if and only if
>> its input halts.
>

> Yes, we have infinite "recursive emulation".
>
>>
>> (3) On the basis of (1) and (2) It is known that a correct halt decider
>> must return false.
>
> There is no such thing as a "correct halt decider" for all inputs, but
> input (H_Hat,H_Hat) is non-halting, assuming your Halts() is as
> described.  This is all baby stuff.  [So the correct halting decision
> for the input is non-halting].
>
> [Just in case you're considering this - of course if you change your
> spec for Halts to make a new function Halts2, then that also changes the
> H_Hat machine to H_Hat2, and the *new* input (H_Hat2,H_Hat2) might be
> halting or non-halting, depending on the change.  This is also baby
> stuff...]
>
>
> Regards,
> Mike.
>

Machines of the pattern of H_Hat can be generally decided to be
infinitely recursive whenever they invoke the same function from the
same machine address and there are no intervening condition branch
instructions in-between that would break this cycle of infinite recursion:

// call to Halts from H_Hat
[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

// call to Halts from H_Hat
[00000503](05) e86ffeffff call 00000377

All of the details of this analysis are shown here:

On Sunday, November 22, 2020 at 7:24:48 PM UTC-6, olcott wrote:
[It is known that a correct halt decider must return false (in this
case)[V4](Linz)]
https://groups.google.com/g/comp.theory/c/aiXoRwqxJgE/m/2GlNMjitAAAJ

[Richard Damon]

The fundamental flaw in the argument is that the infinite recursion
isn't in the specific code of the machine H_Hat, but in the choice of
implementation of the Halt Decider.

In fact, if you look at the structure of H_Hat as a Turing Machine, the
machine itself is not recursive. The algorithm that H choose was
recursive, but not the machine.

Yes, the fact that the problem has a recursive nature does give us
difficulties in finding an answer (and the exact way the recursion was
done says their can't be a right answer), but this form of recursion is
important to mathematics and computer science.

Without recursive definitions, much of what is know about math would not
be know. Heck, without recursion it is hard to define the basics of the
Natural Numbers, try it.

The fundamental principal of even the wider halting problem is that to
build an algorithm to decide the halting nature of a machine, you need
to run that algorithm on a 'more powerful' machine. (This is needed to
break the Linz like contradiction). Thus, since regular expressions are
not 'Turing Complete' in capability, you could possible write a Halt
Decider for a regular expression on a von Neumann machine, since it is
more powerful (and thus said algorithm could not be embedded into the
regular expression),

The problem we run into then is that for Turing Machines and their
computational equivalences, there is no 'more powerful' platform that we
know of to put the halting decider on.

This shows up interestingly in your recent change to your Turing Machine
emulator by adding the Halt Detector to the OS, so that you can restrict
the Machines it can run to be less than Turing Complete, but your Halt
Decider links up to that to wide ability, to make it more capable than
other programs that want to use it.

This just shows up in your machine giving wrong answer when compared to
running as Actual Turing Machines.

[olcott]

This definition of a halt decider allows utterly free reign in
specifying the ⊢* state transitions from H.0 to H.yes or H.no (the final
states of H).

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)

Ĥ.q0 wM ⊢ H.q0 wM wM ⊢* H.yes ∞
Ĥ.q0 wM ⊢ H.q0 wM wM ⊢* H.no

void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (!Input_Halts)

HALT
else
HERE: goto HERE;
}

Thus any set of state transitions from H.q0 to either H.yes or H.no that
meets these specs on Ĥ(Ĥ) does correctly refute Linz.

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

[Richard Damon]

Yes, you have free reign as to what to put there, but you also have to
make the results match the requirements. That is to tough part.

Yes, you are allowed to put an infinite recursion into your decider, as
long as you do something to return the result in finite time. It is the
deciders job to be able to answer for ANY input in finite time. And it
isn't the correct answer to say the program is non-halting if the reason
it wouldn't halt is because the decider won't.

>
>     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)
>
> Ĥ.q0 wM ⊢ H.q0  wM  wM ⊢* H.yes  ∞
> Ĥ.q0 wM ⊢ H.q0  wM  wM ⊢* H.no
>
> void H_Hat(u32 P)
> {
>   u32 Input_Halts = H(P, P);
>   if (!Input_Halts)
>     HALT
>   else
>     HERE: goto HERE;
> }
>
> Thus any set of state transitions from H.q0 to either H.yes or H.no that
> meets these specs on Ĥ(Ĥ) does correctly refute Linz.

But, when you decided that H_Hat(H_Hat) does not stop, and thus got to
H.no, then H_Hat will halt, so you were wrong. If you happend to decide
that H_Hat(H_Hat) would halt, by going to H.yes, then H_Hat will go into
an infinite loop and thus you were wrong again. If you do not get to
either H.no or H.yes you have failed to met your requirements, and thus
you were wrong. It the old case of Head you lose, Tails you lose too.

The problem isn't to just come up with A decision, but the CORRECT
decision. If any old answer was acceptable, it wouldn't be much of a
problem.