Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Mon, 5 May 2025 22:51:12 +0100
Organization: Fix this later
Lines: 55
Message-ID: <vvbbsg$1a9js$1@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvamqc$o6v5$4@dont-email.me>
 <vvan7q$o4v0$1@dont-email.me> <ts5SP.113145$_Npd.41800@fx01.ams4>
 <vvat0g$vtiu$1@dont-email.me> <vvatf3$o4v0$3@dont-email.me>
 <vvaut0$vtiu$4@dont-email.me> <vvav6o$o4v0$4@dont-email.me>
 <vvb329$15u5b$1@dont-email.me> <vvb37g$1451r$1@dont-email.me>
 <vvb43f$15u5b$4@dont-email.me> <vvb4ok$o4v0$9@dont-email.me>
 <vvb52g$15u5b$6@dont-email.me> <vvb5ca$o4v0$10@dont-email.me>
 <bQ8SP.95226$lZjd.50247@fx05.ams4> <vvb8o6$1a9jr$2@dont-email.me>
 <QaaSP.10591$RD41.6988@fx12.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 05 May 2025 23:51:12 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="35396e3e70446f4ec1a7d7dab39281f2";
	logging-data="1386108"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18zyJr+NObv+ZPWElC4HhFC6YMxFk5XIHi14C8TLR8thQ=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:K6owhQJ7ftGM6mFreQf3/MgkP0Q=
Content-Language: en-GB
In-Reply-To: <QaaSP.10591$RD41.6988@fx12.ams4>

On 05/05/2025 22:35, Mr Flibble wrote:
> On Mon, 05 May 2025 21:57:42 +0100, Richard Heathfield wrote:
> 
>> On 05/05/2025 21:03, Mr Flibble wrote:
>>> On Mon, 05 May 2025 16:00:11 -0400, dbush wrote:
>>
>> <snip>
>>
>>>> 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?
>>>
>>> That isn't what the halting problem is about at all:
>>
>> Yes, it is.
>>
>>> the halting problem is about pathological input being undecidable but
>>> not for the reason claimed in any halting problem proof.
>>
>> By "pathological input", you mean a program the halt behaviour of which
>> is undecidable. So we are in agreement, even if you don't yet realise
>> it.
> 
> No we are not in agreement

You now acknowledge the existence of programs whose fate is 
undecidable. You give it a different name, sure, but it's the 
same thing.

> and I suspect you are being dishonest and know
> this already.

On the contrary, when you talk about 'pathological input' you use 
the term to describe uncomputable mappings between programs and 
termination statuses, so you're rather closer to the truth than 
you perhaps intended.

To put it in terms you might be able to understand better:

Turing hypothesised the existence of a universal halt decider, 
but then showed that were such a decider to exist it would be 
possible to use it to create a 'pathological input' that it 
couldn't decide, so it follows that no decider can possibly be 
universal. /At best/, it can decide for all non-pathological inputs.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within