Re: HHH(DD) --- COMPUTE ACTUAL MAPPING FROM INPUT TO OUTPUT

On 16/04/2025 20:42, Mr Flibble wrote:

On Wed, 16 Apr 2025 20:03:52 +0100, Richard Heathfield wrote:
 

On 16/04/2025 19:09, Alan Mackenzie wrote:

Mr Flibble <flibble@red-dwarf.jmc.corp> wrote:

On Wed, 16 Apr 2025 13:29:18 +0100, Richard Heathfield wrote:

>

The question is whether a universal termination analyser can be
constructed, and the answer is that it can't.

>

Aren't you kind of putting the cart before the horse with such an
assertion?  Maybe the prior art you are basing that assertion on is
wrong?

>
You're speaking from ignorance of mathematics.  The halting problem has
been unequivocally proven.  It is a simple theorem, only slightly more
complicated than 2 + 2 = 4.
>
We're not talking about "prior art", or anything like that.  We're
talking rigorous mathematics.  We're talking about absolute truth,
something that Peter Olcott does not understand.  You don't need to
join him.

>
>
Indeed.
>
For the benefit of 'Mr Flibble'(!), the proof is a reductio proof that
works as follows.
>
The question before us is whether a universal termination analyser (A)
can be constructed.
>
A takes two inputs - a program P, and data D - and answers the question
'given D as its input, does P halt?' We will notate this as A(P,D).
>
How it works - parsing the source code, executing the program like a
debugger, casting runes, whatever - is irrelevant, as long as it works,
/no matter what program it is given/.
>
Alan Turing reasoned along these lines:
>
1) We assume that A /can/ be built.
>
2) We arrange A so that if A(P,D) determines that P(D) halts, it enters
an infinite loop. If A(P,D) determines that P(D) doesn't halt, however,
it halts.
>
3) We now run A(A,A). That is, we feed A with itself as the program to
run and itself as the data to use, and we ask it whether A(A) will halt.
>
4) So, /does/ A(A) halt? Yes, but only if it doesn't.
>
     Does A(A) enter an infinite loop? Yes, but only if it doesn't.
>
A is in a bind because it cannot settle on either answer.
>
This is an absurd conclusion, so a premise must be at fault. But we only
have one premise: "We assume that A /can/ be built." So we must conclude
that it can't.
>
QED, reductio ad absurdum.
>
If Mr Flibble would like to point out the flaw in the reasoning, he is
more than welcome to try.

 You are ignoring the elephant in the room:

I see no elephants.

the category error associated
with pathological input.  One simply has to add a third halting result of
"pathological input" and we are fine.

That's just another way of saying that the universal termination analyser as specified (determining whether P(D) does or does not eventually halt) can't be written. If it can't determine whether P(D) halts, no matter how pathological, it isn't universal.
--
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