Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Unix will self-destruct in five seconds... 4... 3... 2... 1...


computers / comp.ai.philosophy / My_Dishonest_reviewers:_André,_Ben,_Mike,_Dennis,_Richard_V4

SubjectAuthor
o My_Dishonest_reviewers:_André,_Ben,_Mike,_Deolcott

1
Subject: My_Dishonest_reviewers:_André,_Ben,_Mike,_Dennis,_Richard_V4
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Mon, 18 Apr 2022 15:44 UTC
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 18 Apr 2022 10:44:40 -0500
Date: Mon, 18 Apr 2022 10:44:39 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.8.0
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: My_Dishonest_reviewers:_André,_Ben,_Mike,_De
nnis,_Richard_V4
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <lZWdnZuUyvf1GsD_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 72
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-SSQHT+u7OUrl9av4IHb+Yl+HotpDJy9BqSV9ADfh+idibFhxwfAMLZYjXiWNuVinXU0SOqW2cG3jzFy!fZjhWSBpOiYvWHGkmZlRGaXMuMLfXkBYJelE+B5lzUEtC9zsmbdpKbZ/AK374fnAY8AQcQdm82Im
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: 4190
View all headers
The function named H continues to simulate its input using an x86 emulator until this input halts on its own or H detects that it will never halt on its own. The technical computer science term "halt" means that a program will reach its last instruction technically called its final state. For P this would be its machine address [000009f0].

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


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

_P()
[000009d6](01) 55         push ebp
[000009d7](02) 8bec       mov ebp,esp
[000009d9](03) 8b4508     mov eax,[ebp+08]
[000009dc](01) 50         push eax         // push P
[000009dd](03) 8b4d08     mov ecx,[ebp+08]
[000009e0](01) 51         push ecx         // push P
[000009e1](05) e840feffff call 00000826    // call H
[000009e6](03) 83c408     add esp,+08
[000009e9](02) 85c0       test eax,eax
[000009eb](02) 7402       jz 000009ef
[000009ed](02) ebfe       jmp 000009ed
[000009ef](01) 5d         pop ebp
[000009f0](01) c3         ret              // Final state
Size in bytes:(0027) [000009f0]

The simulated input to H(P,P) cannot possibly reach its own final state of [000009f0] it keeps repeating [000009d6] to [000009e1] until aborted.

Begin Local Halt Decider Simulation
....[000009d6][00211368][0021136c] 55         push ebp         // enter P
....[000009d7][00211368][0021136c] 8bec       mov ebp,esp
....[000009d9][00211368][0021136c] 8b4508     mov eax,[ebp+08]
....[000009dc][00211364][000009d6] 50         push eax         // Push P
....[000009dd][00211364][000009d6] 8b4d08     mov ecx,[ebp+08]
....[000009e0][00211360][000009d6] 51         push ecx         // Push P
....[000009e1][0021135c][000009e6] e840feffff call 00000826    // Call H
....[000009d6][0025bd90][0025bd94] 55         push ebp         // enter P
....[000009d7][0025bd90][0025bd94] 8bec       mov ebp,esp
....[000009d9][0025bd90][0025bd94] 8b4508     mov eax,[ebp+08]
....[000009dc][0025bd8c][000009d6] 50         push eax         // Push P
....[000009dd][0025bd8c][000009d6] 8b4d08     mov ecx,[ebp+08]
....[000009e0][0025bd88][000009d6] 51         push ecx         // Push P
....[000009e1][0025bd84][000009e6] e840feffff call 00000826    // Call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

Because the correctly simulated input to H(P,P) cannot possibly reach its own final state at [000009f0] it is necessarily correct for H to reject this input as non-halting.

For any program H that might determine if programs halt, a "pathological" program P, called with some input, can pass its own source and its input to H and then specifically do the opposite of what H predicts P will do. No H can exist that handles this case.

https://en.wikipedia.org/wiki/Halting_problem

--
Copyright 2022 Pete Olcott

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


1
rocksolid light 0.7.2
clearneti2ptor