Re: Halting Problem: What Constitutes Pathological Input

On 5/5/2025 3:27 PM, Alan Mackenzie wrote:

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.
 

None-the-less The Linz proof does require a pathological
relationship between the input and the embedded termination
analyzer.
When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
(a) Ĥ copies its input ⟨Ĥ⟩
(b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩
(e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
(f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
(g) goto (d) with one more level of simulation

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

 

--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer