Deutsch   English   Français   Italiano  
<vt9l5c$1tds$3@dont-email.me>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: DDD simulated by HHH cannot possibly halt (Halting Problem)
Date: Thu, 10 Apr 2025 19:44:44 -0400
Organization: A noiseless patient Spider
Lines: 134
Message-ID: <vt9l5c$1tds$3@dont-email.me>
References: <vsnchj$23nrb$2@dont-email.me> <vso4a5$302lq$1@dont-email.me>
 <vsqhuu$1hl94$2@dont-email.me> <vsqknb$1ldpa$1@dont-email.me>
 <vsrmn8$2o2f2$1@dont-email.me> <vstku7$p4u7$1@dont-email.me>
 <vsu95l$1c5kt$1@dont-email.me> <vt01l0$39kn7$1@dont-email.me>
 <vt28vk$1fe7a$1@dont-email.me> <vt2k6t$1onvt$1@dont-email.me>
 <vt3ef4$2flgf$1@dont-email.me> <vt3fgd$2gu7u$1@dont-email.me>
 <vt6apu$12sjs$2@dont-email.me> <vt6g1f$180qf$1@dont-email.me>
 <vt6lmk$1djk6$1@dont-email.me> <vt6mts$1c6b1$1@dont-email.me>
 <vt77vk$1t4il$1@dont-email.me> <vt79c6$1s72i$1@dont-email.me>
 <vt7fdv$26l43$1@dont-email.me> <vt7g2v$2762k$1@dont-email.me>
 <vt9iv1$1snb$1@dont-email.me> <vt9k21$1tds$1@dont-email.me>
 <vt9kr1$3f0a$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 11 Apr 2025 01:44:44 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="051148395ecf80642a827d679b03fa46";
	logging-data="62908"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX199tJCQ28c1GUCCMJU84rd8"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:rgj2DhQ4CRs7Mfl8qKfHufoYYns=
Content-Language: en-US
In-Reply-To: <vt9kr1$3f0a$1@dont-email.me>
Bytes: 6983

On 4/10/2025 7:39 PM, olcott wrote:
> On 4/10/2025 6:25 PM, dbush wrote:
>> On 4/10/2025 7:07 PM, olcott wrote:
>>> On 4/9/2025 11:05 PM, dbush wrote:
>>>> On 4/9/2025 11:54 PM, olcott wrote:
>>>>> On 4/9/2025 9:11 PM, dbush wrote:
>>>>>> On 4/9/2025 9:47 PM, olcott wrote:
>>>>>>> On 4/9/2025 3:56 PM, dbush wrote:
>>>>>>>> On 4/9/2025 4:35 PM, olcott wrote:
>>>>>>>>> On 4/9/2025 1:58 PM, Fred. Zwarts wrote:
>>>>>>>>>> Op 09.apr.2025 om 19:29 schreef olcott:
>>>>>>>>>>>
>>>>>>>>>>> On 4/8/2025 10:31 AM, Fred. Zwarts wrote:
>>>>>>>>>>>> Op 08.apr.2025 om 17:13 schreef olcott:
>>>>>>>>>>>>> On 4/8/2025 2:45 AM, Fred. Zwarts wrote:
>>>>>>>>>>>>>> Op 08.apr.2025 om 06:33 schreef olcott:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> typedef void (*ptr)();
>>>>>>>>>>>>>>> int HHH(ptr P);
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> int DD()
>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>>>>>>>>>    if (Halt_Status)
>>>>>>>>>>>>>>>      HERE: goto HERE;
>>>>>>>>>>>>>>>    return Halt_Status;
>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> int main()
>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>    HHH(DD);
>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> *Simulating termination analyzer Principle*
>>>>>>>>>>>>>>> It is always correct for any simulating termination
>>>>>>>>>>>>>>> analyzer to stop simulating and reject any input that
>>>>>>>>>>>>>>> would otherwise prevent its own termination.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> In this case there is nothing to prevent, because the 
>>>>>>>>>>>>>> finite string specifies a program that halts. 
>>>>>>>>>>>>>
>>>>>>>>>>>>> int DD()
>>>>>>>>>>>>> {
>>>>>>>>>>>>>    int Halt_Status = HHH(DD);
>>>>>>>>>>>>>    if (Halt_Status)
>>>>>>>>>>>>>      HERE: goto HERE;
>>>>>>>>>>>>>    return Halt_Status;
>>>>>>>>>>>>> }
>>>>>>>>>>>>>
>>>>>>>>>>>>> This stuff is simply over-your-head.
>>>>>>>>>>>>> HHH(DD) meets the above: *Simulating termination analyzer 
>>>>>>>>>>>>> Principle*
>>>>>>>>>>>>> Anyone with sufficient competence with the C programming 
>>>>>>>>>>>>> language
>>>>>>>>>>>>> will understand this.
>>>>>>>>>>>>>
>>>>>>>>>>>> Everyone with a little bit of C knowledge understands that 
>>>>>>>>>>>> if HHH returns with a value 0, then DDD halts. 
>>>>>>>>>>>
>>>>>>>>>>> DDD CORRECTLY SIMULATED BY HHH
>>>>>>>>>>> NOT ANY OTHER DAMN DDD IN THE UNIVERSE NITWIT.
>>>>>>>>>>>
>>>>>>>>>> If HHH would correctly simulate DD (and the functions called 
>>>>>>>>>> by DD) then the simulated HHH would return to DD and DD would 
>>>>>>>>>> halt.
>>>>>>>>>
>>>>>>>>> Simply over your level of technical competence.
>>>>>>>>>
>>>>>>>>>> But HHH failed to complete the simulation of the halting program, 
>>>>>>>>>
>>>>>>>>> HHH is only required to report on the behavior of its
>>>>>>>>> own correct simulation (meaning the according to the
>>>>>>>>> semantics of the C programming language) and would be
>>>>>>>>> incorrect to report on any other behavior.
>>>>>>>>
>>>>>>>> Which means HHH has conflicting requirements,
>>>>>>>
>>>>>>> No, it just means that the ones that you have
>>>>>>> been saying are f-cked up and no-one noticed this before.
>>>>>>>
>>>>>>>  > because to perform a
>>>>>>>  > correct simulation of its input it cannot halt itself, and 
>>>>>>> therefore
>>>>>>>  > can't report that.
>>>>>>> In other words you simply "don't believe in" the variant
>>>>>>> form of mathematical induction that HHH uses.
>>>>>>
>>>>>> No, because the form it uses is "changing the input".
>>>>>>
>>>>>> Changing the input is not allowed.
>>>>>
>>>>> I never changed the input.
>>>>
>>>> You absolutely did when you used the form of induction you did.
>>>>
>>>> You hypothesized changing the code of HHH, which is part of the input.
>>>>
>>>> Changing the input, hypothetically or otherwise, is not allowed.
>>>
>>> *Simulating termination analyzer Principle*
>>> It is always correct for any simulating termination
>>> analyzer to stop simulating and reject any input that
>>> would otherwise prevent its own termination.
>>
>> Except when doing so changes the input, as you're doing.
>>
>> Changing the input is not allowed.
> 
> As I pointed out simulating termination analyzers
> are inherently required to terminate the simulation
> of any input that would prevent their own termination.

Category error.  That would imply that the termination analyzer, i.e. an 
algorithm, has some potential choice or variation.

An algorithm is fixed and immutable and only does one thing, always 
giving the same output for the same input.  To describe any variation is 
talking about a completely different algorithm and therefore out of scope.

The only thing a simulating termination analyzer is required to do is 
what all termination analyzers are required to do, and that is map the 
halting function:


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