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

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