Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"You must have an IQ of at least half a million." -- Popeye


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

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

<__WdneskYvGLiLj8nZ2dnUU7-U3NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=7285&group=comp.ai.philosophy#7285

 copy link   Newsgroups: comp.theory comp.ai.philosophy comp.software-eng sci.math.symbolic
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
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,comp.ai.philosophy,comp.software-eng,sci.math.symbolic
References: <3YOdnecvDsA5Q4r8nZ2dnUU7-TXNnZ2d@giganews.com> <8735r1k0p0.fsf@bsb.me.uk> <TIidnUnAVPdb9L_8nZ2dnUU7-RPNnZ2d@giganews.com> <87r1elihh9.fsf@bsb.me.uk> <c9ydnS0MB5tqG7_8nZ2dnUU7-R_NnZ2d@giganews.com> <87czq5i9u0.fsf@bsb.me.uk> <srednU_7RdGxPr_8nZ2dnUU7-eHNnZ2d@giganews.com> <87y28tgt3w.fsf@bsb.me.uk> <xamdnei4F5CzM7_8nZ2dnUU7-KPNnZ2d@giganews.com> <87h7fhgpjm.fsf@bsb.me.uk> <cradndCzBKW6Ir_8nZ2dnUU7-XWdnZ2d@giganews.com> <87o89pf5zi.fsf@bsb.me.uk> <R_WdnWjO0dnDlb78nZ2dnUU7-bvNnZ2d@giganews.com> <87k0kce1yk.fsf@bsb.me.uk> <edCdnTY_IvB2N778nZ2dnUU7-WvNnZ2d@giganews.com> <87bl5oc62l.fsf@bsb.me.uk> <INadnSiJbfTFYb78nZ2dnUU7-LPNnZ2d@giganews.com> <87tujfbv4y.fsf@bsb.me.uk> <5bidne_8HrBuqbn8nZ2dnUU7-dfNnZ2d@giganews.com> <87lf4rbksk.fsf@bsb.me.uk> <Mf2dnamm9d978bn8nZ2dnUU7-cHNnZ2d@giganews.com> <87fsuzaq8t.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (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: <87fsuzaq8t.fsf@bsb.me.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <__WdneskYvGLiLj8nZ2dnUU7-U3NnZ2d@giganews.com>
Lines: 465
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-trY0X0/vxGAhGOZ3PgvnAs7jClnoK6dAGBTkeIikazdxAyr9XYcgNRz0OWOTgG9qvXLav1uzELeYQk8!YBgUFHYjGft1KBxb9e2Y3zweIIvq7am/BnR328Siz/oT6pxnUycW2MZt2wMflme3+1gRN6FubSqU!Q4E=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
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
 by: olcott - Tue, 24 Aug 2021 15:49 UTC

On 8/24/2021 9:09 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 8/23/2021 10:09 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 8/23/2021 6:26 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 8/23/2021 2:30 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> 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
>>>>> error.
>>>>>
>>>>>> 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 ⟨Ĵ⟩
>>> halts?
>>
>> 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,
> sure.
>
>>>> Ĵ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 <NoOne@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.

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.

> <aside>
> 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.
> </aside>
>

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 ⟨Ĥ⟩ ⟨Ĥ⟩)
>>> and
>>> Ĥ.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
>> step.
>
> 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

SubjectRepliesAuthor
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

29olcott
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor