novaBBS - comp.lang.c - Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

<xpmdnb7bu_9vxOf_nZ2dnUU7_8zNnZ2d@giganews.com>

https://www.novabbs.com/devel/article-flat.php?id=21637&group=comp.lang.c#21637

copy link Newsgroups: comp.theory comp.ai.philosophy comp.lang.c comp.lang.c++
Followup: comp.theory

Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 10 May 2022 07:26:26 -0500
Date: Tue, 10 May 2022 07:26:25 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs
]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <xpmdnb7bu_9vxOf_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 106
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-7dlaBDR5AK+v7AjRldOkFe2mZukcWwggN7Z6rzhrjtSB3x9GYBYuUUtv1q8ghVErzBUeYhckvHHrY/D!MxB6mADoMWoypQgpcLECZ2SgA7x4vyvuHzVjCU7rnhDFOWsvHDx/aC25nEq+QiaQ5NGZkGGB24s=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5658

by: olcott - Tue, 10 May 2022 12:26 UTC

(a) Verify that the execution trace of P by H is correct by comparing
this execution trace to the ax86 source-code of P.

(b) Verify that this execution trace shows that P is stuck in infinitely
nested simulation (a non-halting behavior).

#include <stdint.h>
#define u32 uint32_t

void P(u32 x)
{ if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{ Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax
[00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx
[0000135d](05) e840feffff call 000011a2 // call H
[00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]

_main()
[00001372](01) 55 push ebp
[00001373](02) 8bec mov ebp,esp
[00001375](05) 6852130000 push 00001352 // push P
[0000137a](05) 6852130000 push 00001352 // push P
[0000137f](05) e81efeffff call 000011a2 // call H
[00001384](03) 83c408 add esp,+08
[00001387](01) 50 push eax
[00001388](05) 6823040000 push 00000423 // "Input_Halts = "
[0000138d](05) e8e0f0ffff call 00000472 // call Output
[00001392](03) 83c408 add esp,+08
[00001395](02) 33c0 xor eax,eax
[00001397](01) 5d pop ebp
[00001398](01) c3 ret
Size in bytes:(0039) [00001398]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
....[00001372][0010229e][00000000] 55 push ebp
....[00001373][0010229e][00000000] 8bec mov ebp,esp
....[00001375][0010229a][00001352] 6852130000 push 00001352 // push P
....[0000137a][00102296][00001352] 6852130000 push 00001352 // push P
....[0000137f][00102292][00001384] e81efeffff call 000011a2 // call H

Begin Local Halt Decider Simulation Execution Trace Stored at:212352
....[00001352][0021233e][00212342] 55 push ebp // enter P
....[00001353][0021233e][00212342] 8bec mov ebp,esp
....[00001355][0021233e][00212342] 8b4508 mov eax,[ebp+08]
....[00001358][0021233a][00001352] 50 push eax // push P
....[00001359][0021233a][00001352] 8b4d08 mov ecx,[ebp+08]
....[0000135c][00212336][00001352] 51 push ecx // push P
....[0000135d][00212332][00001362] e840feffff call 000011a2 // call H
....[00001352][0025cd66][0025cd6a] 55 push ebp // enter P
....[00001353][0025cd66][0025cd6a] 8bec mov ebp,esp
....[00001355][0025cd66][0025cd6a] 8b4508 mov eax,[ebp+08]
....[00001358][0025cd62][00001352] 50 push eax // push P
....[00001359][0025cd62][00001352] 8b4d08 mov ecx,[ebp+08]
....[0000135c][0025cd5e][00001352] 51 push ecx // push P
....[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

H sees that P is calling the same function from the same machine address
with identical parameters, twice in sequence. This is the infinite
recursion (infinitely nested simulation) non-halting behavior pattern.

....[00001384][0010229e][00000000] 83c408 add esp,+08
....[00001387][0010229a][00000000] 50 push eax
....[00001388][00102296][00000423] 6823040000 push 00000423 //
"Input_Halts = "
---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 // call Output
Input_Halts = 0
....[00001392][0010229e][00000000] 83c408 add esp,+08
....[00001395][0010229e][00000000] 33c0 xor eax,eax
....[00001397][001022a2][00100000] 5d pop ebp
....[00001398][001022a6][00000004] c3 ret
Number of Instructions Executed(15892) lines = 237 pages

Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5

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

Re: Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

<71017c2a-9ba9-421d-a928-03742d35adbfn@googlegroups.com>

copy mid

https://www.novabbs.com/devel/article-flat.php?id=21648&group=comp.lang.c#21648

copy link Newsgroups: comp.lang.c

X-Received: by 2002:a0c:b312:0:b0:45a:a8d7:ecd6 with SMTP id s18-20020a0cb312000000b0045aa8d7ecd6mr21268525qve.100.1652256990418;
Wed, 11 May 2022 01:16:30 -0700 (PDT)
X-Received: by 2002:ac8:5915:0:b0:2f3:db7f:7ad8 with SMTP id
21-20020ac85915000000b002f3db7f7ad8mr11915100qty.77.1652256990247; Wed, 11
May 2022 01:16:30 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c
Date: Wed, 11 May 2022 01:16:30 -0700 (PDT)
In-Reply-To: <xpmdnb7bu_9vxOf_nZ2dnUU7_8zNnZ2d@giganews.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23c7:a280:3401:45ae:3d7f:7f11:60dc;
posting-account=3LA7mQoAAAByiBtHIUvpFq0_QEKnHGc9
NNTP-Posting-Host: 2a00:23c7:a280:3401:45ae:3d7f:7f11:60dc
References: <xpmdnb7bu_9vxOf_nZ2dnUU7_8zNnZ2d@giganews.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <71017c2a-9ba9-421d-a928-03742d35adbfn@googlegroups.com>
Subject: Re: Proof that H(P,P)==0 is correct [ refuting the halting problem
proofs ]
From: mark.blu...@gmail.com (Mark Bluemel)
Injection-Date: Wed, 11 May 2022 08:16:30 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 1351

by: Mark Bluemel - Wed, 11 May 2022 08:16 UTC

DEC diagnostics would run on a dead whale. -- Mel Ferentz

devel / comp.lang.c / Proof that H(P,P)==0 is correct [ refuting the halting problem proofs ]

Subject	Author
Proof that H(P,P)==0 is correct [ refuting the halting problem proofs	olcott
Re: Proof that H(P,P)==0 is correct [ refuting the halting problem	Mark Bluemel