Re: Halting Problem: What Constitutes Pathological Input

On 5/6/2025 12:08 AM, olcott wrote:

On 5/5/2025 10:52 PM, dbush wrote:

On 5/5/2025 11:50 PM, olcott wrote:

On 5/5/2025 10:44 PM, dbush wrote:

On 5/5/2025 11:38 PM, olcott wrote:

On 5/5/2025 10:16 PM, dbush wrote:

On 5/5/2025 11:05 PM, olcott wrote:

On 5/5/2025 9:56 PM, dbush wrote:

On 5/5/2025 10:51 PM, olcott wrote:

On 5/5/2025 9:27 PM, dbush wrote:

On 5/5/2025 10:18 PM, olcott wrote:

On 5/5/2025 8:59 PM, dbush wrote:

On 5/5/2025 8:57 PM, olcott wrote:

On 5/5/2025 7:49 PM, dbush wrote:

>
Which starts with the assumption that an algorithm exists that performs the following mapping:
>
>
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
>
>
>

DO COMPUTE THAT THE INPUT IS NON-HALTING
IFF (if and only if) the mapping FROM INPUTS
IS COMPUTED.

>
i.e. it is found to map something other than the above function which is a contradiction.
>

>
The above function VIOLATES COMPUTER SCIENCE.
You make no attempt to show how my claim
THAT IT VIOLATES COMPUTER SCIENCE IS INCORRECT
you simply take that same quote from a computer
science textbook as the infallible word-of-God.

>
All you are doing is showing that you don't understand proof by contradiction,

>
Not at all.

>
>
Yes.
>
The mapping is well defined.

>
You don't even know that "well defined" means
that all of the steps have been specified.

>
A mapping doesn't *have* steps. It's simply an association between an input domain and an output domain.
>

>
Computing the mapping does > have 100% totally specific steps

>
>
So you're assuming an algorithm exists that can compute the below mapping.
>

>
No the mapping below is stupidly wrong.

>
Not at all.
>
I want to know if any arbitrary algorithm X with input Y will halt when executed directly.
>

>
What are ALL of the steps to determine that for HHH(DD) ?

>
In other words, you're assuming that the halting function is computable.
>

 If you don't even know ALL of what computable means you will
not be able to provide these steps.

That you claim there are steps assumes that an algorithm exists that computes the halting function.

 _DD()
[00002133] 55         push ebp      ; housekeeping
[00002134] 8bec       mov ebp,esp   ; housekeeping
[00002136] 51         push ecx      ; make space for local
[00002137] 6833210000 push 00002133 ; push DD
[0000213c] e882f4ffff call 000015c3 ; call HHH(DD)
[00002141] 83c404     add esp,+04
[00002144] 8945fc     mov [ebp-04],eax
[00002147] 837dfc00   cmp dword [ebp-04],+00
[0000214b] 7402       jz 0000214f
[0000214d] ebfe       jmp 0000214d
[0000214f] 8b45fc     mov eax,[ebp-04]
[00002152] 8be5       mov esp,ebp
[00002154] 5d         pop ebp
[00002155] c3         ret
Size in bytes:(0035) [00002155]
 

We then reach a contradiction,

 Exactly what steps lead to a contradiction, don't leave
an y gaps or vagueness.

We start with the assumption that the following mapping is computable and that algorithm 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
We then construct algorithm DD based on algorithm HHH above.  The description of algorithm DD is implements by reference by giving the starting address of function DD.
This description, by reference, consists of the the code of function DD, the code of the function HHH, and the code of everything that HHH calls down to the OS level.  As such, none of this can be modified for any reason, hypothetically or otherwise.
This is a correct description of algorithm DD as it can be used to exactly replicate what happens when this algorithm is executed directly.   This is proven by UTM(DD) doing this.
Given your implementation of algorithm DDD, the function call HHH(DD) returns 0.  Algorithm DD halts when executed directly, so the above mapping maps algorithm DD to "halting", or 1.  HHH was assumed to map the above halting function, however the value it returns doesn't correspond to that mapping.  This is a contradiction.
Therefore, the assumption that an algorithm exists to compute the above mapping is proven false, as Linz and others have proved, and as you have *explicitly* agreed is correct.