Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Mon, 5 May 2025 16:00:11 -0400 Organization: A noiseless patient Spider Lines: 46 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 05 May 2025 22:00:11 +0200 (CEST) Injection-Info: dont-email.me; posting-host="18d110b57402f35c65b5688042d33321"; logging-data="791520"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/U/rZSwmKW/OpWfvI0I7Eo" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ap+iuWniepG01HHfa6MBApvQV2w= Content-Language: en-US In-Reply-To: On 5/5/2025 3:54 PM, olcott wrote: > On 5/5/2025 2:49 PM, dbush wrote: >> On 5/5/2025 3:38 PM, olcott wrote: >>> On 5/5/2025 2:23 PM, Richard Heathfield wrote: >>>> On 05/05/2025 20:20, olcott wrote: >>>>> Is "halts" the correct answer for H to return?  NO >>>>> Is "does not halt" the correct answer for H to return?  NO >>>>> Both Boolean return values are the wrong answer >>>> >>>> Or to put it another way, the answer is undecidable, QED. >>>> >>>> See? You got there in the end. >>>> >>> >>> Is this sentence true or false: "What time is it?" >>> is also "undecidable" because it is not a proposition >>> having a truth value. >>> >>> Is this sentence true or false: "This sentence is untrue." >>> is also "undecidable" because it is not a semantically sound >>> proposition having a truth value. >>> >>> Can Carol correctly answer “no” to this (yes/no) question? >>> >>> Both Yes and No are the wrong answer proving that >>> the question is incorrect when the context of who >>> is asked is understood to be a linguistically required >>> aspect of the full meaning of the question. >> >> And "does algorthm X with input Y halt when executed directly" has a >> single well defined answer. >> > > That is not even the actual question. > In other words, you don't understand what the halting problem is about, because that is EXACTLY the question. I want to know if any arbitrary algorithm X with input Y will halt when executed directly. It would be *very* useful to me if I had an algorithm H that could tell me that in *all* possible cases. If so, I could solve the Goldbach conjecture, among many other unsolved problems. Does an algorithm H exist that can tell me that or not?