Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The trouble with computers is that they do what you tell them, not what you want. -- D. Cohen


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V7 [ pure function ]

SubjectAuthor
o Concise refutation of halting problem proofs V7 [ pure function ]olcott

1
Concise refutation of halting problem proofs V7 [ pure function ]

<r4Wdna6IAqQQ7RD8nZ2dnUU7-Q_NnZ2d@giganews.com>

  copy mid

https://www.novabbs.com/computers/article-flat.php?id=7578&group=comp.ai.philosophy#7578

  copy link   Newsgroups: comp.theory sci.logic sci.math comp.ai.philosophy
Followup: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 11 Nov 2021 13:35:41 -0600
Date: Thu, 11 Nov 2021 13:35:40 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.3.0
Newsgroups: comp.theory,sci.logic,sci.math,comp.ai.philosophy
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V7 [ pure function ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <r4Wdna6IAqQQ7RD8nZ2dnUU7-Q_NnZ2d@giganews.com>
Lines: 66
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-dbQWhvlvfs504oQ1CWDqwxzyB8yXAjo1fCH5gaKn6+a/nwA21jrgKC0zCcfuiQ7MhH8nw1OIuIKyvpj!LERbyir+04c9E1Wh4IfEI4bALUfeWiAN7n8BssJyiH0OCnL0g6UOywXE/Hro6BlFyeLZ3DRwMIK2!GA==
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: 3178
 by: olcott - Thu, 11 Nov 2021 19:35 UTC

Does the call from P() to H() specify infinite recursion?

#include <stdint.h>
#define ptr uintptr_t

void P(ptr x)
{ H(x, x);
}

int H(ptr x, ptr y)
{ ((void(*)(ptr))x)(y);
return 1;
}

int main()
{ H((ptr)P, (ptr)P);
return 0;
}

Yes it does.

_P()
[00001a5e](01) 55 push ebp
[00001a5f](02) 8bec mov ebp,esp
[00001a61](03) 8b4508 mov eax,[ebp+08]
[00001a64](01) 50 push eax // push P
[00001a65](03) 8b4d08 mov ecx,[ebp+08]
[00001a68](01) 51 push ecx // push P
[00001a69](05) e810000000 call 00001a7e // call H
[00001a6e](03) 83c408 add esp,+08
[00001a71](01) 5d pop ebp
[00001a72](01) c3 ret
Size in bytes:(0021) [00001a72]

Now we switch H executing its input to H simulating its input. H
simulates the x86 machine language of its input and sees that its
simulated P is calling H with the same parameters that H was called
with. On this basis H aborts its simulation of P and correctly reports
that P would never reach its final state at 1a72. Because H and P are
both pure functions we know that H(P,P)==0 is computable.

(a) P only halts if it reaches its final state at 1a72.
(b) If H does not abort its simulation of P then P never reaches its
final state at 1a72.
(c) If H aborts its simulation of P then P never reaches its final state
as 1a72.
(d) Because P never halts in all possible cases H(P,P)==0 is always
correct.

The fact that there are no errors in (a)(b)(c) and (d) is a necessary
consequence of (a)(b)(c) conclusively proves that (d) is correct.

Halting problem undecidability and infinitely nested simulation (V2)

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V7 [ pure function ]

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor