Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Tue, 6 May 2025 08:10:27 -0400
Organization: A noiseless patient Spider
Lines: 149
Message-ID: <vvcu7i$2sk4a$1@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvb4ok$o4v0$9@dont-email.me>
 <vvb52g$15u5b$6@dont-email.me> <vvb5ca$o4v0$10@dont-email.me>
 <vvb5vp$15u5b$7@dont-email.me> <vvb675$o4v0$11@dont-email.me>
 <vvb9d7$1av94$3@dont-email.me> <vvbani$1b6l1$1@dont-email.me>
 <vvbb6s$1av94$4@dont-email.me> <vvbcb3$1b6l1$2@dont-email.me>
 <vvbe0j$1av94$8@dont-email.me> <vvbecc$1b6l1$6@dont-email.me>
 <vvbhk0$1ijna$1@dont-email.me> <vvbjjg$1kegb$1@dont-email.me>
 <vvbk93$1l4cf$1@dont-email.me> <vvbkft$1kegb$4@dont-email.me>
 <vvbl71$1ljaj$1@dont-email.me> <vvbma3$1kegb$5@dont-email.me>
 <vvbmp0$1ljaj$2@dont-email.me> <vvbqd5$1tr5o$1@dont-email.me>
 <vvbrha$1us1f$1@dont-email.me> <vvbs2s$1tr5o$2@dont-email.me>
 <vvbtfh$20bmu$1@dont-email.me> <vvbtos$1tr5o$3@dont-email.me>
 <vvbu94$20bmu$2@dont-email.me> <vvbuv1$1tr5o$4@dont-email.me>
 <vvc088$20bmu$3@dont-email.me> <vvc0j8$1tr5o$5@dont-email.me>
 <vvc0ts$23ln3$1@dont-email.me> <vvc11j$1tr5o$6@dont-email.me>
 <vvc201$24i9i$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 06 May 2025 14:10:27 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="80f1b624b2b67f0b720d14d0d7fce339";
	logging-data="3035274"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX192iFQUS1rHxdUe0WuyRBnA"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:R62H6j3jTujsxYNnD6WwphStg7A=
Content-Language: en-US
In-Reply-To: <vvc201$24i9i$1@dont-email.me>

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.