Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

COBOL is for morons. -- E. W. Dijkstra

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 15:49 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: Tue, 24 Aug 2021 10:49:42 -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: Tue, 24 Aug 2021 10:49:40 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0
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: 465
X-Trace: sv3-trY0X0/vxGAhGOZ3PgvnAs7jClnoK6dAGBTkeIikazdxAyr9XYcgNRz0OWOTgG9qvXLav1uzELeYQk8!YBgUFHYjGft1KBxb9e2Y3zweIIvq7am/BnR328Siz/oT6pxnUycW2MZt2wMflme3+1gRN6FubSqU!Q4E=
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: 21726
View all headers
On 8/24/2021 9:09 AM, Ben Bacarisse wrote:
olcott <> writes:

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.

I know, but you wanted to know what details you'd got wrong.

If my plan was to swap the simulating halt decider at Ĥ.qx with a UTM and then rename this machine to Ĵ and I did swap swap the simulating halt decider at Ĥ.qx with a UTM and rename this machine to Ĵ then it is a God damned lie that I got anything wrong.

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

Except you show below this unreachable state being reached:

No I do frigging not. The code is still there but the infinite cycle from Ĵ.qx to Ĵ.q0 prevents it from ever being reached.

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

The TM at Ĵ.qx is your "UTM-decider" with an unreachable reject state.
Do you see why I don't think you know what you are saying?

The you imagine what I mean to say instead of examining what I actually say is your mistake.

This machine
Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

is transformed into this machine:
Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn // a machine stuck in
infinitely nested simulation

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.

This needs to be addressed.

That you don't believe that there is a cycle from Ĵ.qx to Ĵ.q0 is flatly wrong. The design of Ĥ as a simulating halt decider stipulates that there is a cycle from Ĥ.qx to Ĥ.q0. Changing the simulating halt decider at Ĥ.qx to a UTM at Ĵ.qx makes this cycle infinite.

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.

So why did you write Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn? 

Because that <is> the Ĥ code with the single adaptation of swapping the simulating halt decider at Ĥ.qx with a UTM at Ĵ.qx.

You wrote a
formal description of something that is impossible (qn is unreachable if
it exists at all) and which even if it were possible is not what Ĵ
applied to ⟨Ĵ⟩ does?  No, you wrote something daft without thinking or
maybe without know what it meant.

I wanted to make a single change to Ĥ so that I could show that the input to Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ really does specify an infinite cycle that must be aborted by its simulating halt decider. You seemed to be having an impossibly difficult time understanding this.

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

Which state?  Ĵ.qn?  The one you show Ĵ.q0 ⟨Ĵ⟩ transitioning to?  Yeah,

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

No.  Give this up.  You don't understand what a UTM is, and I can't
possibly teach you.  You have the result you want: the "other TM
computation" is non-halting but it does not do that in the way you
think, but if you keep giving details, I'll have to keep replying that
you are wrong.

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

Yes, typo.
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.

Which is further evidence that you should not.  These books use H to
refer to a hypothetical member of an empty class of TMs.  Your H is
real.  It does stuff.  It is not a member of an empty set.  And gets at
least one instance of the halting problem wrong because your H rejects
the string ⟨Ĥ⟩ ⟨Ĥ⟩.

When I refer to the Linz H it is still hypothetical because I do not show all of the steps.

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.

So you are not going to answer.  OK, it was a lot to expect -- a direct
answer to a simple question.

Do you think that the Linz H might possibly do what Linz specified or do you think that maybe I mean for it to go to the store and buy some groceries? It is a very disingenuous question. Beside that I am freaking applying the Linz H to ⟨Ĵ⟩ ⟨Ĵ⟩, not ⟨Ĥ⟩ ⟨Ĥ⟩.

If you want to see the result of applying a halt decider to a machine with its own halt decider look at:

// 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 = ", H1((u32)P, (u32)P));

H1 is an exact copy of H and in the above configuration decides that P halts.

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.

That won't help you say what Linz's H specified to do when applied to
/your/ ⟨Ĥ⟩ ⟨Ĥ⟩.  Note: to your ⟨Ĥ⟩ ⟨Ĥ⟩.

The question is off-topic.
I am only applying Ĥ to ⟨Ĥ⟩ or H to ⟨Ĵ⟩.

Because of my recent empirical analysis with H1/P it would seem that H applied to ⟨Ĥ⟩ would transition to its final state of H.qy. Prior to this empirical analysis I had no way to verify what would happen.

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

Which is not what I was asking about.

I just answered that.

    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.

For who?  I already know the answer.  I am asking you because you can't
(or dare not) say.

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

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

I have never seen anything remotely resembling a proof from you.  And
you reasoning above is absurd.  It's absurd and it results in an
incorrect conclusion.

The proofs are what the H/P code actually does and why it does this.
It is true that the input to H(P,P) would never halt unless H aborts the simulation of its input. This is easily verified by the execution trace of the code.

It is true that whenever the input to a simulating halt decider would never halt unless this simulating halt decider aborts the simulation of this input that this simulating halt decider does correctly decide that this input never halts. You already agreed to this.

On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
 > olcott <> 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.

