Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

[It is] best to confuse only one issue at a time. -- K&R

computers / / Re: How do we know H(P,P)==0 is the correct halt status for the input to H? [ distinct computations ]

Subject: Re: How do we know H(P,P)==0 is the correct halt status for the input to H? [ distinct computations ]
From: olcott
Newsgroups: comp.theory,,, sci.math.symbolic
Date: Tue, 24 Aug 2021 03:52 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
NNTP-Posting-Date: Mon, 23 Aug 2021 22:52:06 -0500
Subject: Re: How do we know H(P,P)==0 is the correct halt status for the input
to H? [ distinct computations ]
Newsgroups: comp.theory,,,sci.math.symbolic
References: <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <>
<> <>
From: (olcott)
Date: Mon, 23 Aug 2021 22:52:04 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <>
Lines: 245
X-Trace: sv3-y18WS8hrOd0zB16OIpVMbb6Qzgkaea/y4GLR1y3owGQa/IWVuSiZtQwkLj0YShGl2OfNLtpIQEfmQxP!H12jLTsvxOc0ipRpHtAsRl1pXiE/br80TuoAGEmI/g37s74JNrj88loxOofJMTZ49SUFo8Z2Z9pl!9dU=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 11874
View all headers
On 8/23/2021 10:09 PM, Ben Bacarisse wrote:
olcott <> writes:

On 8/23/2021 6:26 PM, Ben Bacarisse wrote:
olcott <> writes:

On 8/23/2021 2:30 PM, Ben Bacarisse wrote:
olcott <> writes:

I ignore dishonest dodges away from the point at hand.
OK, let's do that:
    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation"
is wrong.  You wrote that immediately after a line showing that Ĥ
applied to ⟨Ĥ⟩ halts.  Everything since then has just been dodging this

When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx
instead of a simulating halt decider then we can see that Ĵ applied to
⟨Ĵ⟩ never halts.
The details are mess, but basically, yes.  Detail errors (that would get
your paper rejected out of hand) available if you ask really nicely.

Which details do you think are incorrect?

A UTM is not a decider so the hat construction can't be applied to it.
And if we make a "UTM-decider" (a TM that is a pure simulator except
that is accepts those computations whose simulations terminate) we still
can't apply the hat construction because it won't have a rejecting
state.  Thus your use of "exactly like Ĥ except..." is, at best,
disingenuous.  The differences must be greater than the "except..."
clause suggests.

My whole purpose was to simply show what happens when the simulating halt decide at Ĥ.qx only simulates its input.

We can still have the same final states, except now that are unreachable dead code.

There is an infinite cycle from Ĵ.qx to Ĵ.q0.
No, but that's just because you've never written a UTM so you don't know
how such a TM would work.  Ĵ applied to ⟨Ĵ⟩ is non-halting but there
will not be a cycle from Ĵ.q0 -> Ĵ.qx -> Ĵ.q0...[1]

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

Eh?  You've just said that Ĵ applied to ⟨Ĵ⟩ is non-halting.  Do you know
what this notation means?
And you have another problem which shows how shallow your thinking is.
What is the state qn supposed to mean when J is a UTM?

Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

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

Is it really that difficult to understand that I merely swapped Ĵ for
Ĥ in the Ĥ template to create the Ĵ tempate?

I understand that you think you can just say that, but I also understand
the "template" better than you appear to.

Presumably you
agree with my wording and, in fact, J is a UTM that can only halt when
simulating halting computations.  So what's qn doing there?  (J must
have a qn for Ĵ to have qn.)

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

Do you know this means that you are claiming that Ĵ applied to ⟨Ĵ⟩

I am not claiming that. I am making a single change to Ĥ that now has some unreachable dead code states.

You just claimed the opposite.  I think you are just typing
symbols because they look good.

Ĵ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 ...

No.  Totally wrong.  Your understanding of how a UTM works is
embarrassingly shallow and I simply don't have time to explain it to
you.  In addition, you appear resistant to learning, so it would also be
pointless.  I can only suggest you change you attitude to learning and
then read a book, Linz for example.

If the Ĥ template stipulates that those actions occur then they occur when Ĥ has the one single modification of changing the simulating halt decider at Ĥ.qx to a UTM.

