Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory,sci.logic
Subject: Re: D correctly simulated by pure function H cannot possibly reach
 its, own line 06 --- Linz
Date: Sun, 26 May 2024 16:20:56 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v305j9$26571$1@i2pn2.org>
References: <v2nsvh$1rd65$2@dont-email.me> <v2tdre$22aq1$7@i2pn2.org>
 <v2tfms$30u1r$3@dont-email.me> <v2tgv2$22aq0$2@i2pn2.org>
 <v2th6a$319s1$1@dont-email.me> <v2tjpr$22aq1$9@i2pn2.org>
 <v2tk9i$31qgp$1@dont-email.me> <v2tkit$22aq0$6@i2pn2.org>
 <v2tl8b$31uo4$2@dont-email.me> <v2tm5d$22aq0$7@i2pn2.org>
 <v2tnr1$32e7p$1@dont-email.me> <v2tp5n$22aq0$9@i2pn2.org>
 <v2tpdg$32me8$2@dont-email.me> <v2tptp$22aq1$13@i2pn2.org>
 <v2tq50$32r0d$2@dont-email.me> <v2tqh7$22aq1$15@i2pn2.org>
 <v2tr68$32uto$1@dont-email.me> <v2trch$23vgp$1@i2pn2.org>
 <v2trts$331vq$1@dont-email.me> <v2tsub$23vgp$2@i2pn2.org>
 <v2u0o5$33mgp$1@dont-email.me> <v2u2uf$23vgp$4@i2pn2.org>
 <v2u5a0$349br$2@dont-email.me> <v2u6if$23vgo$3@i2pn2.org>
 <v2u7fj$38fjo$1@dont-email.me> <v2v79q$25ell$2@i2pn2.org>
 <v2vg1g$3e8pb$4@dont-email.me> <v2vo5h$26570$3@i2pn2.org>
 <v2vpt6$3g0m3$3@dont-email.me> <v2vqou$26570$5@i2pn2.org>
 <v2vrcl$3gakv$1@dont-email.me> <v2vslp$26570$6@i2pn2.org>
 <v301m6$3hcgb$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 26 May 2024 20:20:57 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2299105"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <v301m6$3hcgb$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 8706
Lines: 144

On 5/26/24 3:14 PM, olcott wrote:
> On 5/26/2024 12:48 PM, Richard Damon wrote:
>> On 5/26/24 1:26 PM, olcott wrote:
>>> On 5/26/2024 12:16 PM, Richard Damon wrote:
>>>> On 5/26/24 1:01 PM, olcott wrote:
>>>>> On 5/26/2024 11:31 AM, Richard Damon wrote:
>>>>>> On 5/26/24 10:13 AM, olcott wrote:
>>>>>>> On 5/26/2024 6:43 AM, Richard Damon wrote:
>>>>>>>
>>>>>>> typedef int (*ptr)();  // ptr is pointer to int function in C
>>>>>>> 00       int H(ptr p, ptr i);
>>>>>>> 01       int D(ptr p)
>>>>>>> 02       {
>>>>>>> 03         int Halt_Status = H(p, p);
>>>>>>> 04         if (Halt_Status)
>>>>>>> 05           HERE: goto HERE;
>>>>>>> 06         return Halt_Status;
>>>>>>> 07       }
>>>>>>> 08
>>>>>>> 09       int main()
>>>>>>> 10       {
>>>>>>> 11         H(D,D);
>>>>>>> 12         return 0;
>>>>>>> 13       }
>>>>>>>
>>>>>>>
>>>>>>>> Because, as I have said, the answer and reasoning changes 
>>>>>>>> depending on what you acknowledged are the implications of your 
>>>>>>>> stipulations. For instance, if your actual understanding of 
>>>>>>>> being a "Pure Function" is that the program is the equivalent of 
>>>>>>>> a Turing Machine, then we need to add a strictness to the 
>>>>>>>> definition that isn't normally used for just "Pure Functions", 
>>>>>>>> like accessing value of registers like the program counter or 
>>>>>>>> stack pointer might not be allowed in some cases. (which breaks 
>>>>>>>> you H).
>>>>>>>>
>>>>>>>
>>>>>>> Since we can see (and you already agreed) that D correctly simulated
>>>>>>> by pure simulator H remains stuck in infinite recursive 
>>>>>>> simulation then
>>>>>>> we also know that D never reaches its own line 06 and halts in less
>>>>>>> than an infinite number of correctly simulated steps.
>>>>>>
>>>>>> But it depends on what H actually does, which you refuse to agree to.
>>>>>>
>>>>>
>>>>> When I specify that D is correctly simulated by pure function H, that
>>>>> means that H is a pure simulator that stops simulating D after some
>>>>> finite number of correctly simulated steps. There is absolutely 
>>>>> nothing
>>>>> else that needs to be known about H besides this.
>>>>>
>>>>
>>>> And, do you accept that this exact description means that H is NOT 
>>>> the computational equivalent of a Turing Machine, and that this 
>>>> simulation doesn't prove that its input is not a non-halting program?
>>>>
>>>
>>> In other words you are saying that it is 100% totally impossible to
>>> adapt an actual UTM so that it stops simulating after a finite number of
>>> steps.
>>
>> Yep, at least and have it still be a UTM.
>>
> 
> When Ĥ is applied to ⟨Ĥ⟩
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> 
> When we see that ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded_H in an
> infinite number of steps cannot possibly reach its own simulated
> final state of ⟨Ĥ.qn⟩ and halt then we correctly deduce that the
> same thing applies when simulating halt decider embedded_H correctly
> simulates less than an infinite number of steps of ⟨Ĥ⟩ ⟨Ĥ⟩.
> 

