Path: ...!feeds.phibee-telecom.net!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Hypothetical possibilities --- Sipser approved criteria
Date: Sat, 27 Jul 2024 09:41:54 -0500
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <v830vj$3dftr$10@dont-email.me>
References: <v7gl30$3j9fi$1@dont-email.me> <v7led6$kacj$1@dont-email.me>
 <v7lsg5$luh0$5@dont-email.me> <v7nm9m$1433k$1@dont-email.me>
 <v7ofe7$17h8r$6@dont-email.me> <v7qfu0$1m6vf$1@dont-email.me>
 <v7r040$1onhe$3@dont-email.me> <v7vlbj$2ofet$1@dont-email.me>
 <v80a2u$2rabc$4@dont-email.me> <v825jo$39i9l$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 27 Jul 2024 16:41:55 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c4ee90cee71e7f0114aee78a4820d739";
	logging-data="3588027"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+UJtl2YhXmf/jEMQC5TgcK"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:4gy+ql/OPxCOa/xuSBXGbMYZjSs=
Content-Language: en-US
In-Reply-To: <v825jo$39i9l$1@dont-email.me>
Bytes: 3464

On 7/27/2024 1:54 AM, Mikko wrote:
> 
> If a simulator correctly simulates a finite number of instructions
> where x86 program specifies an execution of an infinite number of
> instructions then the simulation deviates from x86 semantics at the
> point where the simulation stops but the x86 semantics specify
> countinuation.
> 

I paraphrase this as the requirement for a termination analyzer
to never terminate. That *is* a ridiculously stupid requirement.

*Here are the actual requirements*
<MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
     If simulating halt decider H correctly simulates its input D
     until H correctly determines that its simulated D would never
     stop running unless aborted then

     H can abort its simulation of D and correctly report that D
     specifies a non-halting sequence of configurations.
</MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>

*H correctly simulates its input D until*
*H correctly simulates its input D until*
*H correctly simulates its input D until*

*A concrete simple example is shown below*

void Infinite_Recursion()
{
   Infinite_Recursion();
}

_Infinite_Recursion()
[0000215a] 55               push ebp
[0000215b] 8bec             mov ebp,esp
[0000215d] e8f8ffffff       call 0000215a ; recursive call
[00002162] 5d               pop ebp
[00002163] c3               ret
Size in bytes:(0010) [00002163]

Begin Local Halt Decider Simulation   Execution Trace Stored at:113934
Decide_Halting_HH:1
[0000215a][00113924][00113928] 55               push ebp
[0000215b][00113924][00113928] 8bec             mov ebp,esp
[0000215d][00113920][00002162] e8f8ffffff       call 0000215a
[0000215a][0011391c][00113924] 55               push ebp
[0000215b][0011391c][00113924] 8bec             mov ebp,esp
[0000215d][00113918][00002162] e8f8ffffff       call 0000215a
Local Halt Decider: Infinite Recursion Detected Simulation Stopped


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