Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Every sufficiently competent C programmer knows --- Semantic
 Property reiterated
Date: Thu, 13 Mar 2025 12:51:50 -0500
Organization: A noiseless patient Spider
Lines: 178
Message-ID: <vqv5vm$3kabb$1@dont-email.me>
References: <vqntaq$1jut5$1@dont-email.me> <vqp388$1tvqa$1@dont-email.me>
 <vqpdv9$202b2$2@dont-email.me> <vqperb$20c9k$2@dont-email.me>
 <E6mcnWv3nMa66036nZ2dnZfqnPWdnZ2d@brightview.co.uk>
 <vqpv2u$23vhr$1@dont-email.me>
 <Ny-dnRlMHcVpA036nZ2dnZfqnPqdnZ2d@brightview.co.uk>
 <878qp9gckd.fsf@bsb.me.uk> <vquvvs$3dmpj$2@dont-email.me>
 <vqv061$3clv8$3@dont-email.me> <vqv1ne$3dmpj$3@dont-email.me>
 <vqv216$3clv8$4@dont-email.me> <vqv3hg$3dmpj$4@dont-email.me>
 <vqv3t3$3clv8$5@dont-email.me> <vqv5dl$3dmpj$5@dont-email.me>
 <vqv5gh$3j2v7$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 13 Mar 2025 18:51:52 +0100 (CET)
Injection-Info: dont-email.me; posting-host="29518dbc565baf39934ae16a91b6709b";
	logging-data="3811691"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18gANacQk14wZ+sUsKeqATE"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:lRKLoJFLdA7bmwior5gxEEA97xY=
X-Antivirus: Norton (VPS 250313-4, 3/13/2025), Outbound message
In-Reply-To: <vqv5gh$3j2v7$1@dont-email.me>
Content-Language: en-US
X-Antivirus-Status: Clean
Bytes: 8516

