Re: Halting Problem: What Constitutes Pathological Input

Op 05.mei.2025 om 23:06 schreef olcott:

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

And G is executed a finite number of times, because embedded H has code for an conditional abort.