Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Incorrect requirements --- Computing the mapping from the input
 to HHH(DD)
Date: Sat, 10 May 2025 10:18:57 +0200
Organization: A noiseless patient Spider
Lines: 132
Message-ID: <vvn25i$3dv8d$4@dont-email.me>
References: <vv97ft$3fg66$1@dont-email.me> <vvil99$1ugd5$1@dont-email.me>
 <vvinvp$1vglb$1@dont-email.me> <vviv75$222r6$1@dont-email.me>
 <vvj1fp$22a62$1@dont-email.me> <vvj2j6$23gk7$1@dont-email.me>
 <as9TP.251456$lZjd.93653@fx05.ams4> <87msbmeo3b.fsf@nosuchdomain.example.com>
 <vvjc9b$27753$1@dont-email.me> <87ecwyekg2.fsf@nosuchdomain.example.com>
 <vvjg6a$28g5i$3@dont-email.me>
 <d577d485d0f5dfab26315f54f91eb84f25eecc40@i2pn2.org>
 <87bjs2cyj6.fsf@nosuchdomain.example.com> <vvkffn$2m36t$4@dont-email.me>
 <vvl84g$2rl0l$10@dont-email.me>
 <c0b0db5de5c7f7ccb24b06d44108deb41fbde8dc@i2pn2.org>
 <vvlm2k$30idv$1@dont-email.me> <vvlnad$2uvnf$5@dont-email.me>
 <vvlnpj$30vce$1@dont-email.me> <vvlsp5$31vqc$1@dont-email.me>
 <vvlv04$32kt3$1@dont-email.me> <87r00xchn5.fsf@nosuchdomain.example.com>
 <vvmg8i$3a34p$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 10 May 2025 10:18:58 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6132ef5c9a5712f5fb4e052234097a74";
	logging-data="3603725"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19N3uYEe4FHi5W77Db7/Yep"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:l/aaG0v/t40hz7wku6jNYpJmfrM=
Content-Language: nl, en-GB
In-Reply-To: <vvmg8i$3a34p$5@dont-email.me>

Op 10.mei.2025 om 05:13 schreef olcott:
> On 5/9/2025 9:40 PM, Keith Thompson wrote:
>> olcott <polcott333@gmail.com> writes:
>>> On 5/9/2025 4:40 PM, Richard Heathfield wrote:
>>>> On 09/05/2025 21:15, olcott wrote:
>>>>> On 5/9/2025 3:07 PM, Richard Heathfield wrote:
>>>>>> On 09/05/2025 20:46, olcott wrote:
>>>>>>> We have not begun to get into any of those points.
>>>>>>> We are only asking can DDD correctly simulated
>>>>>>> by any HHH that can exist ever reach its own
>>>>>>> "return" instruction.
>>>>>>
>>>>>> DDD can't be correctly simulated by itself (which is effectively
>>>>>> what you're trying to do when you fire up the simulation from
>>>>>> inside DDD).
>>>>>
>>>>> How the Hell did you twist my words to say that?
>>>> I haven't touched your words. What I have done is to observe that
>>>> DDD's /only/ action is to call a simulator. Since DDD isn't itself a
>>>> simulator, there is nothing to simulate except a call to a
>>>> simulator.
>>>> It's recursion without a base case - a rookie error.
>>>> HHH cannot successfully complete its task, because it never regains
>>>> control after the first recursion. To return, it must abort the
>>>> simulation, which means the simulation fails.
>>>>
>>>>> void DDD()
>>>>> {
>>>>>     HHH(DDD);
>>>>>     return;
>>>>> }
>>>>>
>>>>> When 1 or more statements of DDD are correctly
>>>>> simulated by HHH then this correctly simulated
>>>>> DDD cannot possibly reach its own “return statement”.
>>>> On what grounds can you persuade an extraordinarily sceptical
>>>> readership that HHH 'correctly simulated' DDD?
>>>
>>> Any competent C programmer can see that
>>> the call from DDD to HHH(DDD) (its own simulator)
>>> is equivalent to infinite recursion.
>>>
>>> On 5/8/2025 8:30 PM, Keith Thompson wrote:
>>>> Assuming that HHH(DDD) "correctly simulates" DDD, and assuming it
>>>> does nothing else, your code would be equivalent to this:
>>>>
>>>>       void DDD(void) {
>>>>           DDD();
>>>>           return;
>>>>       }
>>>>
>>>> Then the return statement (which is unnecessary anyway) will never be
>>>> reached.  In practice, the program will likely crash due to a stack
>>>> overflow, unless the compiler implements tail-call optimization, in
>>>> which case the program might just run forever -- which also means the
>>>> unnecessary return statement will never be reached.
>>
>> I had not intended to post again, but I feel the need to make
>> a clarification.
>>
>> I acknowledged that the return statement would never be reached
>> *given the assumption* that HHH correctly simulates DDD.  Given
>> that assumption, a call to DDD() should be equivalent to a call
>> to HHH(DDD).
>>
> 
> Yes and then I moved on the next tiny incremental> step of my proof. Correctly simulated less than
> an infinite number of instructions does not help
> the simulated DDD to reach its "return statement"
> final halt state.


The word 'tiny' is misleading. It is a fundamental change. Now HHH does 
no longer do a correct simulation, because it ignores the input part of 
the input that specifies that HHH simulates only a *finite* number of steps.

> 
>> I did not address whether the assumption is valid.  I merely
>> temporarily accepted it for the sake of discussion, just as I would
>> accept that if I were ten feet tall I would bump my head against
>> the ceiling in my house.
>>
>> The discussion I had with olcott did not reach the point of
>> discussing *how* HHH could correctly simulate DDD, or whether it
>> would even be logically possible for it to do so. 
> 
> Right this takes a glimmering of understanding of
> the x86 language. The x86 language it needed to
> get an exactly precise understanding of the control
> flow of DDD as directed graph state transition
> diagram.

Yes and it takes into account that the input contains x86 instruction to 
abort and halt.

> 
>> I also did not
>> address any issues of partial simulation, where olcott claims that
>> HHH can "accurately simulate" only a few x86 instructions rather
>> than simulating its entire execution. 
> 
>> I did not participate in
>> any discussion that would require knowledge of x86 machine or
>> assembly code.  (I have no doubt that I could learn x86 machine
>> and assembly code reasonably well if motivated to do so, but I am
>> not so motivated.)
>>
>> What I acknowledged was barely more than "if HHH correctly simulates
>> DDD, then HHH correctly simulates DDD". 
> 
> No much more than this you acknowledged that
> when DDD is correctly simulated by HHH that
> the simulated DDD cannot possibly reach its
> own "return statement" (final halt state)

But when that HHH ignores an important part of its input, it is no 
longer correct.

> 
> This is very important to computer science because
> non-termination is entirely measured by the impossibility
> of reaching a final halt state.
> 
>  From all of the we know that when HHH(DDD) reports
> on the behavior of its correct simulation of its input
> that it can correctly reject this input as not
> specifying a sequence of configurations that halts.

It can only report that it aborted the simulation prematurely, without 
analysing the full input.