On 3/13/2025 12:43 PM, dbush wrote:
> On 3/13/2025 1:42 PM, olcott wrote:
>> On 3/13/2025 12:16 PM, dbush wrote:
>>> On 3/13/2025 1:10 PM, olcott wrote:
>>>> On 3/13/2025 11:44 AM, dbush wrote:
>>>>> On 3/13/2025 12:39 PM, olcott wrote:
>>>>>> On 3/13/2025 11:12 AM, dbush wrote:
>>>>>>> On 3/13/2025 12:09 PM, olcott wrote:
>>>>>>>> On 3/13/2025 10:44 AM, Ben Bacarisse wrote:
>>>>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>>>>>>>
>>>>>>>>>> On 11/03/2025 18:23, Richard Heathfield wrote:
>>>>>>>>>>> On 11/03/2025 17:42, Mike Terry wrote:
>>>>>>>>>>>> Finally, if you really want to see the actual HHH code, its 
>>>>>>>>>>>> in the
>>>>>>>>>>>> halt7.c file (along with DDD) that PO provides links to from 
>>>>>>>>>>>> time to
>>>>>>>>>>>> time.  However it's not very illuminating due to bugs/design
>>>>>>>>>>>> errors/misunderstandings which only serve to obfuscate PO's 
>>>>>>>>>>>> errors in
>>>>>>>>>>>> thinking.
>>>>>>>>>>> [I've now seen the code. Oh deary deary me.]
>>>>>>>>>>
>>>>>>>>>> :)
>>>>>>>>>>
>>>>>>>>>>> Thank you for a spirited attempt to be cogent - or at least 
>>>>>>>>>>> as cogent as
>>>>>>>>>>> it is possible to be in the circumstances!
>>>>>>>>>>> I think PO's first step must be to demonstrate that HHH() 
>>>>>>>>>>> correctly
>>>>>>>>>>> diagnoses some easy functions, such as these:
>>>>>>>>>>
>>>>>>>>>> Not really necessary - PO is not trying or claiming to have a 
>>>>>>>>>> (full)
>>>>>>>>>> halt decider.
>>>>>>>>>>
>>>>>>>>>> Originally his claim was that he had a program which worked 
>>>>>>>>>> for the
>>>>>>>>>> counter-example TM used in the common (e.g. Linz book) proof.
>>>>>>>>>
>>>>>>>>> That, of course, depends on the way the wind's blowing.  For 
>>>>>>>>> example in
>>>>>>>>> 2020:
>>>>>>>>>
>>>>>>>>>    "The non-halting decider that I defined accepts any and all
>>>>>>>>>    non-halting inputs and rejects any and all halting inputs."
>>>>>>>>>
>>>>>>>>> But then he retreated to the "once case" argument again until:
>>>>>>>>>
>>>>>>>>> Me: "Recent posts have said that you really do claim to have a 
>>>>>>>>> halting
>>>>>>>>>      decider.  Have you extended your claim or was that a
>>>>>>>>>      misunderstanding?"
>>>>>>>>>
>>>>>>>>> PO: "I really do have a halting decider."
>>>>>>>>>
>>>>>>>>>> ... Such a
>>>>>>>>>> program is impossible, as Linz and others prove, so having a 
>>>>>>>>>> program H and
>>>>>>>>>> its corresponding "counter-example" D, such that H correctly 
>>>>>>>>>> decides D,
>>>>>>>>>> would certainly show that the Linz proof is wrong.  His claim 
>>>>>>>>>> was always
>>>>>>>>>> that he had "refuted the HP proof", or sometimes that he had 
>>>>>>>>>> refuted the HP
>>>>>>>>>> theorem itself although he's been told dozens of times that 
>>>>>>>>>> there are many
>>>>>>>>>> alternative proofs for the result.
>>>>>>>>>
>>>>>>>>> Way back in 2004 he was sure that:
>>>>>>>>>
>>>>>>>>>    "I have correctly refuted each and every mechanism by which the
>>>>>>>>>    [halting theorem] has been proven to be true. I have not 
>>>>>>>>> shown that
>>>>>>>>>    solving the Halting Problem is possible, merely refuted 
>>>>>>>>> every proof
>>>>>>>>>    that it is impossible."
>>>>>>>>>
>>>>>>>>> I expect a publication anytime.  20 years is just about enough 
>>>>>>>>> to get
>>>>>>>>> all the details right.
>>>>>>>>>
>>>>>>>>>> [As it turned out, PO's D(D) halted when run under his x86utm 
>>>>>>>>>> environment,
>>>>>>>>>> while H(D,D) which is required to return the halting status of 
>>>>>>>>>> computation
>>>>>>>>>> D(D) returned 0 (=non-halting).  That is exactly what the Linz 
>>>>>>>>>> proofs
>>>>>>>>>> claim!]
>>>>>>>>>
>>>>>>>>> We must always remember that PO has re-defined what it means 
>>>>>>>>> for the
>>>>>>>>> answer to be correct:
>>>>>>>>>
>>>>>>>>> Me: "Here's the key question: do you still assert that H(P,P) 
>>>>>>>>> == false
>>>>>>>>>      is the "correct" answer even though P(P) halts?"
>>>>>>>>>
>>>>>>>>> PO: "Yes that is the correct answer even though P(P) halts."
>>>>>>>>>
>>>>>>>>> He's been quite clear about it:
>>>>>>>>>
>>>>>>>>>    "When we make the single change that I suggest the halting 
>>>>>>>>> problem
>>>>>>>>>    ceases to be impossible to solve because this revised 
>>>>>>>>> question is not
>>>>>>>>>    subject to pathological self-reference."
>>>>>>>>>
>>>>>>>>>    "This transforms an undecidable problem into a decidable 
>>>>>>>>> problem."
>>>>>>>>>
>>>>>>>>> I hope you forgive me just chipping in with stuff you know 
>>>>>>>>> perfectly
>>>>>>>>> well, but I thought I'd just give some background as Richard is 
>>>>>>>>> a new
>>>>>>>>> participant and my comments fit better with your post than his.
>>>>>>>>>
>>>>>>>>
>>>>>>>> typedef void (*ptr)();
>>>>>>>> int HHH(ptr P);
>>>>>>>>
>>>>>>>> int DD()
>>>>>>>> {
>>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>>    if (Halt_Status)
>>>>>>>>      HERE: goto HERE;
>>>>>>>>    return Halt_Status;
>>>>>>>> }
>>>>>>>>
>>>>>>>> When N steps of DD are correctly emulated by
>>>>>>>> any HHH then each DD cannot possibly reach
>>>>>>>> its own final state and terminate normally.
>>>>>>>>
>>>>>>>> We we recall Rice's Theorem we know that the
>>>>>>>> issue to be decided must be based on the semantic
>>>>>>>> property that the input finite string specifies.
>>>>>>>>
>>>>>>>
>>>>>>> And the semantic property we care about, which you implicitly 
>>>>>>> agreed is one, is the property of the directly executed DD.
>>>>>>
>>>>>> No that is stupidly wrong 
>>>>>
>>>>> Not when it's the direct execution that we care about.
>>>>>
>>>>
>>>> That stupidly ignores that Rice's Theorem requires
>>>> that a decider makes its decision on the basis of
>>>> a semantic property encoded as a finite string.
>>>>
>>>
>>> It does not, as the semantic property we're interested in that of the 
>>> direct execution.
>>
>> THAT IS NOT THE SEMANTIC PROPERTY SPECIFIED
>> BY THE INPUT FINITE STRING KNUCKLEHEAD
>>
> 
> It is by the stipulated definition of a solution to the halting problem:
> 
> 
> Given any algorithm (i.e. a fixed immutable sequence of instructions) X 
> described as <X> with input Y:
> 
> A solution to the halting problem is an algorithm H that computes the 
> following mapping:
> 
========== REMAINDER OF ARTICLE TRUNCATED ==========