Sujet : Proof that DD correctly simulated by HH provides the correct halt status criteria
De : polcott333 (at) *nospam* gmail.com (olcott)
Groupes : comp.theory sci.logicDate : 07. Jun 2024, 22:48:57
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <v3vv8a$287qb$1@dont-email.me>
User-Agent : Mozilla Thunderbird
*That no counter-example to the following exists proves that it is true*
*That no counter-example to the following exists proves that it is true*
*That no counter-example to the following exists proves that it is true*
Try to show how this DD correctly simulated by any HH ever
stops running without having its simulation aborted by HH.
_DD()
[00001e12] 55 push ebp
[00001e13] 8bec mov ebp,esp
[00001e15] 51 push ecx
[00001e16] 8b4508 mov eax,[ebp+08]
[00001e19] 50 push eax ; push DD
[00001e1a] 8b4d08 mov ecx,[ebp+08]
[00001e1d] 51 push ecx ; push DD
[00001e1e] e85ff5ffff call 00001382 ; call HH
A {correct simulation} means that each instruction of the
above x86 machine language of DD is correctly simulated
by HH and simulated in the correct order.
Anyone claiming that HH should report on the behavior
of the directly executed DD(DD) is requiring a violation
of the above definition of correct simulation.
Halt deciders are required to compute the mapping from their
input to their own accept or reject state based on the behavior
that this input specifies.
Simulating halt deciders are not allowed to simulate non-halting
inputs for more than a finite number of steps because all deciders
must halt.
The basic strategy of a simulating halt decider is to simulate
an input until (a) The input halts or (b) it correctly determines
that the correctly simulated input cannot possibly stop running
unless its simulation has been aborted.
<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 words10/13/2022>
*Professor Sipser is the best selling author of this textbook*
Introduction to the Theory of Computation, by Michael Sipser
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/Here is the earliest version of the proof (that everyone
has simply ignored for three solid years)
Subject: [Would the simulation of D be infinitely nested unless simulating partial halt decider H terminated its simulation of D?]
On 5/29/2021 2:26 PM, olcott wrote:
Message-ID: <
YJKdnZg9v__rCC_9nZ2dnUU7-QXNnZ2d@giganews.com>
http://al.howardknight.net/?STYPE=msgid&MSGI=%3CYJKdnZg9v__rCC_9nZ2dnUU7-QXNnZ2d%40giganews.com%3EThe fact that the execution trace of D derived by the executed
H and the simulated H exactly matches the machine code of D
proves that each instruction of D was simulated correctly and
in the correct order this conclusively proves that D is correctly
simulated by both of these instances of H.
I explained these details hundreds of times in the last three
years and no one paid any attention to the fact that I proved
that I am correct. Because of this I provided the above dumbed
down version.
-- Copyright 2024 Olcott "Talent hits a target no one else can hit; Geniushits a target no one else can see." Arthur Schopenhauer