Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Simulating termination analyzers for dummies
Date: Mon, 17 Jun 2024 07:20:27 -0500
Organization: A noiseless patient Spider
Lines: 74
Message-ID: <v4p9mb$lavj$1@dont-email.me>
References: <v4oaqu$f9p5$1@dont-email.me> <v4os9e$i70m$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 17 Jun 2024 14:20:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="24f2a1964fe8769a85c52084edf5324e";
	logging-data="699379"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/rv/o5Lgci7cx8xkguFr6t"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:0XXUMUvEbotTtt03FzSU08i68E0=
Content-Language: en-US
In-Reply-To: <v4os9e$i70m$1@dont-email.me>
Bytes: 3530

On 6/17/2024 3:31 AM, Fred. Zwarts wrote:
> Op 17.jun.2024 om 05:33 schreef olcott:
>> To understand this analysis requires a sufficient knowledge of
>> the C programming language and what an x86 emulator does.
>>
>> Unless every single detail is made 100% explicit false assumptions
>> always slip though the cracks. This is why it must be examined at
>> the C level before it is examined at the Turing Machine level.
>>
>> typedef void (*ptr)();
>> int H0(ptr P);
>>
>> void Infinite_Loop()
>> {
>>    HERE: goto HERE;
>> }
>>
>> void Infinite_Recursion()
>> {
>>    Infinite_Recursion();
>> }
>>
>> void DDD()
>> {
>>    H0(DDD);
>>    return;
>> }
>>
>> int main()
>> {
>>    H0(Infinite_Loop);
>>    H0(Infinite_Recursion);
>>    H0(DDD);
>> }
>>
>> Every C programmer that knows what an x86 emulator is knows that when H0
>> emulates the machine language of Infinite_Loop, Infinite_Recursion, and
>> DDD that it must abort these emulations so that itself can terminate
>> normally.
>>
>> When this is construed as non-halting criteria then simulating
>> termination analyzer H0 is correct to reject these inputs as non-
>> halting.
>>
> 
> For Infinite_Loop and Infinite_Recursion that might be true, because 
> there the simulator processes the whole input.
> 
> The H0 case is very different. For H0 there is indeed a false 
> assumption, as you mentioned. Here H0 needs to simulate itself, but the 
> simulation is never able to reach the final state of the simulated self. 
> The abort is always one cycle too early, so that the simulating H0 
> misses the abort. Therefore this results in a false negative.
> (Note that H0 should process its input, which includes the H0 that 
> aborts, not a non-input with an H that does not abort.)
> 
> This results in a impossible dilemma for the programmer. It he creates a 
> H that does not abort, it will not terminate. 

*Therefore what I said is correct*
When every input that must be aborted is construed as non-halting
then the input to H0(DDD) is correctly construed as non-halting.

> If he creates a H that 
> does abort, he creates a false negative. It will never be correct.
> 
> It would be very stupid to construe this as non-halting criteria, 
> because it is clear that it will produce false negatives, i.e. false 
> results.

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer