Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Re: Black box halt decider is NOT a partial decider [ H(P,P)==0 is correct ]

1 view
Skip to first unread message

olcott

unread,
Jul 26, 2021, 10:32:56 AM7/26/21
to
On 7/25/2021 7:08 PM, Mike Terry wrote:
> On 25/07/2021 23:42, Ben Bacarisse wrote:
>> Mike Terry <news.dead.p...@darjeeling.plus.com> writes:
>>
>>> On 25/07/2021 21:28, Mike Terry wrote:
>>> Pressed Send too soon. :(
>>>> On 25/07/2021 18:40, Malcolm McLean wrote:
>>>>> On Sunday, 25 July 2021 at 17:14:20 UTC+1, Mike Terry wrote:
>>>>>>
>>>>>> I think this is all a bit like Malcolm suggesting that PO is raising
>>>>>> "interesting ideas" that might be useful with more study, or that
>>>>>> some
>>>>>> basic idea of PO's is "really quite clever...". It is NOT. PO has no
>>>>>> incling of those possibilities and really no interest in them. He is
>>>>>> simply saying things he naively thinks are true, without any logical
>>>>>> reasoning going on. No cleverness at all. He is not "performing a
>>>>>> magic trick", where he will pull a rabit out of a hat - he genuinely
>>>>>> believes he is refuting the Linz proof, no tricks. Pretending
>>>>>> otherwise
>>>>>> may be being nice to PO, making him feel better, but is ultimately
>>>>>> unhelpful IMO. I'd say it seems like "dishonest niceness" to me. (But
>>>>>> maybe Malcolm really thinks PO is producing worthwhile results, or
>>>>>> is on
>>>>>> the path to that, in which case it's just being "actually nice"!)
>>>>>>
>>>>> I've always been very clear that I haven't yet seen from PO
>>>>> anything that
>>>>> constitutes a refutation of Linz. However when we have, for
>>>>> example, the
>>>>> "H is the operating system" ruse, I do tend to say "that's a clever
>>>>> cheat"
>>>>> rather than "how could you make such a simple and obvious error?".
>>>>> Largely because it's a nicer way of conveying essentially the same
>>>>> information.
>>>>>
>>>>> I did say recently that PO had constructed his own paradox. It's
>>>>> this. If
>>>>> H is  simulating halt decider, and is called on H, it creates a
>>>>> series of
>>>>> nested recursions. If it doesn't detect the situation, it never
>>>>> halts. If
>>>>> it does detect the situation and terminates the simulations, it halts.
>>>>> However if it halts, the nested recursions were not infinite.
>>>> Right, that's a bit like something I pointed out to PO last year.  Such
>>>> an emulation-based (putative) decider may have a number of tests in
>>>> its stepping loop.  Some may be /sound/, like a properly implemented
>>>> tight-loop test, or a test might be unsound in that it incorrectly
>>>> decides halting for a non-halting input or vice-versa.  The sound tests
>>>> might match and make correct decisions when examining particular
>>>> inputs, BUT it's sort of weird that the when H examines (P,P), the
>>>> /sound/ tests
>>>> "mysteriously" never ever match!  The only tests that will ever
>>>> match are those that are unsound...  If there are /only/ sound tests
>>>> in the
>>>> loop, none of them will match and H(P,P) will never make its
>>>> decision and halt!  Of course that would disqualify H as a decider.
>>>> This applies for PO and his "detecting infinite recursions" test,
>>>> however much he believes his test to be sound...  I've told him that
>>>> a reviewer will
>>>
>>> ...expect to see a /proof/ of the soundness of any test in his loop,
>>> if he's going to expect them to take matching of the test as
>>> /evidence/ of halting status.  (Of course PO can't deliver such a
>>> proof.)
>>
>> Right.  And very well put.  But he's abandoned almost all pretence at
>> dealing with halting.  What makes a sound test has been defined to be
>> what H does.  This is the "adapted" criterion for halting.  Not halting,
>> but whatever it is he chooses to put into H.  When he says that its
>> "impossibly incorrect" (if that's the term, I try to forget such things)
>> this is what he means.
>
> Perhaps the root problem is that PO REALLY REALLY REALLY believes his
> "infinite recursive behaviour" test is sound, for whatever reason.  I
> mean that his intuition that it is sound is AS STRONG OR STRONGER than
> his recent understanding that a machine which runs and transitions into
> a halt state is a halting computation.
>
> So he has an example where both
> (a) the computation P(P) undeniably reaches a halt state (so is halting)
> (b) his test in H(P,P) matches the computation when it runs!!!!!!! so it
>     is UNDENIABLY "exhibiting infinite recursion" (WTM)
>
> Both principles are equally believed by PO, so both conclusions MUST be
> correct!  A "paradox"!!!  P(P) halts, and yet it exhibits infinite
> recursion and so "cannot halt", even though it does.  What to do?!
>

You have the paradox incorrectly. While the input to H(P,P) is simulated
in pure simulation mode it cannot possibly ever reach a final state thus
conclusively proving that this input never halts.

Anyone bothering to carefully examine these things must necessarily
conclude that the pure simulation of the input to H(P,P) cannot possibly
reach its final state. Anyone not bothering to carefully examine these
things is a liar and a cheat.

When H recognizes this infinite behavior pattern and stops simulating
its input, this input still never reaches its final state, thus never
halts.

Many thanks to André G. Isaak for pointing out the proper and best
definition of halting we no longer have the ambiguity between halting
(reaching its final state) and stopping running (simulation aborted).

> For 99.99999% of people, there would be no dilemma here.  Presented with
> (a), which is /the definition/ of halting as used in HP proofs, and
> given that (b) was an intuition for which they had /no proof/ of its
> correctness, the conclusion would be: (a) is correct, so the test in (b)
> hasn't worked for some reason.  It is unsound.
>
> And 99.3% of those people would be capable of resolving this - they'd
> track through the computation in (a), using it to pin down where they
> went astray in intuition (b).  End of story.
>
> All his recent posts seem to focus on a mixture of one or two totally
> banal claims (along the lines of "a computation which never reaches one
> of its halt states is a non-halting computation" (LOL), followed by a
> bogus claim like "my trace UNDENIABLY proves that the test in (b)
> MATCHED!!!!!! and any software engineer who understands x86 will confirm
> this - THEREFORE non-halting behaviour HAS been detected so non-halting
> is the right answer."  (Well, that's what you said with "halting is what
> H does", and I've rephrased it for you in 200 words for no real benefit
> hehe.)
>
> I don't see any more than that going on - an absolute faith in the
> correctness of his unsound (b) test, although he must realise he can't
> prove it is sound.  I guess he really thinks reviewers will accept it as
> obvious, and everybody here is just stupid or deliberately lying due to
> being "in rebuttal mode".
>
> Mike.
>


--
Copyright 2021 Pete Olcott

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

olcott

unread,
Jul 26, 2021, 10:38:06 AM7/26/21
to
While the input to H(P,P) is simulated in pure simulation mode it cannot
possibly ever reach a final state thus conclusively proving that this
input never halts.

Anyone bothering to carefully examine these things must necessarily
conclude that the pure simulation of the input to H(P,P) cannot possibly
reach its final state. Anyone not bothering to carefully examine these
things is a liar and a cheat.

When H recognizes this infinite behavior pattern and stops simulating
its input, this input still never reaches its final state, thus never halts.

Many thanks to André G. Isaak for pointing out the proper and best
definition of halting we no longer have the ambiguity between halting
(reaching its final state) and stopping running (simulation aborted).


olcott

unread,
Jul 26, 2021, 10:46:35 AM7/26/21
to
While the input to H(P,P) is simulated in pure simulation mode it cannot
possibly ever reach a final state thus conclusively proving that this
input never halts.

Anyone bothering to carefully examine these things must necessarily
conclude that the pure simulation of the input to H(P,P) cannot possibly
reach its final state. Anyone not bothering to carefully examine these
things is a liar and a cheat.

_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H(P,P)
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c36
[00000c36][002117ca][002117ce] 55 push ebp
[00000c37][002117ca][002117ce] 8bec mov ebp,esp
[00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
[00000c3c][002117c6][00000c36] 50 push eax // push P
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx // push P
[00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

[00000c36][0025c1f2][0025c1f6] 55 push ebp
[00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
[00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
[00000c3c][0025c1ee][00000c36] 50 push eax // push P
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx // push P
[00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

That you say the above is not proof that the input to H(P,P) cannot
possibly reach its final state of 0xc50 while H is in pure simulation
mode seems to be either gross ignorance or flat out dishonestly.

You have proven that you can do much better than this, what gives?


>>
>> Mike.
>>
>>>
>>> I do wonder if this could form the nucleus of an another proof that
>>> halting is undecidable.

olcott

unread,
Jul 28, 2021, 6:08:41 PM7/28/21
to
On 7/26/2021 6:48 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> While the input to H(P,P) is simulated in pure simulation mode it
>> cannot possibly ever reach a final state thus conclusively proving
>> that this input never halts.
>
> Who cares? H(P,P) == 0 and P(P) halts so H is not a halt decider. You
> once claimed something "interesting" i.e. that you had
>
> "encoded all of the ... Linz Turing machine H that correctly decides
> halting for its fully encoded input pair: (Ĥ, Ĥ)"
>
> and you insisted that
>
> "Everyone has claimed that H on input pair (Ĥ, Ĥ) meeting the Linz
> specs does not exist. I now have a fully encoded pair of Turing
> Machines H / Ĥ proving them wrong."
>
> Does that "Linz Turing machine H" accept or reject the "fully encoded
> input pair (H^, H^)", and what is the halting status if H^ when given H^
> (encoded)? If, as now, H rejects (H^, H^) but H^ halts when given H^
> then there was never anything interesting about what you were claiming,
> but it was at least about Turing machines and the proof you have fixated
> on.
>
> But you also said your TMs H and H^ are "exactly and precisely as in
> Linz", so really either
>
> (1) H rejects (H^, H^) and H^ does not halt on input H^, or
> (2) H accepts (H^, H^) and H^ halts on input H^
>
> should be the case. So, come clean. Which was the case back then:
>
> (1) H rejects (H^, H^) and H^ does not halt in input H^, or
> (2) H accepts (H^, H^) and H^ halts on input H^, or
> (3) H rejects (H^, H^) and H^ halts on input H^.
>
> Without the comfort blanket of your huge pile of junk x86 code, I
> suspect you won't dare say.
>

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

When we apply Ĥ to its own TM description ⟨Ĥ⟩

While the simulating halt decider at Ĥ.qx remains in pure simulator mode
it specifies a never ending cycle from qx to q0.

As you already (generically) agreed:

On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> Truism:
>> Every simulation that would never stop unless Halts() stops
>> it at some point specifies infinite execution.
>
> Any algorithm that implements this truism is, of course, a halting
> decider.

Therefore: when the simulation of the input to Ĥ.qx must be aborted to
prevent the infinite execution of Ĥ applied to ⟨Ĥ⟩ this proves that the
input to Ĥ.qx never halts.

olcott

unread,
Jul 29, 2021, 10:05:07 PM7/29/21
to
On 7/29/2021 8:18 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
> (I answered your other belligerent reply before I read this.)
>
>> I would prefer to move away from division and animosity to achieve an
>> honest dialogue striving for mutual agreement, are you game?
>
> Sure. Here are some other things about which I would like to seek
> mutual agreement:
>
> (1) A TM, M, halts on input s if the sequence of machine configurations
> generated by M's state transition function, along with the input s,
> is finite.

I like André's reaches one of its own finite states better.
Is this OK with you?

> M is said to accept s if the final state is an accepting
> state. Otherwise M is said to reject the input s.
>
Yes

> (2) A halt decider is a TM, D, that accepts only and all inputs of the
> form <m,s> where m encodes a TM that halts on input s. D rejects
> all others inputs.
Yes with André's definition of halting.
Is this OK with you?

>
> (3) Did you have, back in Dec 2018, a Turing machine (as the term is
> defined in any of the usual textbooks) that you called H to which
> Linz's "hat" constriction could be applied to get another TM, H^?

I never had a Turing machine. I had what I still consider to be
computationally equivalent to the key partial halt deciding aspect of
the Linz H correctly deciding the the simplest possible single example
of the Linz Ĥ (no copying of the input) as never halting. The 2018
version was encoded to correctly recognize one instance of infinitely
nested simulation. It was encoded in nearly complete C.

>
> (4) Using [X] to denote the string that encodes TM X, did your Dec 2018
> H^ halt on input [H^]?
>
> (5) Did your Dec 2018 H accept or reject the string <[H^],[H^]>?
>
> Of course, if your answer to (3) is no, then (4) and (5) are irrelevant.
>
> Either way you should post what you had in Dec 2018. Your conflicting
> claims about what it was are one of the biggest obstacles to honest
> dialogue. With what you had out in the open, we could get some
> agreement on modified versions of (4) and (5).
>

It is on a single piece of hand-written paper. I don't think that I ever
scanned it.

olcott

unread,
Jul 29, 2021, 10:28:56 PM7/29/21
to
On 7/29/2021 8:52 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>>>>>>> If you didn't understand the question, I might be able to explain it
>>>>>>> some other way. If you are just avoiding answering it, then just say so
>>>>>>> and I'll stop asking.
>>>>>>
>>>>>> I totally ignored the convoluted mess of your question...
>>>>> Would you like to know what I was asking, or do you just want to keep
>>>>> posting stuff for your entertainment? It's simpler for me if you are
>>>>> not interested in knowing what I was asking, and I think it helps other
>>>>> readers form an opinion as well.
>>>>
>>>> It was just another one of your endless dishonest dodges as can be
>>>> seen above This quote proves you are clueless: "H rejects (H^, H^)"
>>> You don't want to answer the question it seems. OK.
>>>
>>>> Ĥ( ⟨Ĥ⟩ ) only stops because its simulating halt decider stops it at
>>>> some point.
>>> But you will answer part of it. You are saying that case (1) does not
>>> apply.
>>
>> None of the cases apply because you are not following the last step of
>> the proof where no H is involved.

>> Can we start talking about the last step of the actual proof?
>
> I am trying to. The last step is what Ĥ(⟨Ĥ⟩) does:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* ...
>
> As you can see, that depends on the answer to my question. The
> configurations that follow that last ⊢* are those determined by what
> that part of Ĥ that is identical to H does on input (⟨Ĥ⟩, ⟨Ĥ⟩).
>
> So does the ... lead to Ĥ.qn or Ĥ.qy? If you don't like my wording
> using H, does the part of Ĥ that is identical to H transition to Ĥ.qn
> or Ĥ.qy?
>

Ĥ( ⟨Ĥ⟩ ) specifies an infinite cycle from Ĥ.qx to Ĥ.q0 all the time that
Ĥ.qx remains a pure simulator of its input.

This is the same criteria that both you and André agreed to:
Every simulation that would never stop unless its simulating halt
decider stops it at some point specifies infinite execution. This
remains true for: Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩)

Ĥ( ⟨Ĥ⟩ ) only stops because its simulating halt decider stops it at some
point.

This is very difficult and totally counter-intuitive yet:
This is very difficult and totally counter-intuitive yet:
This is very difficult and totally counter-intuitive yet:
This is very difficult and totally counter-intuitive yet:

The above really seems to prove that the halt decider at Ĥ.qx does
correctly decide that its input never halts even when its input
contradicts this by transitioning to Ĥ.qn and halting.

It really really seems to be a contradiction and wrong, yet when we
really really carefully study it, it really really seems to not be wrong.

When the halt decider correctly decides that its input never halts and
then this input halts we have a paradox and not an actual contradiction.

olcott

unread,
Jul 30, 2021, 10:35:36 AM7/30/21
to
On 7/30/2021 6:00 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/29/2021 8:18 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>> (I answered your other belligerent reply before I read this.)
>>>
>>>> I would prefer to move away from division and animosity to achieve an
>>>> honest dialogue striving for mutual agreement, are you game?
>>> Sure. Here are some other things about which I would like to seek
>>> mutual agreement:
>>> (1) A TM, M, halts on input s if the sequence of machine configurations
>>> generated by M's state transition function, along with the input s,
>>> is finite.
>>
>> I like André's reaches one of its own finite states better.
>> Is this OK with you?
>
> What you say here is too vague. If you can write it clearly and
> formally, I'm sure we could agree on it, but I suspect you can't. In
> the spirit of reaching an agreement, is there anything you object to in
> my definition?
>

Your definition seems to be ambiguous when the simulation of a
computation has been aborted, André's definition is not ambiguous in
this case.

The input to H(P,P) cannot possibly ever reach its final state whether
or not its simulation is aborted.

>>> M is said to accept s if the final state is an accepting
>>> state. Otherwise M is said to reject the input s.
>>>
>> Yes
>>
>>> (2) A halt decider is a TM, D, that accepts only and all inputs of the
>>> form <m,s> where m encodes a TM that halts on input s. D rejects
>>> all others inputs.
>>
>> Yes with André's definition of halting.
>> Is this OK with you?
>
> Not unless you can write it clearly, no.
We can work on this.

The input to my partial halt decider is always a complete function
compiled from C and complete functions always have the explicit final
state of their last address.

>>> (3) Did you have, back in Dec 2018, a Turing machine (as the term is
>>> defined in any of the usual textbooks) that you called H to which
>>> Linz's "hat" constriction could be applied to get another TM, H^?
>>
>> I never had a Turing machine.
>
> OK, thanks. That's clear.
>
>> It was encoded in nearly complete C.
>
> This raises lots of questions:
>
> (3a) What are "the exact TMD instructions of the Linz Turing machine H"
> that you had encoded by Dec 14th in relation to this C code?
>

Like I said I did not have a Turing Machine.

> (3b) What does "I provide the exact ⊢* wildcard states after the Linz
> H.q0 and after Ĥ.qx ... showing exactly how the actual Linz H would
> correctly decide the actual Linz (Ĥ, Ĥ)" mean for C code?
>

the proof ...is so short and simple that
it may be of interest to casual readers.
The version below uses CPL...

rec routine P
§L:if T[P] go to L
Return §

Strachey, C 1965. An impossible program The Computer Journal, Volume 7,
Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

In the same way that Strachey claims that his little CPL program sums up
the entire proof my premise is that this C code sums up the entire proof.

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

What I had in 2018 was a crude way that code determined that the above
does specify infinitely nested simulation.
"the exact ⊢* wildcard states" refers to this code.

> Given that you had C code, the "UTM in C++" that you were writing that
> would allow you to "execute H on the input pair: (Ĥ, Ĥ)" is a C
> interpreter.
>

It was not a C interpreter. It is an x86 emulator.

> (3c) Did you really think you could write a C interpreter in "a week or
> two"?
>

What I thought that I could do in a week or two was write a very simple
virtual machine language lacking all high level control flow structure.
Since I have done this before in two weeks I new that I could do it again.

> (3d) Why write an interpreter when C code is better compiled and a
> debugger can then be used to give any required level of detail
> about the execution?
>

I never wrote a C interpreter. I never intended to write a C
interpreter. The initial idea was to write a compiler for a tiny subset
of C that is compiled into a very simple virtual machine language.

> In the spirit of mutual understanding, I hope you can see that these
> mysterious quotes will have led everyone away from the truth (that you
> had C code) while re-forcing the mistaken impression that you had what
> you had said you had: an actual Turing machine.
>
>>> (4) Using [X] to denote the string that encodes TM X, did your Dec 2018
>>> H^ halt on input [H^]?
>>> (5) Did your Dec 2018 H accept or reject the string <[H^],[H^]>?
>>> Of course, if your answer to (3) is no, then (4) and (5) are irrelevant.
>>> Either way you should post what you had in Dec 2018. Your conflicting
>>> claims about what it was are one of the biggest obstacles to honest
>>> dialogue. With what you had out in the open, we could get some
>>> agreement on modified versions of (4) and (5).
>
> These become
>
> (4) Did your Dec 2018 C code for H^ halt on H^?
>

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

What I had in 2018 was a crude way that code determined that the above
does specify infinitely nested simulation. I was only concerned with
H(P,P) where P is always aborted and can't ever possibly halt.

> (5) You said you had "an H that decides (Ĥ, Ĥ)". What decision did your
> Dec 2018 code come to about "(Ĥ, Ĥ)"?
>

The 2018 version Halts(H_Hat, H_Hat)==0 in the exact same way that
H(P,P)==0 now except that the never halting criteria is much more
elaborate. The initial criteria was very crude.

>> It is on a single piece of hand-written paper. I don't think that I
>> ever scanned it.
>
> Unless you post it, we can't reach a mutual understanding about your
> claim to have something that everyone else says is impossible. Maybe
> you just had some C that does something entirely possible and
> unsurprising. That is certainly the case now.
>

It is what I have now that counts. What I had years ago has been
superseded by newer technology.

olcott

unread,
Jul 30, 2021, 10:54:22 AM7/30/21
to
> Again, you state something trivial and avoid the question. As far as I
> know, H is not a pure simulator (in your confusing wording it's a
> simulator for a while and then it isn't).
>

When it is stipulated that all the sides of a triangle have the same
length then it is logically entailed that this triangle is an
equilateral triangle. There is no leeway allowed to disagree with the
premise in stipulative definitions or geometric "givens".

When it is stipulated that Ĥ.qx is a UTM then it is logically entailed
that Ĥ( ⟨Ĥ⟩ ) never halts.

This logical entailment derives another one Ĥ( ⟨Ĥ⟩ ) cannot possibly
ever reach its final state unless Ĥ.qx( ⟨Ĥ⟩, ⟨Ĥ⟩ ) aborts at least one
of its simulations of its input.

As you (just retracted) and André has already agreed:
Every input to a simulating halt decider that only stops running when
its simulation is aborted unequivocally specifies a computation that
never halts.

Therefore when Ĥ.qx( ⟨Ĥ⟩, ⟨Ĥ⟩ ) aborts the simulation of its input it is
necessarily correct.

>> This is the same criteria that both you and André agreed to:
>> Every simulation that would never stop unless its simulating halt
>> decider stops it at some point specifies infinite execution.
>
> I retract all agreements you may think I've made. That's simpler than
> trying to explain myself. If you claim, henceforth, that I agree with
> anything other than my own, or a published textbook definition of
> halting, you will be arguing in bad faith.
>

Then try and explain how the input to H(P,P) or Ĥ.qx( ⟨Ĥ⟩, ⟨Ĥ⟩ ) can
possibly reach its final state.

> Any chance you will now say if
>
>> Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩)
>
> transitions to Ĥ.qn or Ĥ.qy? If you find this question difficult,
> please ask for some help in understanding it.
>

Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩) transitions to Ĥ.qn on the basis that its input cannot
possibly ever reach its final state, and indeed its input never does
reach its final state.

olcott

unread,
Jul 30, 2021, 9:16:14 PM7/30/21
to
> An answer. Thank you.
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> For Ĥ to be "exactly and precisely as in Linz" this, then, is the clause
> that applies to your H and Ĥ:
>

There is no H in the relevant last paragraph of the Linz proof that
forms the basis for the Linz conclusion.

>>>>>>>>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>>>>>>>>> if M applied to wM does not halt
>
> so Ĥ (M) applied to ⟨Ĥ⟩ (wM) does not halt, but you have just told me
> that it does. That is what this full (but abbreviated) state transition
> sequence means:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> Which is it?
>

Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then Ĥ0.qx simulates Ĥ1 with the
⟨Ĥ2⟩ copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then Ĥ1.qx simulates Ĥ2 with the
⟨Ĥ3⟩ copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then Ĥ2.qx simulates Ĥ3 with the
⟨Ĥ4⟩ copy then ...

The outermost Ĥ0.qx correctly decides that its input: (⟨Ĥ1⟩, ⟨Ĥ2⟩) can't
possibly ever reach its final state. Then it transitions to Ĥ0.qn
causing the outermost Ĥ0 to halt.

Because the outermost Ĥ0.qx did not decide that Ĥ0 would never halt and
it is self evident that its input: (⟨Ĥ1⟩, ⟨Ĥ2⟩) can't possibly ever
reach its final state there is no contradiction or paradox and it
decided correctly.

olcott

unread,
Jul 31, 2021, 10:20:58 PM7/31/21
to
On 7/31/2021 5:08 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/30/2021 2:58 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/30/2021 7:39 AM, Ben Bacarisse wrote:
>>>
>>>>> Any chance you will now say if
>>>>>
>>>>>> Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩)
>>>>>
>>>>> transitions to Ĥ.qn or Ĥ.qy? If you find this question difficult,
>>>>> please ask for some help in understanding it.
>>>>
>>>> Ĥ.qx(⟨Ĥ⟩, ⟨Ĥ⟩) transitions to Ĥ.qn
>>>
>>> An answer. Thank you.
>>>
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>
>>> For Ĥ to be "exactly and precisely as in Linz" this, then, is the clause
>>> that applies to your H and Ĥ:
>>
>> There is no H in the relevant last paragraph of the Linz proof that
>> forms the basis for the Linz conclusion.
>
> Distraction. Everything you ignore below is about the proof and refers
> only to Ĥ.
>
>>>>>>>>>>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>>>>>>>>>>> if M applied to wM does not halt
>>>
>>> so Ĥ (M) applied to ⟨Ĥ⟩ (wM) does not halt, but you have just told me
>>> that it does. That is what this full (but abbreviated) state transition
>>> sequence means:
>>>
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>
>>> Which is it?
>>
>> Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then Ĥ0.qx simulates Ĥ1 with the
>> ⟨Ĥ2⟩ copy then
>> Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then Ĥ1.qx simulates Ĥ2 with the
>> ⟨Ĥ3⟩ copy then
>> Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then Ĥ2.qx simulates Ĥ3 with the
>> ⟨Ĥ4⟩ copy then ...
>
> This is an abuse of the notation (but I know what you mean). There is
> no Ĥ1 or Ĥ2. If you think it helps to show which copy of ⟨Ĥ⟩ your
> simulating "decider" is either running and/or currently looking at, you
> need to come up with a notation that does that.

A better notation is what I have in my PDF actual subscripts but people
here tel me that their newsreader makes sure to totally ignore posts
with HTML so that do even see the post at all.

> At least I know what
> this "math poem" means, because you've been saying this "it's a
> simulator until" stuff for years.
>
>> The outermost Ĥ0.qx correctly decides that its input: (⟨Ĥ1⟩, ⟨Ĥ2⟩)
>> can't possibly ever reach its final state. Then it transitions to
>> Ĥ0.qn causing the outermost Ĥ0 to halt.
>
> Apart from the bad notation, yes. All those copies and tests and
> eventual deciding are neatly summed up in the last ⊢* Ĥ.qn of
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
>> Because the outermost Ĥ0.qx did not decide that Ĥ0 would never halt
>> and it is self evident that its input: (⟨Ĥ1⟩, ⟨Ĥ2⟩) can't possibly
>> ever reach its final state there is no contradiction or paradox and it
>> decided correctly.
>
> You are free to define "decide correctly" in any way you like provided
> you are honest about it. But you hooked people in by saying that your Ĥ
> is "exactly and precisely as in Linz", and you quoted, even now, what
> Linz has to say about such TMs:
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt
>
> This is your quote. You brought it up. You claimed your Ĥ was as Linz
> states -- that Ĥ.q0 wM ⊢* Ĥ.qn if and only if M applied to wM does not
> halt. Linz makes no exceptions based on why the transitions from Ĥ.q0
> wM to Ĥ.qn occur. Linz does not say
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt or if M applied wM only halts
> because...
>
> Are you now saying that your TM was not "as in Linz"? (You should,
> because you've admitted that elsewhere.)
>

Ĥ[0] is to be interpreted to mean Ĥ<sub>0</sub>
[0] Means the actual Turing machine and not a TM description.
[1] Means the first TM description parameter
[2] Means a copy of the the first TM description parameter

Now I am saying that when the actual unmodified Linz Ĥ is understood to
have a UTM/Halt-Decider at Ĥ[0].qx that this Ĥ[0].qx does correctly
decide that its input: (⟨Ĥ[1]⟩, ⟨Ĥ[2]⟩) can't possibly ever reach its
final state of Ĥ[1].qn or Ĥ[2].qn, therefore we know that its input
never halts therefore we know that a state transition from Ĥ[0].qx to
Ĥ0.qn is necessarily correct.

This is not a case of the halt decider deciding that Ĥ never halts and
then Ĥ halts. There are three different instances of Ĥ involved. It is
only their differing placement in the execution trace that makes the
result vary.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

> --------
> You have real trouble with this notation so I don't think you will know
> what I'm saying above, but for anyone else, here is a summary:
>
> If we have a TM "as in Linz" then this applies:
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt
>
> When asked what Ĥ does when given ⟨Ĥ⟩ PO says that it (eventually)
> transitions to Ĥ.qn, so the above clause applies with M = Ĥ and wM =
> ⟨Ĥ⟩:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> if Ĥ applied to ⟨Ĥ⟩ does not halt
>
> The first line says that Ĥ applied to ⟨Ĥ⟩ halts -- the final halting
> state is right there (Ĥ.qn) -- but the second line says that this should
> happen if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt. This is why
> PO's Ĥ is not "as in Linz".

olcott

unread,
Aug 1, 2021, 3:46:04 PM8/1/21
to
On 8/1/2021 1:41 PM, Malcolm McLean wrote:
> On Sunday, 1 August 2021 at 16:30:46 UTC+1, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>
>>> We've elimiated the "invert the result" step from Linz's proof. We
>>> have to insist that H is a "simulating halt decider" to achieve this.
>> The proof is still there, with all the same steps in it. I think you
>> mean there is a /different/ proof, without that step, that shows that
>> some naive "deciders" gets other cases wrong. I don't see why you find
>> that interesting, but I think that's the bottom line: you find some
>> things interesting that I don't.
>>
> Sure, there's a different proof, inspired by Linz's, but with the "invert
> the result" step removed. It only applies to naive simulating deciders.
> So to make it into a proof of general interest, we've got to show that
> a naive simulating decider can't be bettered by any other type of
> decider.
>>
>>> But that seems to be a reasonable condition. We know there are
>>> many properties of Turing machines that cannot be determined other
>>> than by stepping them.
>> And again I'm lost. Can you name an "interesting" property of a TM
>> computation that /can/ be determined by stepping it?
>>
> Take its busy beaver score, for example. You might object that even a
> stepping scorer can't always detect when a machine won't halt. So just
> add a limit, which grows with then number of states to keep the set
> infinite. Busy beaver score before either a halt or m * N states steps.
>>
>> My guess (you'll have to confirm) is that you mean there are many
>> properties that we can't always determine by stepping, but stepping the
>> computation is the "best we can do". If so, we've had this discussion
>> before, and I still disagree.
>>
> Yes, that's a reasonable summary.
>

>

Some errors were corrected and the rest was adapted to x86utm.

u32 HH(I, I)
{
HERE:
{
if (H(I, I) == 0)
return 0;
else
return 1;
}
goto HERE;
}

u32 H_Cap(I)
{
return HH(I, I);
}

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

Begin Local Halt Decider Simulation at Machine Address:d02
...[00000d02][00211915][00211919] 55 push ebp
...[00000d03][00211915][00211919] 8bec mov ebp,esp
...[00000d05][00211915][00211919] 8b4508 mov eax,[ebp+08]
...[00000d08][00211911][00000d02] 50 push eax
...[00000d09][00211911][00000d02] 8b4d08 mov ecx,[ebp+08]
...[00000d0c][0021190d][00000d02] 51 push ecx
...[00000d0d][00211909][00000d12] e8c0ffffff call 00000cd2
...[00000cd2][00211905][00211915] 55 push ebp
...[00000cd3][00211905][00211915] 8bec mov ebp,esp
...[00000cd5][00211905][00211915] 8b4508 mov eax,[ebp+08]
...[00000cd8][00211901][00000d02] 50 push eax
...[00000cd9][00211901][00000d02] 8b4d08 mov ecx,[ebp+08]
...[00000cdc][002118fd][00000d02] 51 push ecx
...[00000cdd][002118f9][00000ce2] e8e0fdffff call 00000ac2
...[00000d02][0025c33d][0025c341] 55 push ebp
...[00000d03][0025c33d][0025c341] 8bec mov ebp,esp
...[00000d05][0025c33d][0025c341] 8b4508 mov eax,[ebp+08]
...[00000d08][0025c339][00000d02] 50 push eax
...[00000d09][0025c339][00000d02] 8b4d08 mov ecx,[ebp+08]
...[00000d0c][0025c335][00000d02] 51 push ecx
...[00000d0d][0025c331][00000d12] e8c0ffffff call 00000cd2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

Input_Halts = 0

Proving that the above code is decided correctly.

olcott

unread,
Aug 1, 2021, 11:17:43 PM8/1/21
to
On 8/1/2021 5:39 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/31/2021 4:54 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> It matters not what I had.
>>> Because you can't justify it the honest debate you claim to want.
>>>
>>>> It only matters what I have.
>>> I.e. nothing of any interest. You make it plain in a previous reply
>>> that you've had nothing of interest going right back to the original
>>> deceptive claim.
>>>
>>>> If you are sincere about an honest dialogue then we must quit focusing
>>>> on details of obsolete technology.
>>> And yet you skipped the big picture part:
>>>
>>>>> (5) You said you had "an H that decides (Ĥ, Ĥ)". What decision did your
>>>>> Dec 2018 code come to about "(Ĥ, Ĥ)"?
>>>>
>>>> The 2018 version Halts(H_Hat, H_Hat)==0 in the exact same way that
>>>> H(P,P)==0 now except that the never halting criteria is much more
>>>> elaborate. The initial criteria was very crude.
>>>
>>> Ah, so you never had H and H_Hat that do anything that anyone would say
>>> is impossible. Had you said, back in Dec 2018, "I have C code such that
>>> H(H_Hat, H_Hat) == 0 but H_Hat(H_Hat) halts" no one would have been
>>> interested.
>>
>> If you are sincere about an honest dialogue then we must quit focusing
>> on details of obsolete technology.
>
> Ah, an honest dialogue requires me to ignore your past deception? Well,
> I can accommodate that: you /currently/ don't have anything that anyone
> would consider to be impossible or even interesting. An H/H_Hat pair
> such that H(H_Hat, H_Hat) == 0 and H_Hat(H_Hat) halts is of no interest
> to anyone. Is that better?
>

When H is a simulating partial halt decider and the halt decider
embedded in Ĥ at Ĥ.qx is a simulating halt decider then:

It is the case that the input to H(P,P) and the input to Ĥ(⟨Ĥ⟩) cannot
possibly ever reach their final state and must have their simulation
aborted to prevent the infinite execution of P and Ĥ.

Let's have an honest dialogue about that.

>>> I think you owe everyone an apology. Even if there was no indent to
>>> deceive, your words back then did everything possible to suggest some
>>> impossible Turing machine. And you wouldn't say, until recently, even
>>> when explicitly asked, what decision H came to. It was fishy from the
>>> start.
>
> You still owe everyone an apology. Neither Turing machines nor C code
> are obsolete technology. If you really had what you falsely claimed to
> have had, posting it at any time in the last 30 months would have
> settled the matter. It still would, but you either never had anything
> at all or you are too embarrassed to post what it was.
>

The technology that I had in 2018 is obsolete and not relevant to an
honest dialogue about the technology that I currently have.

olcott

unread,
Aug 1, 2021, 11:45:12 PM8/1/21
to
> I am happy you have a notation you like. Are you prepared to address
> that fact that your H^ is not "as in Linz"?
>

My Ĥ is exactly the Linz Ĥ with the additional elaboration that the
second wildcard state transition ⊢* is defined to be a simulating halt
decider. The Linz ⊢* explicitly allows for this without diverging from
the Linz template at all.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢*


> We all know you are declaring that to be correct. Here's why your Ĥ is
> not "as in Linz". Linz requires that
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt
>
> Any Ĥ that eventually transitions to Ĥ.qn on input wM must do so
> if, and only if, the encoded M applied to wM does not halt. But you've
> given us a case where your Ĥ is not like this:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>

And when we eliminate the fallacy of equivocation error we have

Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn

The way that you do it when your twin bother commits a crime that makes
you guilty.

Ĥ[0].q0 ⟨Ĥ[1]⟩ only halts because the simulation of the
the input to Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ was aborted.

(a) The simulation of the input to Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩
was aborted because neither ⟨Ĥ[1]⟩ nor ⟨Ĥ[2]⟩ could
ever possibly reach their final states.

(b) Because neither ⟨Ĥ[1]⟩ nor ⟨Ĥ[2]⟩ could ever possibly reach
their final states we know that they never halt.

(c) Because they never halt we know that Ĥ[0].qx correctly decided
that its input never halts.

This is the same as: X > Y & Y > Z therefore X > Z
I do seem to have a correct chain of inference.
I do not think that you can point to any error in
this chain of inference.

In an honest dialogue when you would disagree that a
chain of inference derives a correct conclusion you
would point to a specific error in this chain of inference.

What is the error in (a)(b)(c) ?

> Here we can see that Ĥ applied to ⟨Ĥ⟩ halts. You can call your Ĥ's
> behaviour "correct". You can call it anything you like. But it's not
> "as in Linz". It does not say anything about Linz's proof. It does not
> do anything people would call impossible or even interesting.
>
> Presumably, you will simply explain, yet again, why you choose to call
> it correct. You might even, yet again, quote the symbols from Linz that
> don't apply to your Ĥ in order to make you posts seem relevant.

olcott

unread,
Aug 2, 2021, 2:16:19 PM8/2/21
to
> Yes, let's. Here's how to say what happens without all those vague
> (and, frankly, incorrect) words:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> If you don't mean
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> can you say what you do mean formally? Formally means using some
> formal notation like Linz does.
>

As Linz already specifies yet does not encode in his notation there are
at least three separate and distinct instances of Ĥ.

The first one of these instances is the actual Turing machine Ĥ.
The second one is the TM description ⟨Ĥ⟩ input to Ĥ.
The third one is the copy of the TM description ⟨Ĥ⟩ input to Ĥ.

If we do not keep track of these distinctions then it seems like Ĥ.qx
decides that its input never halts and then its input immediately halts.
This would be an actual contradiction.

When we do keep track of these distinctions then the input: ⟨Ĥ^1⟩ to Ĥ^0
can be understood to never reach its final states Ĥ^1.qy or Ĥ^1.qn thus
proving that Ĥ^0.qx did correctly decide that its input ⟨Ĥ^1⟩ ⟨Ĥ^2⟩
never halts.

> If what you want to say is all about what happens in that second ⊢*
> (i.e. all the nested simulations and so on) then don't bother, because
> what makes your Ĥ irrelevant is what state Ĥ applied to ⟨Ĥ⟩ gets to, not
> how it gets there.
>
>>>>> I think you owe everyone an apology. Even if there was no indent to
>>>>> deceive, your words back then did everything possible to suggest some
>>>>> impossible Turing machine. And you wouldn't say, until recently, even
>>>>> when explicitly asked, what decision H came to. It was fishy from the
>>>>> start.
>>> You still owe everyone an apology. Neither Turing machines nor C code
>>> are obsolete technology. If you really had what you falsely claimed to
>>> have had, posting it at any time in the last 30 months would have
>>> settled the matter. It still would, but you either never had anything
>>> at all or you are too embarrassed to post what it was.
>>
>> The technology that I had in 2018 is obsolete and not relevant to an
>> honest dialogue about the technology that I currently have.
>
> You had C code. C code is not obsolete. It's also a good formalism.
> You could say what you meant back then by posting the code. But you
> won't post it either because you never had it or you are embarrassed by
> it. An honest academic would simply say "this is what I had -- very
> rough and ready, isn't it? Here's the tidied up version...".

olcott

unread,
Aug 2, 2021, 2:25:16 PM8/2/21
to
H[0] means H<sub>0</sub>

When we do keep track of these distinctions then the input: ⟨Ĥ[1]⟩ to
Ĥ[0] can be understood to never reach its final states Ĥ[1].qy or
Ĥ[1].qn thus proving that Ĥ[0].qx did correctly decide that its input
⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ never halts.

olcott

unread,
Aug 2, 2021, 4:53:20 PM8/2/21
to
On 8/2/2021 2:10 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/1/2021 5:54 AM, Ben Bacarisse wrote:
>
>>> I am happy you have a notation you like. Are you prepared to address
>>> that fact that your H^ is not "as in Linz"?
>>
>> My Ĥ is exactly the Linz Ĥ with the additional elaboration that the
>> second wildcard state transition ⊢* is defined to be a simulating halt
>> decider.
>
> No. I've explained many times now why your Ĥ is not at all "the Linz
> Ĥ". Do you see any point in my doing so again?
>
>>> We all know you are declaring that to be correct. Here's why your Ĥ is
>>> not "as in Linz". Linz requires that
>>>
>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>> if M applied to wM does not halt
>>>
>>> Any Ĥ that eventually transitions to Ĥ.qn on input wM must do so
>>> if, and only if, the encoded M applied to wM does not halt. But you've
>>> given us a case where your Ĥ is not like this:
>>>
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>
>> And when we eliminate the fallacy of equivocation error we have
>>
>> Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn
>
> The only thing I think you are equivocating on is pretending that Ĥ[0]
> is not Ĥ, and it doesn't look as if you've removed that error. I think
> you /should/ remove it so that you can be saying something of value
> about Ĥ.
>

It is clear from the text that Linz does specify at least three
different instances of Ĥ, The TM the TMD input ⟨Ĥ⟩ and a copy of this
TMD input.

Failing to keep track of which is which when the simulated execution is
analyzed simply ignores a key salient detail.

>> The way that you do it when your twin bother commits a crime that
>> makes you guilty.
>>
>> Ĥ[0].q0 ⟨Ĥ[1]⟩ only halts because the simulation of the
>> the input to Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ was aborted.
>>
>> (a) The simulation of the input to Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩
>> was aborted because neither ⟨Ĥ[1]⟩ nor ⟨Ĥ[2]⟩ could
>> ever possibly reach their final states.
>>
>> (b) Because neither ⟨Ĥ[1]⟩ nor ⟨Ĥ[2]⟩ could ever possibly reach
>> their final states we know that they never halt.
>>
>> (c) Because they never halt we know that Ĥ[0].qx correctly decided
>> that its input never halts.
>>
>> This is the same as: X > Y & Y > Z therefore X > Z
>> I do seem to have a correct chain of inference.
>> I do not think that you can point to any error in
>> this chain of inference.
>>
>> In an honest dialogue when you would disagree that a
>> chain of inference derives a correct conclusion you
>> would point to a specific error in this chain of inference.
>>
>> What is the error in (a)(b)(c) ?
>
> Far too many to go into all of them (if you are not inclined to correct
> anything, just jump to number 7) but ere are some:
>
> (1) Unless Ĥ[0] is just another name for Ĥ you are not saying anything I
> care about. What matters is what Ĥ applied to ⟨Ĥ⟩ does.
>
> (2) TMs don't "abort". The sequence of configurations ends.
>

This seems to diverge from an honest dialogue in that it seems like you
are saying that the concept of a simulating halt decider cannot possibly
exist.

Do you agree that a simulating halt decider can abort its simulation of
its input? If not please provide all of the details of why you disagree.

> (3) Stop talking about what "could possibly" happen. TMs do what they
> do. There are no "possibilities".
>

When the simulating halt decider at Ĥ.qx examines the behavior of its
pure simulation its input ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ it determines that this input
never reaches its final state.

> (4) ⟨Ĥ[1]⟩ and ⟨Ĥ[2]⟩ are strings. A string does not "reach" anything.
> Strings don't even have states that can be reached. I can unravel
> this, but why must your readers work hard to unpick your metaphors?
>

The Simulation of ⟨Ĥ[1]⟩ on input ⟨Ĥ[2]⟩ is computationally equivalent
to the execution of Ĥ[1] on input ⟨Ĥ[2]⟩ thus the Simulation of ⟨Ĥ[1]⟩
either reaches or fails to reach a final state.

> (5) Ĥ[0].qx is a state. It does not decide anything. (Again, I can
> guess what you mean but you asked for help.)
>

Ĥ[0].qx is stipulated to be the halt decider named H.
In the erroneous Linz notation it is at the second start state of Ĥ.

> (6) States don't have input. Whilst I could guess that you mean "the
> tape" at the point the state is entered", states in a TM may be
> entered many times so there is no obvious single "input".
>

Linz refers to it as: "The input to H" thus making your "correction"
within the context of Linz, incorrect.

> (7) The correct behaviour of Ĥ is not based on (a) and (b) but on what
> Linz says about Ĥ applied to ⟨Ĥ⟩. Your Ĥ does not behave as Linz's
> Ĥ should, even in the one case you care about.

You slightly changed the subject. We are not talking about the behavior
of Ĥ. We are talking about what the future behavior of the input to the
simulating halt decider at Ĥ.qx would be.

When we stay 100% perfectly focused on exactly this we can see that the
future behavior of the input to Ĥ.qx never reaches its final state.

olcott

unread,
Aug 2, 2021, 8:55:45 PM8/2/21
to
On 8/2/2021 7:11 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/2/2021 2:10 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/1/2021 5:54 AM, Ben Bacarisse wrote:
>>>
>>>>> I am happy you have a notation you like. Are you prepared to address
>>>>> that fact that your H^ is not "as in Linz"?
>>>>
>>>> My Ĥ is exactly the Linz Ĥ with the additional elaboration that the
>>>> second wildcard state transition ⊢* is defined to be a simulating halt
>>>> decider.
>>> No. I've explained many times now why your Ĥ is not at all "the Linz
>>> Ĥ". Do you see any point in my doing so again?
>
> I suspect not. You certainly have not asked a single question that
> could help you to understand why your Ĥ is irrelevant.
>
>>>>> We all know you are declaring that to be correct. Here's why your Ĥ is
>>>>> not "as in Linz". Linz requires that
>>>>>
>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>> if M applied to wM does not halt
>>>>>
>>>>> Any Ĥ that eventually transitions to Ĥ.qn on input wM must do so
>>>>> if, and only if, the encoded M applied to wM does not halt. But you've
>>>>> given us a case where your Ĥ is not like this:
>>>>>
>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>>
>>>> And when we eliminate the fallacy of equivocation error we have
>>>>
>>>> Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn
>>> The only thing I think you are equivocating on is pretending that Ĥ[0]
>>> is not Ĥ, and it doesn't look as if you've removed that error. I think
>>> you /should/ remove it so that you can be saying something of value
>>> about Ĥ.
>>
>> It is clear from the text that Linz does specify at least three
>> different instances of Ĥ, The TM the TMD input ⟨Ĥ⟩ and a copy of this
>> TMD input.
>
> Still equivocating. Either Ĥ[0] = Ĥ or you are wasting everyone's time.
>

Ĥ[0] = Ĥ
Ĥ[1] != Ĥ
Ĥ[2] != Ĥ

> (This is mathematical equality. Ĥ is a tuple of sets. If Ĥ[0] is not
> exactly identical in every way to Ĥ then I don't care about it. Note

The different instances of Ĥ are different in a crucial way and that is
their placement in the execution trace.

> that I'm not disputing your right, for ease of explanation, to give
> identical things more than one name. But the same permission allows me
> to use any of the names because they name the same thing.)
>

Only because their differing placement in the execution trace do they
have different halting behavior. This is a crucial distinction.

> You are wrong because
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> where Linz requires that
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>

Linz could require that all cats must be dogs, the verifiable fact is
that the input ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qx is correctly decided as never halting.

If you really do sincerely want an actual honest dialogue you would
carefully work through all the steps to confirm that the input ⟨Ĥ⟩ ⟨Ĥ⟩
to Ĥ.qx never halts.

Once we have mutual agreement that Ĥ.qx correctly decides that its
input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts and Ĥ does halt, then we have the basis to go
to the next step and resolve the actual paradox.

As long as it is simply dismissed out-of-hand as a contradiction the
paradox remains unresolved.

> Either you ask questions that might help you to understand what I'm
> saying, or you can just repeat again, in ever greater detail, what
> happens in that ⊢* as if the exact way in which you are wrong is the key
> thing you want to tell the world. It's up to you.
>
> Please don't think I don't know what you are saying. I understand all
> the copying and levels and so on. But the details don't make you right
> because it's the outcome that makes you wrong. No explanation of how
> you get the wrong behaviour, no matter how detailed, makes the wrong
> behaviour right. Your Ĥ is just one of countless other TMs that do not
> do what Linz says is impossible, even for this one input.
>
> I'll leave it there. If you really want my comments on your replies to
> the errors you asked me to point it, I'll post again, but it it's all
> noise compared to the big mistake.

olcott

unread,
Aug 2, 2021, 10:11:49 PM8/2/21
to
On 8/2/2021 8:45 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/2/2021 7:11 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>

> (I'm going to ignore errors that I've already pointed out.)
>
>> If you really do sincerely want an actual honest dialogue you would
>> carefully work through all the steps to confirm that the input ⟨Ĥ⟩ ⟨Ĥ⟩
>> to Ĥ.qx never halts.
>
> If you want me to comment on that, write it without the errors. It has
> two, both of which I've commented on before. If you are sincere, you
> will want to write clearly and without errors.
>
>> Once we have mutual agreement that Ĥ.qx correctly decides that its
>> input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts and Ĥ does halt, then we have the basis to
>> go to the next step and resolve the actual paradox.
>
> There is no paradox. That Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn when Ĥ applied to ⟨Ĥ⟩
> clearly halts is not paradoxical. It's just not the sort of TM the
> proof is talking about. And how could it be? The "Linz Ĥ" is as
> illogical as a cat that is a dog.
>
>> As long as it is simply dismissed out-of-hand as a contradiction the
>> paradox remains unresolved.
>
> There is no contradiction or paradox. You Ĥ is just the wrong sort of
> TM. The proof you want to "refute" is talking about this sort of Ĥ:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>

Ĥ.qx correctly decides that its input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts
Ĥ.qx correctly decides that its input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts
Ĥ.qx correctly decides that its input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts
Ĥ.qx correctly decides that its input: ⟨Ĥ⟩ ⟨Ĥ⟩ never halts

In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever https://en.wikipedia.org/wiki/Halting_problem

olcott

unread,
Aug 3, 2021, 9:00:27 AM8/3/21
to
On 8/3/2021 12:29 AM, Malcolm McLean wrote:
> On Tuesday, 3 August 2021 at 02:01:14 UTC+1, olcott wrote:
>> On 8/2/2021 7:20 PM, Ben Bacarisse wrote:
>>
>> As long as you keep thinking of it as a resolved contradiction the
>> actual paradox remains unresolved.
>>
>> I proved that Ĥ.qx does correctly decide that its input ⟨Ĥ⟩ ⟨Ĥ⟩ never
>> halts it is also equally proven that Ĥ halts thus a paradox and not a
>> contradiction is formed.
>>
>> My current answer to this is GIGO self-contradictory input <IN>
>> contractory output <OUT>. There may be a better answer.
>>
> With your H, H_Hat <H_Hat> halts. That's common ground.
> With your H H<H_Hat><H_Hat> returns false (non-halting). That's also
> common ground.
>
> So one positive in this is that you are clearly being honest about the
> behaviour of your code.
> But don't you see that this behaviour is exactly what Linz says would
> happen? H_Hat<H_Hat> is a case that H cannot classify correctly.
>

On pages 4-6 I proves that H(P,P) does correctly decide that its input
never halts.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

Thus meeting this criteria:
In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem

> You're trying to claim that H_Hat<H_Hat> doens't really halt because
> the recursion of H instances is terminated by H.

No I have never been saying that. I am claiming that the input to H(P,P)
never halts whether or not H terminates its simulation of this input.

No I have never been saying that. I am claiming that the input to H(P,P)
never halts whether or not H terminates its simulation of this input.

No I have never been saying that. I am claiming that the input to H(P,P)
never halts whether or not H terminates its simulation of this input.

No I have never been saying that. I am claiming that the input to H(P,P)
never halts whether or not H terminates its simulation of this input.

> This leads us down
> a rabbit hole of talking of the "inner" and "outer" H or H1, H2 and so on.

None-the-less if this is where the actual truth is we can't simply
dismiss it out-of-hand.

> But what Linz is saying is that the internal details of H don't matter. It
> can be a simulating halt decider, a control graph anlyser, or even just
> a stub machine that returns a flag. However cleverly or simply it is
> written, it classifies H_Hat<H_Hat> wrongly.
>

We can see that the input to H(P,P) never halts therefore H IS NOT WRONG.

> I think it's high time to wind up these threads.
>

I think that it is high time that people actually pay complete attention.

olcott

unread,
Aug 3, 2021, 11:21:36 AM8/3/21
to
On 8/3/2021 9:33 AM, Malcolm McLean wrote:
> On Tuesday, 3 August 2021 at 14:00:28 UTC+1, olcott wrote:
>> On 8/3/2021 12:29 AM, Malcolm McLean wrote:
>>>
>>> You're trying to claim that H_Hat<H_Hat> doens't really halt because
>>> the recursion of H instances is terminated by H.
>> No I have never been saying that. I am claiming that the input to H(P,P)
>> never halts whether or not H terminates its simulation of this input.
>>
> We agree that P(P) halts.
> So now you're drawing a distinction between P(P) and "the input to H(P,P)".
> ThIs is nonsense..

Try and find any error in (a)(b)(c)(d) on page 6

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


>>>
>> We can see that the input to H(P,P) never halts therefore H IS NOT WRONG.
>>> I think it's high time to wind up these threads.
>>>
>> I think that it is high time that people actually pay complete attention.
>>
> You can't complain about lack of attention.

olcott

unread,
Aug 3, 2021, 3:26:47 PM8/3/21
to
On 8/3/2021 12:11 PM, André G. Isaak wrote:
> On 2021-08-03 09:21, olcott wrote:
>> On 8/3/2021 9:33 AM, Malcolm McLean wrote:
>>> On Tuesday, 3 August 2021 at 14:00:28 UTC+1, olcott wrote:
>>>> On 8/3/2021 12:29 AM, Malcolm McLean wrote:
>>>>>
>>>>> You're trying to claim that H_Hat<H_Hat> doens't really halt because
>>>>> the recursion of H instances is terminated by H.
>>>> No I have never been saying that. I am claiming that the input to
>>>> H(P,P)
>>>> never halts whether or not H terminates its simulation of this input.
>>>>
>>> We agree that P(P) halts.
>>> So now you're drawing a distinction between P(P) and "the input to
>>> H(P,P)".
>>> ThIs is nonsense..
>>
>> Try and find any error in (a)(b)(c)(d) on page 6
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>
>
>
> The error, which has been pointed out repeatedly, is in your (b).
>
> You claim "there are no control flow instructions in the execution trace
> that would escape the infinite recursion", but there *are* flow control
> instructions. But your trace is incomplete and skips over the call to
> B82 where these flow control instructions reside.
>

Whether H aborts its simulation of P or not P never reaches its final
state.

The conditional instructions are merely the aspect of H aborting its
simulation of P.

Because P never reaches its final state whether H aborts its simulation
of P or not we know that P never halts.

> The code at B82 is *part* of the computation performed by P. It *must*
> be included in any trace of P which purports to be a complete and honest
> trace.
>
> You don't seem to grasp the fact that *all* code executed by a
> particular computation from the moment the computation begins to the
> time it halts (assuming it halts) is part of that computation. It
> doesn't matter whether the code in question is shared by some other
> routine, or is operating system code or whatever. These are purely
> artificial distinctions which play no role in the theory of computation.
>
> André

olcott

unread,
Aug 3, 2021, 4:47:44 PM8/3/21
to
On 8/3/2021 3:08 PM, André G. Isaak wrote:
> On 2021-08-03 13:26, olcott wrote:
>> On 8/3/2021 12:11 PM, André G. Isaak wrote:
>>> On 2021-08-03 09:21, olcott wrote:
>>>> On 8/3/2021 9:33 AM, Malcolm McLean wrote:
>>>>> On Tuesday, 3 August 2021 at 14:00:28 UTC+1, olcott wrote:
>>>>>> On 8/3/2021 12:29 AM, Malcolm McLean wrote:
>>>>>>>
>>>>>>> You're trying to claim that H_Hat<H_Hat> doens't really halt because
>>>>>>> the recursion of H instances is terminated by H.
>>>>>> No I have never been saying that. I am claiming that the input to
>>>>>> H(P,P)
>>>>>> never halts whether or not H terminates its simulation of this input.
>>>>>>
>>>>> We agree that P(P) halts.
>>>>> So now you're drawing a distinction between P(P) and "the input to
>>>>> H(P,P)".
>>>>> ThIs is nonsense..
>>>>
>>>> Try and find any error in (a)(b)(c)(d) on page 6
>>>>
>>>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>>
>>>
>>>
>>>
>>>
>>> The error, which has been pointed out repeatedly, is in your (b).
>>>
>>> You claim "there are no control flow instructions in the execution
>>> trace that would escape the infinite recursion", but there *are* flow
>>> control instructions. But your trace is incomplete and skips over the
>>> call to B82 where these flow control instructions reside.
>>>
>>
>> Whether H aborts its simulation of P or not P never reaches its final
>> state.
>
> But H's simulation of P is *not* a computation.
>

Sure it is.
The pure simulation of a computation on its input is computationally
equivalent to the direct execution of this same computation on its input.

> When we run H(P, P) the only computation being performed is H(P, P), and
> if H aborts its simulation of P(P), then control returns to H which then
> Halts.
>

The job of a halt decider is to correctly predict the future behavior of
its input. Because the input to H(P,P) does not transition to its final
state whether or not H aborts the simulation of this input we know that
this input never halts.

In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem

Because the P that halts is not: "a description of an arbitrary computer
program" it is not in the scope of the Halting Problem. Only the input
to P is in scope of the halting problem.

> When we run P(P) as a computation, again, the only computation being
> performed is P(P). Any simulations performed by P are *not*
> computations, and when some simulation is aborted control returns to the
> outermost P which then halts. And the behaviour of the actual
> independent computation P determines the *only* correct answer to the
> question 'does P(P) halt?'.
>
> The question which H(P, P) is supposed to answer *isn't* about some
> internal simulation. It's supposed to answer a question about an actual
> computation, P(P) and we know that that computation halts. What occurs
> in some internal simulation isn't relevant to the answer to this question.
>
>> The conditional instructions are merely the aspect of H aborting its
>> simulation of P.
>
> Which then allows the *actual* computation being performed to halt. The
> halting problem is *only* concerned with actual computations.
>
>> Because P never reaches its final state whether H aborts its
>> simulation of P or not we know that P never halts.
>
> Again, the question being asked isn't concerned with the simulation but
> with the actual computation. The simulation is *part* of that
> computation. The fact that the simulation gets aborted is *also* part of
> the computation, and that allows the *whole* computation to halt. The
> halting problem isn't interested in some part of a computation, only the
> computation as a whole.
>
>>> The code at B82 is *part* of the computation performed by P. It
>>> *must* be included in any trace of P which purports to be a complete
>>> and honest trace.
>
> Again, if you stopped omitting a portion of your traces, things would be
> clearer to you.
>
> Remember that the halting problem is concerned with computations, not
> with subroutines. Since you insist on using C rather than actual Turing
> Machines, though, this minimally requires that your H and your P be
> *separate* programs. That means each one should have its own source file
> with its own main. Each should be compiled and linked separately. Your
> insistence on sticking everything into a single source file is a cheat
> which you need to abandon.
>
> H needs to take as input a complete *program*, not just some function
> which is part of the same source file as H.

olcott

unread,
Aug 3, 2021, 5:03:17 PM8/3/21
to
On 8/3/2021 3:56 PM, André G. Isaak wrote:
> No. It isn't. A computation is a free-standing, self-contained piece of
> code. When you run H(P, P) the computation P(P) isn't being computed.
> It's being evaluated. H(P, P) is the only computation being run in this
> case.
>

So you don't understand how UTMs work.

> And your H *doesn't* perform a pure simulation of its input, so we can't
> even talk about the simulation as being 'computationally equivalent' to
> some computation.
>

The fact that the first seven instructions of P keep repeating while H
is in pure simulation mode proves that H is doing pure simulation mode
correctly.

>>> When we run H(P, P) the only computation being performed is H(P, P),
>>> and if H aborts its simulation of P(P), then control returns to H
>>> which then Halts.
>>>
>>
>> The job of a halt decider is to correctly predict the future behavior
>> of its input. Because the input to H(P,P) does not transition to its
>> final state whether or not H aborts the simulation of this input we
>> know that this input never halts.
>>
>> In computability theory, the halting problem is the problem of
>> determining, from a description of an arbitrary computer program and
>> an input, whether the program will finish running, or continue to run
>> forever. https://en.wikipedia.org/wiki/Halting_problem
>>
>> Because the P that halts is not: "a description of an arbitrary
>> computer program" it is not in the scope of the Halting Problem. Only
>> the input to P is in scope of the halting problem.
>
> Here you're very confused. The "P that halts" *is* the computation which
> the input to H describes. A halt decider takes a description of an
> arbitrary program and answers *about the program described by that
> description*. The "input to P" isn't a computation. It's a description
> of a computation. Halting applies to actual computations, not to
> descriptions.
>
> André
>
>

The key point is that if it is not AN INPUT the it doesn't count.
The simulation of inputs is not forbidden.

olcott

unread,
Aug 3, 2021, 5:51:06 PM8/3/21
to
On 8/3/2021 4:26 PM, André G. Isaak wrote:
> I'm well aware of how UTMs work. I am also aware that an x86 simulator
> is not the same thing as a UTM.
>

It is equivalent. In any case my exactly same reasoning directly applies
to the Linz proof.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

When Ĥ is applied to its own Turing Machine description ⟨Ĥ⟩ the embedded
halt decider at Ĥ.qx correctly decides that its input ⟨Ĥ⟩ ⟨Ĥ⟩ never halts.

>>> And your H *doesn't* perform a pure simulation of its input, so we
>>> can't even talk about the simulation as being 'computationally
>>> equivalent' to some computation.
>>>
>>
>> The fact that the first seven instructions of P keep repeating while H
>> is in pure simulation mode proves that H is doing pure simulation mode
>> correctly.
>
> The problem is that your 'pure simulation mode' is a cheat.
>

That the execution trace of the simulation of P precisely corresponds to
its source-code proves beyond all possible doubt that the pure
simulation of P by H is correct. There is no way to wiggle out of this.

> Your H and P *need* to be independent, self-contained programs. They
> need to both be compiled and linked separately resulting in two
> different executables. This means that the copy of H contained in P will
> be *distinct* from program H. It will be at an entirely different
> address and any code inside H which tells it to ignore its 'own code'
> will not result in it ignoring the H contained in P.
>
> That also means that any change in the "mode" in which the main H runs
> *cannot* have any effect on what the H contained in P does.
>
> Your 'pure simulation mode' is only valid as a test if it applies *only*
> to the behaviour of H, and not to the behaviour of the H contained
> inside P.
>
> If you change what the H inside P does, you are then talking about an
> *entirely different* computation which has no bearing on the halting
> behaviour of P.
>
> You can't evaluate whether P halts by considering what some modified
> version of P does, which is in effect what you are doing.
>
> André
>

That the execution trace of the simulation of P precisely corresponds to
its source-code proves beyond all possible doubt that the pure
simulation of P by H is correct. There is no way to wiggle out of this.

olcott

unread,
Aug 3, 2021, 8:42:55 PM8/3/21
to
On 8/3/2021 5:35 PM, André G. Isaak wrote:
> No, it isn't equivalent. A UTM takes a description of a *Turing Machine*
> as its input. A description of an x86 program is not a Turing Machine.
> How can two computations which take entirely distinct inputs be equivalent?
>

Apparently you don't understand computational equivalence either.

>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt
>>
>> When Ĥ is applied to its own Turing Machine description ⟨Ĥ⟩ the
>> embedded halt decider at Ĥ.qx correctly decides that its input ⟨Ĥ⟩ ⟨Ĥ⟩

Specifies a computation that halts.

>> never halts.
>
> Inputs neither halt nor don't halt. Only computations halt. >
> And Ĥ.qx isn't an 'embedded halt decider'. It is a state.
>

Linz stipulates that it <is> Turing machine H.

>>>>> And your H *doesn't* perform a pure simulation of its input, so we
>>>>> can't even talk about the simulation as being 'computationally
>>>>> equivalent' to some computation.
>>>>>
>>>>
>>>> The fact that the first seven instructions of P keep repeating while
>>>> H is in pure simulation mode proves that H is doing pure simulation
>>>> mode correctly.
>>>
>>> The problem is that your 'pure simulation mode' is a cheat.
>>>
>>
>> That the execution trace of the simulation of P precisely corresponds
>> to its source-code proves beyond all possible doubt that the pure
>> simulation of P by H is correct. There is no way to wiggle out of this.
>
> No. It doesn't 'precisely correspond' to its source code because your
> trace *omits* a big chunk of code.
>

*What details of this paragraph do you feel are incorrect (and why)*

Because H only acts as a pure simulator of its input until after its
halt status decision has been made it has no behavior that can possibly
effect the behavior of its input. Because of this H screens out its own
address range in every execution trace that it examines. This is why we
never see any instructions of H in any execution trace after an input
calls H.

>>> Your H and P *need* to be independent, self-contained programs. They
>>> need to both be compiled and linked separately resulting in two
>>> different executables. This means that the copy of H contained in P
>>> will be *distinct* from program H. It will be at an entirely
>>> different address and any code inside H which tells it to ignore its
>>> 'own code' will not result in it ignoring the H contained in P.
>>>
>>> That also means that any change in the "mode" in which the main H
>>> runs *cannot* have any effect on what the H contained in P does.
>>>
>>> Your 'pure simulation mode' is only valid as a test if it applies
>>> *only* to the behaviour of H, and not to the behaviour of the H
>>> contained inside P.
>>>
>>> If you change what the H inside P does, you are then talking about an
>>> *entirely different* computation which has no bearing on the halting
>>> behaviour of P.
>>>
>>> You can't evaluate whether P halts by considering what some modified
>>> version of P does, which is in effect what you are doing.
>>>
>>> André
>>>
>>
>> That the execution trace of the simulation of P precisely corresponds
>> to its source-code proves beyond all possible doubt that the pure
>> simulation of P by H is correct. There is no way to wiggle out of this.
>
> No. It doesn't 'precisely correspond' to its source code because your
> trace *omits* a big chunk of code.
>

*What details of this paragraph do you feel are incorrect (and why)*

Because H only acts as a pure simulator of its input until after its
halt status decision has been made it has no behavior that can possibly
effect the behavior of its input. Because of this H screens out its own
address range in every execution trace that it examines. This is why we
never see any instructions of H in any execution trace after an input
calls H.

> Come back and post a complete trace once you've actually set up your H
> and P *properly*. i.e. as two *separate* programs which have been
> compiled and linked two form two separate, *complete* executables where
> P does not call any code contained in H. If there is code in common, it
> must be *duplicated* so that each executable contains its own copy of
> this code.
>
> There is no point discussing your implementation where your H and P are
> contained in a single executable. That's not how 'TM equivalents' work,
> nor is it how the Linz Proof constructs H_Hat, and no conclusions which
> you draw from such a mangled implementation can possibly shed any light
> on the halting problem.
>

So when your reasoning fails to show that my H is incorrect you change
the subject. It is true that the input to H(P,P) never halts therefore
H(P,P)==0 is correct.

> If you don't grasp why what you are doing is illegitimate, then I
> suggest you go and actually learn what the term 'computation' means.

The standard formal definition of computation, repeated in all the major
textbooks, derives from these early ideas. Computation is defined as the
execution sequences of halting Turing machines (or their equivalents).
An execution sequence is the sequence of total configurations of the
machine, including states of memory and control unit.

https://dl.acm.org/doi/pdf/10.1145/1880066.1880067

> That would involve actually reading Linz and/or Sipser *from the
> beginning*. Your notion than you can somehow overcome a well-established
> proof without even grasping the fundamentals of the subject matter is
> mystifying to say the least.
>
> André

olcott

unread,
Aug 3, 2021, 11:24:00 PM8/3/21
to
On 8/2/2021 7:11 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/2/2021 2:10 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/1/2021 5:54 AM, Ben Bacarisse wrote:
>>>
>>>>> I am happy you have a notation you like. Are you prepared to address
>>>>> that fact that your H^ is not "as in Linz"?
>>>>
>>>> My Ĥ is exactly the Linz Ĥ with the additional elaboration that the
>>>> second wildcard state transition ⊢* is defined to be a simulating halt
>>>> decider.
>>> No. I've explained many times now why your Ĥ is not at all "the Linz
>>> Ĥ". Do you see any point in my doing so again?
>
> I suspect not. You certainly have not asked a single question that
> could help you to understand why your Ĥ is irrelevant.
>
>>>>> We all know you are declaring that to be correct. Here's why your Ĥ is
>>>>> not "as in Linz". Linz requires that
>>>>>
>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>> if M applied to wM does not halt
>>>>>
>>>>> Any Ĥ that eventually transitions to Ĥ.qn on input wM must do so
>>>>> if, and only if, the encoded M applied to wM does not halt. But you've
>>>>> given us a case where your Ĥ is not like this:
>>>>>
>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>>
>>>> And when we eliminate the fallacy of equivocation error we have
>>>>
>>>> Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn
>>> The only thing I think you are equivocating on is pretending that Ĥ[0]
>>> is not Ĥ, and it doesn't look as if you've removed that error. I think
>>> you /should/ remove it so that you can be saying something of value
>>> about Ĥ.
>>
>> It is clear from the text that Linz does specify at least three
>> different instances of Ĥ, The TM the TMD input ⟨Ĥ⟩ and a copy of this
>> TMD input.
>
> Still equivocating. Either Ĥ[0] = Ĥ or you are wasting everyone's time.
>
> (This is mathematical equality. Ĥ is a tuple of sets. If Ĥ[0] is not
> exactly identical in every way to Ĥ then I don't care about it. Note
> that I'm not disputing your right, for ease of explanation, to give
> identical things more than one name. But the same permission allows me
> to use any of the names because they name the same thing.)
>
> You are wrong because
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> where Linz requires that
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>

You have the above incorrectly in these two
M refers to the Turing Machine described by wM.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

This is *NOT* the Ĥ that is executed.
This is only the Turing Machine description ⟨Ĥ⟩ input.

In computability theory, the halting problem is the
problem of determining, from a description of an
arbitrary computer program and an input, whether
the program will finish running, or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem

The key point is that only the input to the halt decider is within the
scope of the halting problem.

As long as the halt decider correctly decides its input what these same
programs do what they are not inputs to the halt decider make no
difference to the actual halting problem.

olcott

unread,
Aug 4, 2021, 11:11:39 AM8/4/21
to
On 8/4/2021 9:13 AM, Malcolm McLean wrote:
> On Wednesday, 4 August 2021 at 05:55:59 UTC+1, olcott wrote:
>>
>> I am not willing to talk about anything besides page 6 until we have
>> mutual agreement on page 6.
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>
> We agree that P(P) halts and that H(P, P) reports false (non-halting).
>
> I've suggested that maybe you are trying to argue that P(P)'s halting
> doesn't count, because it is generated by the copy of H inside P.
>
> You've rejected that idea, and insist that H(P,P) has correctly determined
> that P(P) is non-halting.
>
> I don't really think there's anything useful left to say.
>

In computability theory, the halting problem is the problem
of determining, from a description of an arbitrary computer
program and an input, whether the program will finish running,
or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


Because page 6 does prove that H(P,P) does correctly decide that its
input never halts and the halting problem only requires that H decide
its input correctly the fact that H(P,P)==0 is correct does directly
refute the halting problem counter-example conclusion.

That people are unwilling to critique page 6 only shows that they are
unwilling to have an actual honest dialogue.

olcott

unread,
Aug 4, 2021, 11:14:28 AM8/4/21
to
On 8/4/2021 12:36 AM, André G. Isaak wrote:
> On 2021-08-03 22:55, olcott wrote:
>> On 8/3/2021 11:38 PM, olcott wrote:
>>> On 8/3/2021 11:36 PM, André G. Isaak wrote:
>>>> On 2021-08-03 22:25, olcott wrote:
>>>>> On 8/3/2021 11:16 PM, André G. Isaak wrote:
>>>>>> On 2021-08-03 22:00, olcott wrote:
>>>>>>> On 8/3/2021 10:56 PM, André G. Isaak wrote:
>>>>>>>> On 2021-08-03 21:23, olcott wrote:
>>>>>>>>
>>>>>>>>> The key point is that only the input to the halt decider is
>>>>>>>>> within the scope of the halting problem.
>>>>>>>>>
>>>>>>>>> As long as the halt decider correctly decides its input what
>>>>>>>>> these same programs do what they are not inputs to the halt
>>>>>>>>> decider make no difference to the actual halting problem.
>>>>>>>>
>>>>>>>> You have this completely back-assward.
>>>>>>>>
>>>>>>>> How the TM described by the input to a halt decider behaves when
>>>>>>>> they are run as *independent* computations (i.e. not as inputs
>>>>>>>> to the halt decider) is the question a halt decider is supposed
>>>>>>>> to answer by the very definition of a 'halt decider'. If the
>>>>>>>> answer provided by the decider does not match the behavior of
>>>>>>>> the *independent* computation, then that answer is wrong.
>>>>>>>>
>>>>>>>> Talking about how the description behaves "as an input" isn't
>>>>>>>> even coherent. Inputs don't behave like anything. They are just
>>>>>>>> data.
>>>>>>>>
>>>>>>>> André
>>>>>>>>
>>>>>>>
>>>>>>>     In computability theory, the halting problem is the
>>>>>>>     problem of determining,
>>>>>>>
>>>>>>> from a description of an arbitrary computer program and an input,
>>>>>>> from a description of an arbitrary computer program and an input,
>>>>>>> from a description of an arbitrary computer program and an input,
>>>>>>> from a description of an arbitrary computer program and an input,
>>>>>>>
>>>>>>>     whether the program will
>>>>>>>     finish running, or continue to run forever.
>>>>>>>     https://en.wikipedia.org/wiki/Halting_problem
>>>>>>>
>>>>>>> I have proved that the input to H(P,P) never halts whether or not
>>>>>>> it is aborted by H, are you going to have an honest dialogue
>>>>>>> about the steps of the proof or not?
>>>>>>
>>>>>> Yes, and when run H(P, P) the arbitrary program and input which it
>>>>>> is being given described P(P).
>>>>>>
>>>>>> It is supposed to answer how that *program* will behave. And you
>>>>>> have acknowledged that that program *halts*. That behaviour is
>>>>>> what *defines* the correct answer to the question 'does P(P)
>>>>>> halt'. And your H gets this *wrong*.
>>>>>>
>>>>>> The halting question is not concerned with how the input string
>>>>>> behaves inside your partial simulator. It is *only* concerned with
>>>>>> the actual, *independent* program P(P).
>>>>>>
>>>>>
>>>>> So in other words you insist on not going through my steps
>>>>> (a)(b)(c)(d) on page 6 and trying to find an error?
>>>>
>>>>
>>>> I already pointed out that your (b) has major errors in an earlier
>>>> post which you disregarded. I see no reason to repeat that.
>>>>
>>>
>>> I am not willing to talk about anything else.
>>
>> I am not willing to talk about anything besides page 6 until we have
>> mutual agreement on page 6.
>
> That's not going to happen since your argument on page 6 is fallacious.
>
> Read my earlier message <sebtb9$plb$1...@dont-email.me>
>
> I see no reason to repeat it.
>

You simply ignored my correction of your error.
I responded to this message again with words that are more clear.

Simply ignoring this response is sufficient proof that you are
unmotivated to have an actual honest dialogue.

olcott

unread,
Aug 4, 2021, 11:48:29 AM8/4/21
to
On 8/1/2021 11:00 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/1/2021 7:41 AM, Ben Bacarisse wrote:
>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>
>>>> On Sunday, 1 August 2021 at 11:54:57 UTC+1, Ben Bacarisse wrote:
>>>>>
>>>>> Here we can see that Ĥ applied to ⟨Ĥ⟩ halts. You can call your Ĥ's
>>>>> behaviour "correct". You can call it anything you like. But it's not
>>>>> "as in Linz". It does not say anything about Linz's proof. It does not
>>>>> do anything people would call impossible or even interesting.
>>>>>
>>>> It seems to be established that H(H_Hat, H_Hat) returns "non-halting"
>>>> whilst H_Hat(H_Hat) halts. So all is as Linz says it must be and no
>>>> theorems are refuted. Which you would expect. If results were consistent
>>>> it would have to be some cheap trick.
>>> I case there is some confusion, I mean that PO's Ĥ is not an Ĥ as
>>> specified in Linz. Yes, everything is in accordance with the truth as
>>> laid out in Linz and, indeed, in any textbook.
>>> I point this out to PO because he brings it up. He keeps posting the
>>> specification of what an Ĥ, as Linz specifies it, would do:
>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>> if (and only if) M applied to wM does not halt.
>>> He claims (or used to claim) that his Ĥ meets this specification for at
>>> least the one case where wM == ⟨Ĥ⟩:
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>>> To remain relevant, he /must/ keep insisting that his Ĥ meets the
>>> requirements laid out in Linz, if only for this one key input.
>>>
>>
>> Ĥ[0].q0 is taken to mean Ĥ<sub>0</sub>.q0 which is the Turing machine.
>>
>> Ĥ[1].q0 is taken to mean Ĥ<sub>1</sub>.q0 which is the Turing machine
>> description input to Ĥ[0].q0
>>
>> Ĥ[2].q0 is taken to mean Ĥ<sub>2</sub>.q0 which is first copy of the
>> Turing machine description input to Ĥ[0].q0
>>
>> Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn
>
> Ĥ[0] is Ĥ so you are confirming, yet again, that
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
>
>> It is neither a contradiction nor a paradox because there are three
>> different instances of Ĥ.
>
> I agree that this is neither a paradox nor a contradiction. It's just a
> fact derived form the logic of how your Ĥ is written (the majority of
> which you are keeping hidden from us).
>
>> Because the only reason that the first instance halts is that Ĥ[0].qx
>> correctly determines that its input cannot possibly ever reach its
>> final state of Ĥ[1].qn or Ĥ[1].qy whether or not the simulating halt
>> decider aborts its simulation of this input, we know with 100%
>> perfectly justified logical certainty that the input to Ĥ[0].qx never
>> halts.
>
> We know, since you keep telling us, that Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn. This clearly
> shows that Ĥ applied to ⟨Ĥ⟩ halts. You can see the final state right

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

You are using the wrong Ĥ. Linz stipulates that wM is ⟨Ĥ⟩ and M is the
underlying machine of this ⟨Ĥ⟩ therefore M applied to wM means ⟨Ĥ⟩
applied to ⟨Ĥ⟩. We can see that M never reaches its final state.

Because the input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ does specify infinitely nested
simulation we can know for sure that M never reaches its final state
whether or not Ĥ.qx aborts its simulation of M.

> there in the line you keep posting again and again. As far as I know,
> you have never disputed this fact.
>
> As you say, this is neither a paradox nor a contradiction. It just
> shows that Ĥ does not behave as Linz says it should, in the one case you
> have obsessed about for 17 years. Having an H (and thus an Ĥ) that is
> wrong (i.e. not "exactly and precisely as on Linz" as you once claimed)
> is trivial. It is not something that anyone (except Malcolm,
> apparently) would care about.

olcott

unread,
Aug 4, 2021, 12:16:04 PM8/4/21
to
> Maybe saying it a couple more times will help. After four times I can
> tell you that it's still wrong. Maybe about a dozen more?
>
> Whether what happens after Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is correct or not is determined
> by Linz, not by you. And you are clear that
>
> Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn.
>

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

As explained in complete detail below:
Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

because M applied to wM does not halt
where M is Machine_of(⟨Ĥ⟩) (1st param) above
and wM is ⟨Ĥ⟩ the second param above.

Because wM is referring to ⟨Ĥ⟩ and M is referring to the underlying
machine of ⟨Ĥ⟩ the last line above is translated to:
if Machine_of(⟨Ĥ⟩) applied to ⟨Ĥ⟩ does not halt

We can know that Machine_of(⟨Ĥ⟩) applied to ⟨Ĥ⟩ never reaches its final
state whether or not the embedded halt decider at Ĥ.qx aborts it
simulation of Machine_of(⟨Ĥ⟩), therefore we know that Machine_of(⟨Ĥ⟩)
never halts. Therefore we know that M applied to wM does not halt.

> Linz is equally clear that this is wrong. You even helpfully keep
> quoting Linz telling you it's wrong:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>
> You can repeat, again and again, that "Ĥ.qx correctly decides"
> something, but you've already told the world that the computation halts
> when is should not. Your Ĥ is not doing what it should to show a fault
> in Linz's proof. It's doing something else that is of no interest to
> anyone.
>
> (It's possible that just can't see why it is that those two lines from
> Linz are telling you that your Ĥ does is wrong. You've struggled with
> what this notation really means, so it's possible. But reasonable
> student would ask if they could not see that Linz is telling you your Ĥ
> is wrong.)
>
>> In computability theory, the halting problem is the problem of
>> determining, from a description of an arbitrary computer program and
>> an input, whether the program will finish running, or continue to run
>> forever https://en.wikipedia.org/wiki/Halting_problem
>
> Really? Well scan my tape and call me halting!
>
> If you had had the two TMs you lied about having (sorry, used "poetic
> license" to say you had) you could have run
>
> Ĥ.q0 ⟨Ĥ⟩
>
> and
>
> H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩
>
> and you would have seen, right away, that H(⟨Ĥ⟩ ⟨Ĥ⟩) is wrong about
> Ĥ(⟨Ĥ⟩). Maybe you did and that's why you've spent 30 months waking back
> that lie^H^H^H poetic license.

olcott

unread,
Aug 4, 2021, 6:31:08 PM8/4/21
to
> First of all, let's be 100% clear: I am talking about what /your/ Ĥ
> does, based in the facts you have let slip about it.
>
>> Linz stipulates that wM is ⟨Ĥ⟩ and M is the underlying machine of this
>> ⟨Ĥ⟩ therefore M applied to wM means ⟨Ĥ⟩ applied to ⟨Ĥ⟩.
>
> No. How many years have you been staring at this one page from Linz?
> You still don't know what it says. Do ask me questions, if you'd like
> to know what the text you've been sure is wrong for 17 years really
> says.
>

...Turing machine halting problem.
Simply stated, the problem is:
given the description of a Turing machine M
given the description of a Turing machine M
given the description of a Turing machine M
given the description of a Turing machine M
given the description of a Turing machine M

and an input w, does M, when started in the initial configuration q0w,
perform a computation that eventually halts?

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

Ĥ.q0 ⟨M⟩ ⊢* Ĥ.qx ⟨M⟩ ⟨M⟩ ⊢* Ĥ.qn
if M applied to ⟨M⟩ does not halt

When ⟨M⟩ = ⟨Ĥ⟩: I have proved that Ĥ ⟨M⟩ transitions to Ĥ.qn because M
never reaches a final state.

olcott

unread,
Aug 4, 2021, 6:38:33 PM8/4/21
to
> Yes, please don't tell me the final state yet again. This is not been
> in dispute for some time.
>
>> because M applied to wM does not halt
>> where M is Machine_of(⟨Ĥ⟩) (1st param) above
>> and wM is ⟨Ĥ⟩ the second param above.
>>
>> Because wM is referring to ⟨Ĥ⟩ and M is referring to the underlying
>> machine of ⟨Ĥ⟩ the last line above is translated to: if
>> Machine_of(⟨Ĥ⟩) applied to ⟨Ĥ⟩ does not halt
>
> That's convoluted. ⟨Ĥ⟩ is the encoding of Ĥ so to find out what Linz
> expects from Ĥ applied to ⟨Ĥ⟩ we just substitute M = Ĥ and wM = ⟨Ĥ⟩ into
> the above:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> if Ĥ applied to ⟨Ĥ⟩ does not halt.
>

It is not the first Ĥ that is being referred to it is *only* the machine
represented by the input ⟨Ĥ⟩ that is being referred to. That machine
never reaches its final state.

Ĥ.q0 ⟨Ĥ[1]⟩ ⊢* Ĥ.qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ.qn
if Ĥ[1] applied to ⟨Ĥ[2]⟩ does not halt.

That you persistently ignore this distinction really seems to be a
diverge from an honest dialogue.

>> We can know that Machine_of(⟨Ĥ⟩) applied to ⟨Ĥ⟩ never reaches its
>
> Machine_of(⟨Ĥ⟩) = Ĥ.
>
>> final state whether or not the embedded halt decider at Ĥ.qx aborts it
>
> You keep telling me that Ĥ applied to ⟨Ĥ⟩ reaches a final state. You
> even tell me the final state.
>
>> simulation of Machine_of(⟨Ĥ⟩), therefore we know that Machine_of(⟨Ĥ⟩)
>> never halts. Therefore we know that M applied to wM does not halt.
>
> You keep telling me that Ĥ applied to ⟨Ĥ⟩ reaches the final state Ĥ.qn.
> Are you changing your mind after all this time? No, you are searching
> for some form of words that will make the wrong answer sound right.

olcott

unread,
Aug 5, 2021, 8:07:12 AM8/5/21
to
On 8/5/2021 4:02 AM, Malcolm McLean wrote:
> On Thursday, 5 August 2021 at 04:18:21 UTC+1, olcott wrote:
>> On 8/4/2021 6:22 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>> If the various strings you've chosen to number (badly) are not identical
>>> then your "hat" construction is wrong. Linz's "hat" version makes an
>>> exact copy.
>>>
>> When Bill says that his identical twin brother is not going to go to the
>> store, and then Bill goes to the store this does not make him a liar.
>>
>>> You are free to write ⟨Ĥ[99]⟩ if you like, but I am also free to change
>>> that back to ⟨Ĥ⟩ because they are identical strings. Anything true of
>>>
>> Ĥ is not a string it is a Turing machine.
>> Turing machines are not identical to strings.
>> Ĥ halts the simulation of ⟨Ĥ⟩ on ⟨Ĥ⟩ never reaches its final state
>> whether or not the halt decider at Ĥ.qx stop simulating it.
>>
>> If you want an actual honest dialogue we must have closure on some of
>> the points. You must say what things you agree with and not merely
>> ignore those things that you agree with.
>>
>> Do you understand that the simulation of ⟨Ĥ⟩ on ⟨Ĥ⟩ never reaches its
>> final state whether or not the halt decider at Ĥ.qx stop simulating it?
>>
> H_Hat <H_Hat> halts. So if it is simulated by a UTM, the simulation
> UTM <H_HAT><H_Hat> also halts.

It is very easily proven that ⟨Ĥ⟩ on ⟨Ĥ⟩ cannot possibly ever reach its
final state. If it stops running without reaching is final state then
this does not count as halting.

> But the halt decider embedded in H_Hat is not a UTM. It's a near UTM,
> that has abort logic. Somewhere the abort logic must be triggered,
> which causes H_Hat<H_Hat> to halt.

If it stops running without reaching is final state then this does not
count as halting. It can not possibly reach its final state whether or
not its simulation is ever aborted, therefore it never halts.

> H<H_Hat><H_Hat> also triggers this abort logic, so H<H_Hat><H_Hat>
> reports "false" (non-halting).
>>
>> If you disagree then to prove that you are not simply being disagreeable
>> you must proceed with a dialogue on this single point until we reach
>> mutual agreement. All other points will not be discussed until we reach
>> mutual agreement on this point.
>>
> We agree that H_Hat<H_Hat> halts.
> We agree that H <H_Hat> <H_Hat> reports "false" (non-halting).
>
> Can't you see the obvious?
>

The mistake that you are making is counting stopping without reaching a
final state as halting, it is not.

olcott

unread,
Aug 11, 2021, 10:28:39 AM8/11/21
to
On 8/10/2021 9:26 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/10/2021 8:41 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/10/2021 7:42 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 8/7/2021 7:34 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 8/5/2021 9:36 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 8/5/2021 5:14 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
>>>>>>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>>>>>>>>>>
>>>>>>>>>>>> The question is not: Does Ĥ halt on its input?
>>>>>>>>>>> Yes it is.
>>>>>>>>>>
>>>>>>>>>> The question is:
>>>>>>>>>> Does the Ĥ specified by the first ⟨Ĥ⟩ halt on its input ⟨Ĥ⟩ ?
>>>>>>>>>> The ansswer to this question is provably no!
>>>>>>>>> The question is: does Ĥ applied to ⟨Ĥ⟩ halt. It does:
>>>>>>>>>
>>>>>>>>>> Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn THIS IS NOT A CONTRADICTION
>>>>>>>>> Indeed. There is no contradiction. Just an Ĥ that does not meet Linz
>>>>>>>>> spec.
>>>>>>>>
>>>>>>>> Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn is correct and forms no contradiction.
>>>>>>>> Because it is correct it meets the Linz spec.
>>>>>>> I find it startling that you think that, but then it seems you don't yet
>>>>>>> know what the key words mean:
>>>>>>>
>>>>>>>> if M applied to wM does not halt
>>>>>>>> means if the execution of the machine of the first ⟨Ĥ⟩ on its input of
>>>>>>>> the seocond ⟨Ĥ⟩ does not halt then ⊢* Ĥ.qn
>>>>>>> No. Would you like to know "what M applied to wM does not halt" means?
>>>>>>> Do you need help to see that "Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn" is clearly a case of "M
>>>>>>> applied to wM halts"?
>>>>>>
>>>>>> the Turing machine halting problem. Simply stated, the problem
>>>>>> is: given the description of a Turing machine M and an input w,
>>>>>> does M, when started in the initial configuration q0w, perform a
>>>>>> computation that eventually halts? (Linz:1990:317).
>>>>> Yes. I was offering to help you understand the key words in that text.
>>>>>
>>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>> You've missed off the key lines yet again. Is that deliberate? They
>>>>> are the lines that show you are wrong so I am suspicious that you keep
>>>>> omitting them.
>>>>>
>>>>>> When Ĥ is applied to ⟨Ĥ⟩ the description of the Turing Machine and its
>>>>>> input are specified as: ⟨Ĥ⟩ ⟨Ĥ⟩ for the embedded halt decider at Ĥ.qx.
>>>>> Ungrammatical.
>>>>>
>>>>>> When Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn this is not a final state of the simulated
>>>>>> input it is a final state of the executed Ĥ.
>>>>> Yes. You don't seem to know why that's wrong.
>>>>
>>>> What is your basis for believing that is wrong?
>>> Ah, a question about what I'm saying. I can help there. The basis is
>>> what Linz says about Ĥ. He says that (translating to your notation)
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn
>>> should be the case "if Ĥ applied to ⟨Ĥ⟩ does not halt". But, as you can
>>> see, your Ĥ does halt when applied to ⟨Ĥ⟩ (qn is a halting or final
>>> state). Your Ĥ is not doing what it should in this one crucial case.
>>>
>>
>> the Turing machine halting problem. Simply stated, the problem
>> is: given the description of a Turing machine M and an input w,
>> does M, when started in the initial configuration q0w, perform a
>> computation that eventually halts? (Linz:1990:317).
>
> and so on. Same old stuff.
>

When the challenge to support one's assertion with reasoning is simply
ignored as you are ignoring it right now one can reasonably construe a
deceptive intent.

-- the Turing machine halting problem. Simply stated, the problem
-- is: given the description of a Turing machine M and an input w,
-- does M, when started in the initial configuration q0w, perform a
-- computation that eventually halts? (Linz:1990:317).

PROOF THAT M REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO H
PROOF THAT M REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO H
PROOF THAT M REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO H
PROOF THAT M REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO H

The input to H will be the description (encoded in some form) of M, say
WM, as well as the input w. (Linz:1990:318)

H.q0 WM w ⊢* H.qn
if M applied to W does not halt.

becomes

H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
if Ĥ applied to ⟨Ĥ⟩ does not halt.


Pages of the Linz text to verify the above quotes in their full context:
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

M STILL REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO Ĥ.qx
M STILL REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO Ĥ.qx
M STILL REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO Ĥ.qx
M STILL REFERS TO THE TURING MACHINE DESCRIPTION PARAMETER WM TO Ĥ.qx

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

When we know that M refers to the Turing machine specified by the first
wM then when Ĥ transitions to its final state of Ĥ.qn there is no direct
contradiction formed.

Can you admit when you are wrong when you really are wrong?
Can you admit when you are wrong when you really are wrong?
Can you admit when you are wrong when you really are wrong?
Can you admit when you are wrong when you really are wrong?

if M applied to wM does not halt (see above for definition of M)
means when the Turing machine of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
Ĥ.qx correctly transitions to its final state when the Ĥ.qx acts as a
UTM and simulates ⟨Ĥ⟩ ⟨Ĥ⟩ and determines that this input never halts.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

> I'm sorry my explanation did not help at all. I'm happy to answer any
> other questions you might have if you think it might help you understand
> what I (and Linz) are saying.

olcott

unread,
Aug 11, 2021, 10:58:33 AM8/11/21
to
if M applied to wM halts, and // M refers to the TM of the first wM
parameter to Ĥ.qx

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt // M refers to the TM of the first wM
parameter to Ĥ.qx

olcott

unread,
Aug 11, 2021, 3:53:18 PM8/11/21
to
On 8/11/2021 11:10 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/11/2021 9:28 AM, olcott wrote:
>
> Subject: Re: Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn is correct and forms no
> contradiction. [ Is Ben a Liar or simply woefully ignorant? ]
>
> This is a scumbag move. It's also cowardly and disingenuous --
> pretending to be coy about your scumbag opinions. I'll leave it
> unedited as it says everything readers need to know about your
> character.
>
>>> When the challenge to support one's assertion with reasoning is simply
>>> ignored as you are ignoring it right now one can reasonably construe
>>> a deceptive intent.
>
> A scumbag could construe it that way. Reasonable people could come to
> all sorts of other conclusions.
>
>>> H.q0 WM w ⊢* H.qn
>>> if M applied to W does not halt.
> if M applied to MW does not halt.
>
> (typo corrected)
>
>>>   becomes
>>> H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
>>> if Ĥ applied to ⟨Ĥ⟩ does not halt.
>
> Yes. After a lot a pressing (and I mean lots, over several years!) you
> eventually admitted that H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ does indeed transition to H.qn.
> You also keep telling us that Ĥ applied to ⟨Ĥ⟩ halts. That's why your H
> (and its associated Ĥ) are wrong but for some reason you can't see this.
>
> You will plainly state that H rejects the string "⟨Ĥ⟩ ⟨Ĥ⟩" which it
> should do if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt. And you
> will, time and time again, show us exactly how Ĥ applied to ⟨Ĥ⟩ halts.
>
> This should be the end of the matter, but apparently your stating facts
> that show that H and Ĥ are wrong does not mean you know that H and Ĥ are
> wrong. I don't think I know any way to make progress on this.
>
>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>> if M applied to wM does not halt
> ...
>>> if M applied to wM does not halt (see above for definition of
>>> M) means when the Turing machine of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt.
>
> Of course. We all know that. Unless you are pulling a fast one. "the
> Turing machine of ⟨Ĥ⟩" is just Ĥ. Is there a reason you are not simply
> saying "when Ĥ applied to ⟨Ĥ⟩ does not halt"?
>
>>> Ĥ.q0 ⟨Ĥ⟩  ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>> Ĥ.qx correctly transitions to its final state when the Ĥ.qx acts as a
>>> UTM and simulates ⟨Ĥ⟩ ⟨Ĥ⟩ and determines that this input never halts.
>
> Yes, we know the ruse: the computation would not halt if it were not the
> computation that it is. You've been trying to pull off this trick ever
> since the infamous "it wouldn't halt if line 15 was commented out"
> admission. Your Ĥ, however, not being a UTM, has the property that
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> when it should not. Ĥ.q0 ⟨Ĥ⟩ should eventually transition to qn only
> "if Ĥ applied to ⟨Ĥ⟩ does not halt" (or, as you rather suspiciously
> write "if the Turing machine of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt"). But
> you've told us, time and time again, that Ĥ applied to ⟨Ĥ⟩ halts. You
> keep showing us the summary description of it's configuration sequence.
> You keep showing us the final state it transitions to. It's so obvious,
> someone would need about 16 years misunderstanding Turing machines to
> avoid seeing it.
>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and // M refers to the TM of the first wM
>> parameter to Ĥ.qx
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt // M refers to the TM of the first wM
>> parameter to Ĥ.qx
>
> The case you care about has M = Ĥ and wM = ⟨Ĥ⟩ as you've written it out
> above.
>

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn // see highlighted portion of Linz text
to confirm:
if M applied to wM does not halt // M refers to the TM of the first
wM parameter to Ĥ.qx

Turing machine Ĥ is applied to its input ⟨Ĥ⟩. It copies this input such
that this input and the copy of this input become the first and second
parameters to the simulating halt decider at Ĥ.qx. When Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
decides that the simulation of its first parameter on the input of its
second parameter never halt it correctly transitions to its own final
state of Ĥ.qn.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

olcott

unread,
Aug 11, 2021, 8:26:24 PM8/11/21
to
On 8/11/2021 7:01 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/11/2021 11:10 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/11/2021 9:28 AM, olcott wrote:
>>> Subject: Re: Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn is correct and forms no
>>> contradiction. [ Is Ben a Liar or simply woefully ignorant? ]
>>>
>>> This is a scumbag move. It's also cowardly and disingenuous --
>>> pretending to be coy about your scumbag opinions. I'll leave it
>>> unedited as it says everything readers need to know about your
>>> character.
>
> This is still a scumbag move.
>
>>>>> When the challenge to support one's assertion with reasoning is simply
>>>>> ignored as you are ignoring it right now one can reasonably construe
>>>>> a deceptive intent.
>>> A scumbag could construe it that way. Reasonable people could come to
>>> all sorts of other conclusions.
>>>
>>>>> H.q0 WM w ⊢* H.qn
>>>>> if M applied to W does not halt.
>>> if M applied to MW does not halt.
>>> (typo corrected)
>>>
>>>>>   becomes
>>>>> H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
>>>>> if Ĥ applied to ⟨Ĥ⟩ does not halt.
>>>
>>> Yes. After a lot a pressing (and I mean lots, over several years!) you
>>> eventually admitted that H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ does indeed transition to H.qn.
>>> You also keep telling us that Ĥ applied to ⟨Ĥ⟩ halts. That's why your H
>>> (and its associated Ĥ) are wrong but for some reason you can't see this.
>>>
>>> You will plainly state that H rejects the string "⟨Ĥ⟩ ⟨Ĥ⟩" which it
>>> should do if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt. And you
>>> will, time and time again, show us exactly how Ĥ applied to ⟨Ĥ⟩ halts.
>>>
>>> This should be the end of the matter, but apparently your stating facts
>>> that show that H and Ĥ are wrong does not mean you know that H and Ĥ are
>>> wrong. I don't think I know any way to make progress on this.
>
> You just read past this explanation of why your H and Ĥ are wrong and
> you decided that you understood everything I'd said, did you? And you
> also decided that nothing in these three paragraphs needs to be
> challenged?
>

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

// M refers to the TM of the first wM parameter to Ĥ.qx

Now that you accept that the above is true we can move on to the next
point. My proof must proceed exactly one point at a time an cannot
possibly move to the next point until the current point is fully accepted.

That you believe that the fact that Ĥ applied to ⟨Ĥ⟩ transitions to its
final state of Ĥ.qn and halts nullifies the fact that Ĥ.qx wM wM does
correctly decide that its input never halts is the next point.

It is easier to discuss this with the H(P,P) model of the exact same
thing because with the H(P,P) model we can examine every single detail.

_P()
[00000d02](01) 55 push ebp
[00000d03](02) 8bec mov ebp,esp
[00000d05](03) 8b4508 mov eax,[ebp+08]
[00000d08](01) 50 push eax // push 2nd Param
[00000d09](03) 8b4d08 mov ecx,[ebp+08]
[00000d0c](01) 51 push ecx // push 1st Param
[00000d0d](05) e870feffff call 00000b82 // call H
[00000d12](03) 83c408 add esp,+08
[00000d15](02) 85c0 test eax,eax
[00000d17](02) 7402 jz 00000d1b
[00000d19](02) ebfe jmp 00000d19
[00000d1b](01) 5d pop ebp
[00000d1c](01) c3 ret
Size in bytes:(0027) [00000d1c]

...[00000d0d][00101829][00000d12] e870feffff call 00000b82 // call H

Begin Local Halt Decider Simulation at Machine Address:d02
...[00000d02][002118f1][002118f5] 55 push ebp
...[00000d03][002118f1][002118f5] 8bec mov ebp,esp
...[00000d05][002118f1][002118f5] 8b4508 mov eax,[ebp+08]
...[00000d08][002118ed][00000d02] 50 push eax // push P
...[00000d09][002118ed][00000d02] 8b4d08 mov ecx,[ebp+08]
...[00000d0c][002118e9][00000d02] 51 push ecx // push P
...[00000d0d][002118e5][00000d12] e870feffff call 00000b82 // call H

...[00000d02][0025c319][0025c31d] 55 push ebp
...[00000d03][0025c319][0025c31d] 8bec mov ebp,esp
...[00000d05][0025c319][0025c31d] 8b4508 mov eax,[ebp+08]
...[00000d08][0025c315][00000d02] 50 push eax // push P
...[00000d09][0025c315][00000d02] 8b4d08 mov ecx,[ebp+08]
...[00000d0c][0025c311][00000d02] 51 push ecx // push P
...[00000d0d][0025c30d][00000d12] e870feffff call 00000b82 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

It is very obvious to people that know the x86 language very well that
while H acts as a pure simulator of P(P) that P cannot possibly stop
running.

The same thing applies to the infinite cycle from Ĥ.qx to Ĥ.q0 while the
simulating halt decider at Ĥ.qx acts as a UTM.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

// M refers to the TM of the first wM parameter to Ĥ.qx


> There's not much more I can add if you do indeed understand and accept
> these remarks of mine. But, as I keep saying, I'm happy to answer any
> questions you may have about my explanation.

olcott

unread,
Aug 11, 2021, 10:14:07 PM8/11/21
to
On 8/11/2021 8:35 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/11/2021 11:10 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/11/2021 9:28 AM, olcott wrote:
>
>>>>> H.q0 WM w ⊢* H.qn
>>>>> if M applied to W does not halt.
>>> if M applied to MW does not halt.
>>> (typo corrected)
>>>
>>>>>   becomes
>>>>> H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn
>>>>> if Ĥ applied to ⟨Ĥ⟩ does not halt.
>>> Yes. After a lot a pressing (and I mean lots, over several years!) you
>>> eventually admitted that H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ does indeed transition to H.qn.
>>> You also keep telling us that Ĥ applied to ⟨Ĥ⟩ halts. That's why your H
>>> (and its associated Ĥ) are wrong but for some reason you can't see this.
>>> You will plainly state that H rejects the string "⟨Ĥ⟩ ⟨Ĥ⟩" which it
>>> should do if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt. And you
>>> will, time and time again, show us exactly how Ĥ applied to ⟨Ĥ⟩ halts.
>>> This should be the end of the matter, but apparently your stating facts
>>> that show that H and Ĥ are wrong does not mean you know that H and Ĥ are
>>> wrong. I don't think I know any way to make progress on this.
>>>
>>>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>>>>> if M applied to wM does not halt
>>> ...
>>>>> if M applied to wM does not halt (see above for definition of
>>>>> M) means when the Turing machine of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt.
>>> Of course. We all know that. Unless you are pulling a fast one. "the
>>> Turing machine of ⟨Ĥ⟩" is just Ĥ. Is there a reason you are not simply
>>> saying "when Ĥ applied to ⟨Ĥ⟩ does not halt"?
>
> I didn't expect an answer. You may be reserving this phrase as a
> get-out clause for later, so saying what you mean too early will block
> that escape route.
>
>>>>> Ĥ.q0 ⟨Ĥ⟩  ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>>>> Ĥ.qx correctly transitions to its final state when the Ĥ.qx acts as a
>>>>> UTM and simulates ⟨Ĥ⟩ ⟨Ĥ⟩ and determines that this input never halts.
>>> Yes, we know the ruse: the computation would not halt if it were not the
>>> computation that it is. You've been trying to pull off this trick ever
>>> since the infamous "it wouldn't halt if line 15 was commented out"
>>> admission. Your Ĥ, however, not being a UTM, has the property that
>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>>> when it should not. Ĥ.q0 ⟨Ĥ⟩ should eventually transition to qn only
>>> "if Ĥ applied to ⟨Ĥ⟩ does not halt" (or, as you rather suspiciously
>>> write "if the Turing machine of ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt").
>>
>> We can see that the above never halts.
>
> We can see that it halts. It's right there in a fact that has been
> undisputed for months:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>

The above Ĥ halts only because Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decides that its
input never halts.

the Turing machine halting problem. Simply stated, the problem
is: given the description of a Turing machine M and an input w,
does M, when started in the initial configuration q0w, perform a
computation that eventually halts? (Linz:1990:317).

Thus the halting problem is solved for this input because the halting
problem only applies to inputs. It does not apply to computations that
are not inputs.

olcott

unread,
Aug 12, 2021, 4:36:09 PM8/12/21
to
On 8/12/2021 3:00 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt
>>
>> // M refers to the TM of the first wM parameter to Ĥ.qx
>>
>> Now that you accept that the above is true...
>
> I don't. It's a garbled formula arising from a silly error on your
> part. I'd like to know where (you think) I said I accept this nonsense
> so I can correct any such impression.
>
>> ... we can move on to the next point. My proof must proceed exactly
>> one point at a time an cannot possibly move to the next point until
>> the current point is fully accepted.
>
> It would be simpler if we worked though the reasons you are wrong
> because there are fewer steps.
>
> You've stated that
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> and you accept (at least you keep quoting) that Linz requires that this
> should be the case only if Ĥ applied to ⟨Ĥ⟩ does not halt. QED.
>
>> That you believe that the fact that Ĥ applied to ⟨Ĥ⟩ transitions to
>> its final state of Ĥ.qn and halts nullifies the fact that Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
>> does correctly decide that its input never halts is the next point.
>
> ⟨Ĥ⟩ ⟨Ĥ⟩ is a string that encodes a halting computation as shown a few
> lines above. That Ĥ applied to ⟨Ĥ⟩ halts does not "nullify" anything,
> it's just wrong as clearly stated by Linz.
>

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation.

Ĥ is a TM that halts only because
Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decides that its input never halts.

When you examine this in its x86utm equivalent of H(P,P) there are no
loopholes that can slip through the cracks because every detail is
explicitly encoded in the x86 language.

When we examine this as Ĥ applied to ⟨Ĥ⟩ there are millions of pages of
Turing machine code that cannot be explicitly specified.

None-the-less the key element of all this is the fact that if we assume
that the simulating halt decider at Ĥ.qx is simply a UTM then it becomes
quite obvious that we have an infinite cycle from Ĥ.qx to Ĥ.q0.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

If we know that we have an infinite cycle then this knowledge all by
itself proves that the simulating halt decider at Ĥ.qx must abort the
simulation of its input which proves that this input never halts.
0 new messages