Path: ...!weretis.net!feeder8.news.weretis.net!news.szaf.org!news.karotte.org!news.space.net!news.muc.de!.POSTED.news.muc.de!not-for-mail
From: Alan Mackenzie <acm@muc.de>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Mon, 5 May 2025 20:27:07 -0000 (UTC)
Organization: muc.de e.V.
Message-ID: <vvb6ur$1fho$6@news.muc.de>
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>
Injection-Date: Mon, 5 May 2025 20:27:07 -0000 (UTC)
Injection-Info: news.muc.de; posting-host="news.muc.de:2001:608:1000::2";
	logging-data="48696"; mail-complaints-to="news-admin@muc.de"
User-Agent: tin/2.6.4-20241224 ("Helmsdale") (FreeBSD/14.2-RELEASE-p1 (amd64))
Bytes: 2683
Lines: 38

Mr Flibble <flibble@red-dwarf.jmc.corp> wrote:
> On Mon, 05 May 2025 16:00:11 -0400, dbush wrote:

>> On 5/5/2025 3:54 PM, olcott wrote:

[ .... ]

>>> 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?

> That isn't what the halting problem is about at all: the halting problem 
> is about pathological input being undecidable but not for the reason 
> claimed in any halting problem proof.

Linz's proof (according to Ben Bacarisse last Thursday) is a trivial
corollary of the fact, proved in chapter 11 of his book, that not all
recursively enumerable languages are recursive.  There is no mention of
"pathological input" anywhere in that proof.

You would do better to avoid spouting off about "any halting problem
proof".  There are several of these.  It wouldn't do you any harm at all
to find out what "recursively enumerable language" means.  It would put
you in a much better position to carry on the arguments in this newsgroup
intelligently.

> /Flibble

-- 
Alan Mackenzie (Nuremberg, Germany).