Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Halting Problem is wrong two different ways Date: Fri, 7 Jun 2024 09:22:50 +0300 Organization: - Lines: 107 Message-ID: References: <87h6eamkgf.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 07 Jun 2024 08:22:50 +0200 (CEST) Injection-Info: dont-email.me; posting-host="6ffc97c8aed538b65f79c8ced6ee8603"; logging-data="2070315"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19WHGiPUKCHwUSlmHf5CQM8" User-Agent: Unison/2.2 Cancel-Lock: sha1:oZsgAhx3LpbptiunF7DhCUPLQF4= Bytes: 5810 On 2024-06-06 15:18:21 +0000, olcott said: > On 6/6/2024 10:09 AM, Mikko wrote: >> On 2024-06-06 13:48:29 +0000, olcott said: >> >>> On 6/6/2024 4:34 AM, Mikko wrote: >>>> On 2024-06-05 13:18:24 +0000, olcott said: >>>> >>>>> On 6/5/2024 2:13 AM, Mikko wrote: >>>>>> On 2024-06-04 17:40:47 +0000, olcott said: >>>>>> >>>>>>> On 6/4/2024 3:28 AM, Mikko wrote: >>>>>>>> On 2024-06-03 18:14:39 +0000, olcott said: >>>>>>>> >>>>>>>>> On 6/3/2024 9:27 AM, Mikko wrote: >>>>>>>>>> On 2024-06-03 12:20:01 +0000, olcott said: >>>>>>>>>> >>>>>>>>>>> On 6/3/2024 4:42 AM, Ben Bacarisse wrote: >>>>>>>>>>>> Mike Terry writes: >>>>>>>>>>>> >>>>>>>>>>>>> PO's D(D) halts, as illustrated in various traces that have been posted here. >>>>>>>>>>>>> PO's H(D,D) returns 0 : [NOT halting] also as illustrated in various traces. >>>>>>>>>>>>> i.e. exactly as the Linz proof claims.  PO has acknowledged both these >>>>>>>>>>>>> results.  Same for the HH/DD variants. >>>>>>>>>>>>> >>>>>>>>>>>>> You might imagine that's the end of the matter - PO failed.  :) >>>>>>>>>>>>> >>>>>>>>>>>>> That's right, but PO just carries on anyway! >>>>>>>>>>>> >>>>>>>>>>>> He has quite explicitly stated that false (0) is the correct result for >>>>>>>>>>>> H(D,D) "even though D(D) halts".  I am mystified why anyone continues to >>>>>>>>>>>> discuss the matter until he equally explicitly repudiates that claim. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Deciders only compute the mapping *from their inputs* to their own >>>>>>>>>>> accept or reject state. >>>>>>>>>> >>>>>>>>>> That does not restrict what a problem statement can specify. >>>>>>>>>> If the computed mapping differs from the specified one the >>>>>>>>>> decider does not solve the problem. >>>>>>>>> >>>>>>>>> int sum(int x, int y) { return x + y; } >>>>>>>>> sum(2,3) cannot return the sum of 5 + 6. >>>>>>>> >>>>>>>> That does not restrict what a problem statement can specify. >>>>>>>> If the mapping computed by sum differs from the specified one >>>>>>>> the program sum does not solve the problem. >>>>>>>> >>>>>>> >>>>>>> On 6/3/2024 9:53 PM, Richard Damon wrote: >>>>>>>  > Because you keep on mentioning about DD Halting, >>>>>>>  > which IS about the direct execution of DD >>>>>>> >>>>>>> Only when one contradicts the definition of a decider that must >>>>>>> compute the mapping FROM ITS INPUTS BASED ON THE ACTUAL BEHAVIOR >>>>>>> OF THESE INPUTS (as measured by DD correctly simulated by HH). >>>>>>> >>>>>>> When we go ahead and contradict this definition then the >>>>>>> *HALTING PROBLEM IS STILL WRONG IN A DIFFERENT WAY* >>>>>>> >>>>>>> When D is defined to do the opposite of whatever yes/no >>>>>>> an answer that H provides then the counter-example input >>>>>>> is precisely isomorphic to the question: >>>>>>> Is this sentence: "This sentence is not true." true or false? >>>>>>> Thus that question and the HP question are both incorrect >>>>>>> because both yes and no are the wrong answer. >>>>>>> >>>>>>> The theory of computation may be ignorant of the details of >>>>>>> how the context of who is asked a question changes the meaning >>>>>>> of this question, none-the-less this cannot be ignored. >>>>>>> It is and remains incorrect for the theory of computation >>>>>>> to ignore this. >>>>>> >>>>>> Nice to see that you don't disagree with my observation that >>>>>> your statement >>>>>> >>>>>>>>>>> Deciders only compute the mapping *from their inputs* to their own >>>>>>>>>>> accept or reject state. >>>>>> >>>>>> does not restrict what a problem statement can specify. >>>>>> >>>>> >>>>> Sure it does. >>>>> int sum(int x, int y) { return x + y; } >>>>> sum(3,4) cannot correctly return the sum of 5 + 6. >>>> >>>> That does not restrict what the problem statement can specify. >>>> >>> >>> When someone tries to prove that sum(3,4) is incorrect on the >>> basis that it cannot correctly provide the sum of 5 + 6, then >>> they are wrong. >> >> Meybe, maybe not. That depends on the requirements. In any case, >> that does not restrict what the problem statement can specify. >> > > *Here is that problem statement* > Prove that sum(3,4) is incorrect on the basis that > sum(3,4) cannot and does not provide the sum of 5 + 6. That problem statement does not restrict what another problem statement may specify. -- Mikko