Deutsch   English   Français   Italiano  
<vva94c$d8cv$1@dont-email.me>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
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: <vva94c$d8cv$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <87cyd5182l.fsf@nosuchdomain.example.com> <vu6lnf$39fls$2@dont-email.me>
 <vugddv$b21g$2@dont-email.me> <vui4uf$20dpc$1@dont-email.me>
 <vuivtb$2lf64$3@dont-email.me> <vungtl$2v2kr$1@dont-email.me>
 <vuoaac$3jn5n$5@dont-email.me> <vuq81v$1hjka$1@dont-email.me>
 <vutefq$gmbi$3@dont-email.me> <vv22hs$puqs$1@dont-email.me>
 <vv89ll$2erlq$4@dont-email.me> <vv8en2$2kjgk$3@dont-email.me>
 <vv8ot8$2ub3p$1@dont-email.me> <vv8pqu$2ut5q$1@dont-email.me>
 <5YRRP.109778$_Npd.21893@fx01.ams4> <vv8qkt$2uhjq$2@dont-email.me>
 <87a57ramha.fsf@bsb.me.uk> <vv94qm$383jd$2@dont-email.me>
 <vv99l9$3h92p$2@dont-email.me> <vv9a6f$3hjhu$2@dont-email.me>
 <vv9alm$3h92p$6@dont-email.me> <vv9bli$3ifj7$2@dont-email.me>
 <vv9bvi$3h92p$8@dont-email.me> <vv9cab$3ifj7$4@dont-email.me>
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: <vv9cab$3ifj7$4@dont-email.me>

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 <rjh@cpax.org.uk> 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 <is> 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.