Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott 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: References: <878qp9gckd.fsf@bsb.me.uk> 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: 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 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 with input Y: > > A solution to the halting problem is an algorithm H that computes the > following mapping: > ========== REMAINDER OF ARTICLE TRUNCATED ==========