Re: Title: A Structural Analysis of the Standard Halting Problem Proof

Liste des GroupesRevenir à ca philosophy 
Sujet : Re: Title: A Structural Analysis of the Standard Halting Problem Proof
De : noreply (at) *nospam* example.org (joes)
Groupes : comp.theory
Date : 24. Jul 2025, 22:24:16
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <105u8a0$r1ct$3@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11
User-Agent : Pan/0.145 (Duplicitous mercenary valetism; d7e168a git.gnome.org/pan2)
Am Thu, 24 Jul 2025 09:32:45 -0500 schrieb olcott:
On 7/24/2025 5:03 AM, Fred. Zwarts wrote:
Op 23.jul.2025 om 17:29 schreef olcott:

The directly executed HHH does reach its final halt state. DDD
correctly simulated by HHH cannot possibly reach its final halt state
no matter what HHH does because it remains stuck in recursive
simulation.
 
Indeed, but irrelevant. The simulating HHH does not do a correct
simulation, it aborts prematurely.

_DDD()
[00002192] 55             push ebp [00002193] 8bec           mov ebp,esp
[00002195] 6892210000     push 00002192  // push DDD [0000219a]
e833f4ffff     call 000015d2  // call HHH [0000219f] 83c404         add
esp,+04 [000021a2] 5d             pop ebp [000021a3] c3             ret
Size in bytes:(0018) [000021a3]
 
Aborting prematurely literally means that after N instructions of DDD
are correctly emulated by HHH that this emulated DDD would reach its own
emulated "ret" instruction final halt state.
What value of N are you proposing?

Let's see: the call to HHH is #4, [waves hands], then another 4 inside
the next level of simulation, and after another 4 the first simulated
HHH (the one called by the input, not the outermost simulator. We are
now 3 levels in) decides that enough is enough and aborts, returning
to the outermost level which takes 3 more instructions to halt,
whereupon our treasured HHH returns that DDD halts. So, 4+4+4+3=15?

Of course the crux is that changing "HHH" changes the input, so HHH
can never do it.

--
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.

Date Sujet#  Auteur
27 Jul 25 o 

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal