Path: ...!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: Mon, 29 Jul 2024 11:25:27 -0500
Organization: A noiseless patient Spider
Lines: 78
Message-ID: <v88fpn$i7kl$4@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>
 <v830vj$3dftr$10@dont-email.me> <v831eq$3c7$2@news.muc.de>
 <v8320m$3e9sa$1@dont-email.me> <v84v31$3rsds$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 29 Jul 2024 18:25:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9d358cc663705f17d44fb4afa23cd753";
	logging-data="597653"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ydAemL815c0Y0UjKl5utI"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:bKOjqcSTLBugCSUdqgKWrr0AVA8=
Content-Language: en-US
In-Reply-To: <v84v31$3rsds$1@dont-email.me>
Bytes: 4654

On 7/28/2024 3:21 AM, Mikko wrote:
> On 2024-07-27 14:59:34 +0000, olcott said:
> 
>> On 7/27/2024 9:50 AM, Alan Mackenzie wrote:
>>> olcott <polcott333@gmail.com> wrote:
>>>> 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.
>>>
>>> I think you would do better to "paraphrase" it that a correct simulator
>>> cannot always be a termination analyser.  The two are different things.
>>>
>>
>> *When you say if backwards (like that) it makes less sense*
>> A correct termination analyzer can always be based on a correct 
>> simulator using this criteria:
>>
>> <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>
> 
> The quoted criterion requires a partial simulation that discontinues the
> simulation in a situation where the input specifies that the execution
> must be continued.
> 
> It also requires that the analyzer must be able to determine whithout
> simulation whether the unsimulated behaviour ever terminates.

void Infinite_Recursion()
{
   Infinite_Recursion();
}

_Infinite_Recursion()
[0000215a] 55         push ebp      ; 1st line
[0000215b] 8bec       mov ebp,esp   ; 2nd line
[0000215d] e8f8ffffff call 0000215a ; 3rd line
[00002162] 5d         pop ebp
[00002163] c3         ret
Size in bytes:(0010) [00002163]

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

If you cannot see that the above x86 machine code proves that
it will never halt then you can't possibly understand what I
have been saying.

It is like you reject mathematical induction as a wild guess.

>  In some
> cases this is determinable but no analyzer can determine it in all
> cases. Your attempt does it right in some cases but gets wrong the
> case that many consider the most interesting.
> 

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