H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĥ.qn
Typo: H.qn not Ĥ.qn.

Yes, typo.

When we apply the original H to ⟨Ĵ⟩ ⟨Ĵ⟩ it transitions to its final
state of H.qn
If you say so.  I can't know because you are hiding H

It is the Linz H.

Since, against my repeated advice, you chose to use the same symbol for
your actual TM as Linz does for his empty class of TMs you need to be
more careful distinguishing them.

Apparently most all of the textbooks call this H.

 "The original H" is not clear and
discussion of it should be phrased hypothetically.  You should talk
about what Linz's H is specified to do, not what it does.

Yes that makes sense.

But since you brought up Linz's H, here's a question (get your avoidance
waffle ready!).  What is Linz's H specified to do when applied to your
⟨Ĥ⟩ ⟨Ĥ⟩?  For clarity, let Linz's H be called L just for now.  What goes
after the ⊢* here:

I am breaking that analysis down to its simpler components. We take the Linz Ĥ and change the simulating halt decider at Ĥ.qx to a UTM and rename this new machine Ĵ. The new machine has come dead code staes that are never reached.

Now we apply the Linz H to ⟨Ĵ⟩ ⟨Ĵ⟩ and H transitions to its final state of H.qn indicating that Ĵ applied to ⟨Ĵ⟩ never halts.

   L.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* ?

I really expect an answer to this.  If you can't answer, be honest and
say you can't.

Maybe it is easier now.

(well, you don't
actually have a TM H we are just playing pretend here).  For all I know,
your H gets this case wrong as well, but I am prepared to accept what
you say about it.

It is the Linz H: Nitwit !!!

You should give some thought to being more respectful.

I only call people a nitwit when they seem to being too disrespectful to me. Richard disrespectfully fails to distinguish between the words "before" and "after" so I gave up on him.

I cannot believe that he actually fails to understand what all grade school kids understand, he is merely playing head games beyond my tolerance threshold.

Can you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not
computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩
⟨Ĵ⟩ ?

I am not going to answer trivial, patronising questions.

It it a mandatory prerequisite to the next step of my proof that you
are persistently (intentionally ?) failing to understand.

Don't be daft.  You can present your argument whether or not I answer
your patronising questions.  If you choose not to, that suits me better
because there will be fewer errors to point out if you keep it to

If you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not
computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩ ⟨Ĵ⟩

then you should be able to understand that

the direct execution of Ĥ on input ⟨Ĥ⟩ is not computationally
equivalent to simulating halt decider at Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩.

That is beyond absurd.  I leave it to you spot the silly error in your
reasoning (though you almost certainly won't be able to).  And you will
need to account for the fact that both

My only "error" is that you very persistently and thus disrespectfully fail to bother to pay attention to my proof that this is correct.

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
   if (H(x, x))
     HERE: goto HERE;

int main()
   Output("Input_Halts = ", H((u32)P, (u32)P));
   Output("Input_Halts = ", H1((u32)P, (u32)P));

The fact that the first line of main() does produce different results than the second line of main conclusively proves that these two computations are computationally distinct different computations.

The first line of main() decides that its input never halts. Because it is the only halt decider it must abort the simulation of its input or its input never halts.

The second line of main() uses an exact copy H1 of H and reports that its input halts. It can see that another halt decider will abort its input.

The third lines of main() halts.

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn  (via Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩)


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

and how that can be true of computations that are not "computationally
equivalent".  (You don't give the final state of the tape but it will be
the same in both cases.)  Let me be clear: the reasoning is silly (how
you go from one assertion to the next) and the conclusion is wrong.
This is not "failing to understand" it is "knowing more about the
subject than you do".

Your understanding of TM computations is woefully inadequate to discuss
these matters.  Almost everything you say contains errors, many of them
huge errors that render your arguments null and void.  Even so, nothing
you say addresses the reason why your H is not a halt decider.  Your H
(not Linz's H) rejects a string that encodes a halting computation.
It's as simple as that.

TM's always leave most of their behavior to the imagination.
The C code that I referenced is fully operational and shows every step.

Copyright 2021 Pete Olcott

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

o How do we know H(P,P)==0 is the correct halt status for the input to

By: olcott on Sat, 14 Aug 2021

rocksolid light 0.7.2