This leaves no legitimate basis for rebuttal.
This leaves no legitimate basis for rebuttal.
This leaves no legitimate basis for rebuttal.
This leaves no legitimate basis for rebuttal.

int main() { H1(P,P); }
int main() {  P(P); }

The fact that the above pair agree also eliminates the illegitimate basis for rebuttal.

Part of the problem is that you don't know what a proof is.  I mean that

Valid deduction on the basis of verifiably true premises <is> a proof anyone that does not understand this is a numbskull.

literally.  Your ancient error about entailment suggests that you think
you can just add "stipulations" that make theorems into non-theorems.

This is my only theorem, the rest is simply seeing what actual code actually does and why it does it:

Simulating Halt Decider Theorem (Olcott 2020):
A simulating halt decider correctly decides that any input that never halts unless the simulating halt decider aborts its simulation of this input is an input that never halts.

It means you think you don't need to address the original argument
because you think you can invalidate it with other "true" things.  You
may not know it, but this makes your "arguments" laughable in the eyes
of educated readers.  Some will find not paying attention to them the
most respectful thing they can do.

That your "rebuttals" merely side step key points might seem to be valid for ignorant gullible people not understanding the material well enough to see that you simply dodged the actual reasoning.

Not only have you no proof, there is a trivial and concrete argument
that you are wrong: ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the halting computation of Ĥ applied
to ⟨Ĥ⟩.  H incorrectly reject that string.

By this same reasoning we could say that P(P) encodes a halting computation yet in this case we can directly see all of the details of how you are proved wrong.

Gullible ignorance people take emotionally charged rhetoric as equivalent to proof. They need not see any actual evidence. As long as someone in their reference group displays great confidence that their baseless accusation is correct then take this as proof that it is correct.

Donald Trump's best approval rating ever was an election losing -3.9% This is such a large election losing margin that it could not have been overturned by the electoral college.

Gullible fools that don't believe in approval ratings need to ask themselves if approval ratings can be manipulated then why didn't their people manipulate an approval rating to counter the many different scientific polls that were against Trump?

I've cut the waffle about C code.  The theorem, and the error we are
currently discussing are about the behaviour or TMs.

The x86 code generated from the C code can be verified to do what its specifies and it can also be verified that its decision basis is correct. Most of the details of TM proofs can at best only be imagined. These leaves huge gaps such that what is imagined does not correspond to what actually occurs.

The C/x86 model of computation is known to be Turing equivalent on the basis of the RASP model for all computations that have all of the memory that they need. As long as an x86 function is a pure function of its inputs the C/x86 model of computation can be fully relied upon as a much higher level of abstraction of the behavior of actual Turing machines.

And I've moved some quoted material to help with the context:

  And you will need to account for the fact that both

     Ĥ.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.)

See?  Every important question you just duck.  Your claim that

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

Ĥ applied to ⟨Ĥ⟩ is equivalent to int main() { P(P); } both halt.

Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ is equivalent to H(P,P) booth abort the simulation of their inputs.

is simply wrong based on facts you keep posting.  I suspect you just
don't know what any of this means and you are totally out of your
depth.  Mind you, you flop about on this issue.  Elsewhere you only
claim that the computations are distinct.  Of course they are distinct.
But here you talk about computational equivalence without, I suspect,
knowing what that means for TMs.

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.

No, you've just never written one or even understood one that someone
else wrote.

Show me a halting problem proof that has a simulating halt decider that is written in the Turing machine description language that has every single detail 100% fully specified such that a Turing machine interpreter could directly execute all of this code.

No one ever did this because:
(1) It never occurred to them that a simulating halt decider would work.
(2) without direct memory addressing it would take at least hundreds of thousands of pages of code.

The C code that I referenced is fully operational and shows every

And that's a lie.  You very carefully don't show the code or the
critical steps.  They are all hidden. 

The steps that the halt decider performs are very obviously self-evidently correct on the basis of the execution trace that is shown.
It is very obvious that when P calls H with its own machine address and H is a simulating halt decider that this specifies infinitely nested simulation.

Dishonest people can disingenuously disagree or simply fail to have the required prerequisite knowledge.

It is also true that a simulating halt decider cannot possibly have any effect on the behavior of its input while it remains in pure simulation mode. Because H remains in pure simulation mode until after it makes its halt status decision we only need to examine that it had a correct basis and sued this correct basis correctly. 14 lines of the execution trace of P shows this.

Dishonest people can disingenuously disagree or simply fail to have the required prerequisite knowledge.

We can tell if a rebuttal is dishonest or the respondent simply fails to have the required prerequisite knowledge by the fact that their "rebuttal" is a mere dogmatic assertion without any supporting reasoning (liar) or sidesteps rather than directly addressed the key points (liar or ignorant).

It's unfortunate for you that we
can still work out that your code is wrong despite your efforts to hide
it and to obscure its behaviour.

I gave you an opportunity to write C code that is incontrovertibly
"interesting" in that the specification is for a different undecidable
problem, but your response was to post output showing that your (again
hidden) code did not meet the specification.  Then you declared that my
"opinion" of what I wanted the code to do was wrong!  It's hard to see
how you expect these postings to be treated with respect.  I, for one,
am constantly biting my tongue.

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