Nope.

Since we are talking about Turing Machines, your stipulated POOP 
definitions go away, and we are back to the actual definitions of 
Computaiton theory. We are also, due to the context of the problem, and 
the use of the term "halt decider" in the context of the halting problem.

THe ONLY machine we have described here is H^, and the sub-machine 
embeded_H that it uses, which needs to be an exact copy of the claimed 
halt decider H. Which have to be specific machines fully specified, as 
that is all you can apply to an input with this notation.

Yes, you might be able to define that embedded_H DOES abort its 
simulation after some number of steps, but since this is context of a 
Halting Problem, the definition of "Correct" here is that embedded_H is 
only correct to abort its simulation and transition to Qn is if the 
machine its input describes will never halt, which IS H^ applied to H^.

The talk of a DIFFERENT H^ based on a DIFFERENT embedded_H is not 
relevent, no more than using facts about a 10 story office building when 
talking about a cat.

Since if embedded_H transitions to qn, that also means that H^ ended up 
in Qn and halted, embedded_H waa NOT correct in determining that its 
input was non-halting.

Note, the problem is that the H^ built on an embedded_H that simulates 
an infinite number of steps is NOT the same H^ as the one built on an 
embedded_H that aborts its simulation in a finite number of steps.

This is NOT your perverted infinite set built of a templete, but an 
example of a SPECIFIC H^, built on a specific embedded_H, applied to a 
specific input (H^).


If you want to try to talk about embedded_H determining that it can't 
simulate to a final state, that isn't a proper question, "can't" doesn't 
apply, since it was defined to abort before it got there. This has been 
your problem, you are trying to argue about an attribute that doesn't 
exist.

This is where the non-simulator shows its "just as valid" face, 
embedded_H doesn't reach the end, because it aborted its simulation too 
soon. If you process that exact same input by a UTM (and thus, H^ still 
uses the original embedded_H) we see that the UTM DOES simulate to the 
end, and thus it isn't that embedded_H "Can't" simulate THIS INPUT to a 
final state, but that it just doesn't.

The problem for you is that the input is what the input is and that will 
ALWAYS have the algorithm of the final H you decide on, even when you 
hypotosis other variations of the decider to check the answer, so some 
of them WILL simulate it to the final state, so you "Can't" claim is broken.

H^ doesn't change as you try these other deciders, because it its 
allowed to, it is a FIXED input, that can't some how refer to who is 
trying to decide it.

This shows the error of your perverse template generating an infinte set 
of H/D pairs. That just isn't the problem that was being looked at. In 
fact, it asks a question that can't be formed by an actual input in 
computation theory with Turing Machines, as there is no way to reference 
the decider on the input.

This is similer to, but stronger than, your claim that H can't be asked 
to decider about the machine that is using it. That is true in the sense 
that the input can't refer to that containing program just as an 
abstract concept of a containing program, but it CAN descirbe a specific 
containing program in the input. That option doesn't exist for defining 
H^/D.