Re: Halting Problem: What Constitutes Pathological Input

Op 07.mei.2025 om 03:39 schreef olcott:

On 5/6/2025 5:41 PM, Richard Damon wrote:

On 5/6/25 11:23 AM, olcott wrote:

On 5/6/2025 4:30 AM, Mikko wrote:

On 2025-05-05 19:27:18 +0000, olcott said:
>

On 5/5/2025 2:12 PM, dbush wrote:

On 5/5/2025 2:47 PM, olcott wrote:

On 5/5/2025 1:21 PM, dbush wrote:

On 5/5/2025 2:14 PM, olcott wrote:

On 5/5/2025 11:16 AM, dbush wrote:

On 5/5/2025 12:13 PM, Mr Flibble wrote:

On Mon, 05 May 2025 11:58:50 -0400, dbush wrote:
>

On 5/5/2025 11:51 AM, olcott wrote:

On 5/5/2025 10:17 AM, Mr Flibble wrote:

What constitutes halting problem pathological input:
>
Input that would cause infinite recursion when using a decider of the
simulating kind.
>
Such input forms a category error which results in the halting problem
being ill-formed as currently defined.
>
/Flibble

>
I prefer to look at it as a counter-example that refutes all of the
halting problem proofs.

>
Which start with the assumption that the following mapping is computable
and that (in this case) HHH computes it:
>
>
Given any algorithm (i.e. a fixed immutable sequence of instructions) X
described as <X> with input Y:
>
A solution to the halting problem is an algorithm H that computes the
following mapping:
>
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed
directly
>
>
>

int DD()
{
    int Halt_Status = HHH(DD);
    if (Halt_Status)
      HERE: goto HERE;
    return Halt_Status;
}
>
https://github.com/plolcott/x86utm
>
The x86utm operating system includes fully operational HHH and DD.
https://github.com/plolcott/x86utm/blob/master/Halt7.c
>
When HHH computes the mapping from *its input* to the behavior of DD
emulated by HHH this includes HHH emulating itself emulating DD. This
matches the infinite recursion behavior pattern.
>
Thus the Halting Problem's "impossible" input is correctly determined
to be non-halting.
>
>

>
Which is a contradiction.  Therefore the assumption that the above
mapping is computable is proven false, as Linz and others have proved
and as you have *explicitly* agreed is correct.

>
The category (type) error manifests in all extant halting problem proofs
including Linz.  It is impossible to prove something which is ill- formed
in the first place.
>
/Flibble

>
All algorithms either halt or do not halt when executed directly. Therefore the problem is not ill formed.
>

>
When BOTH Boolean RETURN VALUES are the wrong answer
THEN THE PROBLEM IS ILL-FORMED. Self-contradiction must
be screened out as semantically incorrect.

>
In other words, you're claiming that there exists an algorithm, i.e. a fixed immutable sequence of instructions, that neither halts nor does not halt when executed directly.
>

>
That is not what I said.

>
Then there's no category error, and the halting function is well defined.  It's just that no algorithm can compute it.

>
It is insufficiently defined thus causing it
to be incoherently defined.

>
It is well defined. There are computations that halt and computations that
do not. Nothing else is in the scope of the halting problem.
>

>
It is incorrectly defined when-so-ever it is not specified
that a specific sequence of steps must be applied to the
input to derive the output.

>
Functions don't define the steps that create the mapping.
>
It is algorithms that perform them
>

 We are saying the same thing here using different words.

No that is not the same thing. A mapping can be defined without an algorithm. Not for each mapping a correct algorithm exists.

There must be an algorithm having a specified sequence
of steps that are applied to the input to derive the output.
 

Your 'must' has no basis.