Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Every sufficiently competent C programmer knows --- Truthmaker Maximalism Date: Fri, 14 Mar 2025 21:00:13 -0400 Organization: A noiseless patient Spider Lines: 106 Message-ID: References: <5429f6c8b8a8a79e06b4aeefe677cc54a2a636bf@i2pn2.org> <924e22fc46d629b311b16a954dd0bed980a0a094@i2pn2.org> <0c100c3673494d00bdc02acd44b2d5b930bd2212.camel@gmail.com> <6c64432865001be54d691f8ef0cc89ddc71d18b6.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 15 Mar 2025 02:00:13 +0100 (CET) Injection-Info: dont-email.me; posting-host="22e85aca536ab619b45b62b85c20fbc6"; logging-data="2526545"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Hsn4x3L3iU8NN2/KTFG/x" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:pCeHjMm6DVsV4BJ8jsIlmBrc7X8= In-Reply-To: Content-Language: en-US Bytes: 5644 On 3/14/2025 8:45 PM, olcott wrote: > On 3/14/2025 12:54 PM, dbush wrote: >> On 3/14/2025 12:33 PM, olcott wrote: >>> On 3/14/2025 11:01 AM, wij wrote: >>>> On Fri, 2025-03-14 at 10:51 -0500, olcott wrote: >>>>> On 3/14/2025 10:04 AM, wij wrote: >>>>>> On Fri, 2025-03-14 at 09:35 -0500, olcott wrote:>> >>>>>>> void DDD() >>>>>>> { >>>>>>>      HHH(DDD); >>>>>>>      return; >>>>>>> } >>>>>>> >>>>>>> DDD correctly simulated by HHH cannot possibly reach >>>>>>> its own "return" instruction in any finite number of >>>>>>> correctly simulated steps. >>>>>>> >>>>>>> That you are clueless about the semantics of something >>>>>>> as simple as a tiny C function proves that you are not >>>>>>> competent to review my work. >>>>>>> >>>>>> >>>>>> https://en.wikipedia.org/wiki/Halting_problem >>>>>> In computability theory, the halting problem is the problem of >>>>>> determining, from a description of >>>>>> an >>>>>> arbitrary computer program and an input, whether the program will >>>>>> finish running, or continue to >>>>>> run >>>>>> forever. >>>>>> >>>>>> That means: H(D)=1 if D() halts and H(D)=0 if D() does not halt. >>>>>> >>>>>> But, it seems you don't understand English, as least as my >>>>>> level, .... >>>>>> >>>>>> >>>>>> >>>>> >>>>> void DDD() >>>>> { >>>>>     HHH(DDD); >>>>>     return; >>>>> } >>>>> >>>>> The only difference between HHH and HHH1 is that they are >>>>> at different locations in memory. DDD simulated by HHH1 >>>>> has identical behavior to DDD() directly executed in main(). >>>>> >>>>> The semantics of the finite string input DDD to HHH specifies >>>>> that it will continue to call HHH(DDD) in recursive simulation. >>>>> >>>>> The semantics of the finite string input DDD to HHH1 specifies >>>>> to simulate to DDD exactly once. >>>>> >>>>> When HHH(DDD) reports on the behavior that its input finite >>>>> string specifies it can only correctly report non-halting. >>>>> >>>>> When HHH(DDD) is required to report on behavior other than >>>>> the behavior that its finite string specifies HHH is not >>>>> a decider thus not a halt decider. >>>>> >>>>> All deciders are required to compute the mapping from >>>>> their input finite string to the semantic or syntactic property >>>>> that this string specifies. Deciders return true when this >>>>> string specifies this property otherwise they return false. >>>>> >>>> >>>> Are you solving The Halting Problem or not? Yes or No. >>>> >>>> >>> >>> I have only correctly refuted the conventional halting >>> problem proof. >> >> And what exactly do you think this proof is proving?  More >> specifically, what do you think the Linz proof is proving? > > All of the proofs merely show that there cannot > possibly exist any halt decider that returns a > value corresponding to the behavior of any input > that is actually able to do the opposite of whatever > value is returned. > Not exactly. What they prove is that no H exists that satisfies these requirements: 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: (,Y) maps to 1 if and only if X(Y) halts when executed directly (,Y) maps to 0 if and only if X(Y) does not halt when executed directly And they do so via proof-by-contradiction: First they assume that such an H exists. That is the ONLY assumption, so all possible implementations are included, including simulation. Then they build a D such that H doesn't meet the above requirements for D. This is a contradiction, so the assumption that such an H exists is proven false.