Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Two computer science professors agree with Flibble Date: Mon, 5 May 2025 07:58:04 -0400 Organization: A noiseless patient Spider Lines: 113 Message-ID: References: <87cyd5182l.fsf@nosuchdomain.example.com> <5YRRP.109778$_Npd.21893@fx01.ams4> <87a57ramha.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 05 May 2025 13:58:05 +0200 (CEST) Injection-Info: dont-email.me; posting-host="18d110b57402f35c65b5688042d33321"; logging-data="434591"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+hyq+Na1v4Qz4iGhADbVt7" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:9gcao1+4y3+Vn6Ux6MH1cl44Zkc= Content-Language: en-US In-Reply-To: On 5/4/2025 11:46 PM, olcott wrote: > On 5/4/2025 10:40 PM, dbush wrote: >> On 5/4/2025 11:35 PM, olcott wrote: >>> On 5/4/2025 10:18 PM, dbush wrote: >>>> On 5/4/2025 11:10 PM, olcott wrote: >>>>> On 5/4/2025 10:00 PM, dbush wrote: >>>>>> On 5/4/2025 9:38 PM, olcott wrote: >>>>>>> On 5/4/2025 8:13 PM, Ben Bacarisse wrote: >>>>>>>> Richard Heathfield writes: >>>>>>>> >>>>>>>>> On 04/05/2025 23:34, Mr Flibble wrote: >>>>>>>>>> The function is neither computable nor incomputable because >>>>>>>>>> there is no >>>>>>>>>> function at all, just a category error. >>>>>>>>> >>>>>>>>> It's a point of view. >>>>>>>> >>>>>>>> It's a point of view only in the sense that there is no opinion >>>>>>>> so daft >>>>>>>> that it's not someone's point of view.  The technical-sounding >>>>>>>> waffle >>>>>>>> about it being a "category error" is simply addressed by asking >>>>>>>> where >>>>>>>> the supposed category error is in other perfectly straightforward >>>>>>>> undecidable problems.  For example, whether or not a context-free >>>>>>>> grammar is ambiguous or not, or the very simple to pose Post >>>>>>>> correspondence problem. >>>>>>>> >>>>>>> >>>>>>> Flibble IS CORRECT when the halting problem is defined >>>>>>> to be isomorphic (AKA analogous) to the Liar Paradox: >>>>>>> "This sentence is not true". >>>>>>> >>>>>>> When the Halting Problem is defined as an input that >>>>>>> does the opposite of whatever its decider reports >>>>>>> then both Boolean return values are incorrect >>>>>> >>>>>> False.  One value is correct and one is incorrect. >>>>>> >>>>> >>>>> Both Boolean RETURN VALUES FROM H *ARE* INCORRECT, >>>> Category error.  Algorithms do one thing and one thing only.  And >>>> the algorithm that is the fixed code of the function H and >>>> everything it calls gives the wrong answer, and the opposing answer >>>> is the right answer. >>> >>> Look at the paper from the PhD computer science >>> professor. >>> >>> Halting misconceived? >>> Bill Stoddart >>> August 25, 2017 >>> >>> *the halting function, as described, cannot be implemented*, >>> *because its specication is inconsistent*... >>> >>> *Context* >>> That halting is not in general computable has been >>> proved in many text books and taught on many computer >>> science courses, and is supposed to illustrate the >>> limits of computation. However, there is a dissenting >>> view that these proofs are misconceived. >>> >>> In this paper we look at what is perhaps the simplest >>> such proof, based on a program that interrogates its own >>> halting behaviour and then decides to thwart it. This >>> leads to a contradiction that is generally held to show >>> that a halting function cannot be implemented. >>> >>> The dissenting view agrees with the conclusion that >>> *the halting function, as described, cannot be implemented*, >>> but suggests that this is *because its specication is inconsistent* >>> https://www.complang.tuwien.ac.at/anton/euroforth/ef17/papers/ >>> stoddart.pdf >>> >> >> The only way for the specification to be inconsistent if there was an >> algorithm, i.e. a fixed immutable sequence of instructions, that >> neither halts nor not halts when executed directly. >> > > OK now we get down to the nuances. > > The way that meaning in language actually works > as understood by linguistics: The context of > who as asked a question an aspect of the > full meaning of this question. > > When we assume that D is actually able to do the > opposite of whatever value that H returns then both > RETURN VALUES of {True, False} ARE THE WRONG ANSWER. Category error. "D" and "H" refer to algorithms, i.e. a fixed immutable sequence of instructions, as that is what the halting problem is about. They do NOT refer to C functions with a specific name/address that can contain arbitrary code. The halting problem is about the instructions themselves, not about where instructions reside. Suppose function H is implemented such that function call H(D) returns 0. We will call these algorithms D0 and H0. In this case, algorithm D0 halts so 1 is the correct answer, and algorithm H0(D0)==0 is wrong. Suppose now function H is implemented such that function call H(D) returns 1. We will call these algorithms D1 and H1. In this case, algorithm D1 does not halt so 1 is the correct answer, and algorithm H1(D1)==1 is wrong. For algorithm D1, algorithm H1 gets the wrong answer. For algorithm D0, algorithm H0 gets the wrong answer.