Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

"But what we need to know is, do people want nasally-insertable computers?"


computers / comp.ai.philosophy / Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]

SubjectAuthor
o Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]olcott

1
Subject: Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Fri, 12 Nov 2021 18:48 UTC
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!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: Fri, 12 Nov 2021 12:49:00 -0600
Date: Fri, 12 Nov 2021 12:48:59 -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,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <OoCdnb0IbOuBKhP8nZ2dnUU7-WmdnZ2d@giganews.com>
Lines: 84
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-xcupQZK2CBLgRt02MWs99KpN/DyUE6wL4Y3ABmfTsAjCzR+7tPU5ey6oyLqVucXBtZuh9l5NBa4vxj5!78G4t/NnlwnV3CmeO5HLgHpZKtA9BLgOiayxVQsX+xqziQvYa7jNVsksFTrSozrcmMmHF2+k9zW1!8g==
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: 3412
View all headers
Giving credit where credit is due
Ben posted these very excellent improvements
to my initial syntax in comp.lang.c
On 11/11/2021 2:31 PM, Ben Bacarisse wrote:

#include <stdint.h>
typedef void (*ptr)();

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

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P (see below)
void P(ptr x)
{
   H(x, x);
}

int main(void)
{
   H(P, P);
}

It is obvious that the direct execution of the above code never halts because it is infinitely recursive. It is equally obvious that when H performs a correct pure simulation of its input (instead of directly executing it) that its input never halts.

_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]

Because there is nothing that H can possibly do to cause or enable P to reach its final state at 1a72 we correctly conclude that the input to H(P,P) never halts.









// Simplified Linz(1990) Ĥ and Strachey(1965) P
void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

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

Strachey, C 1965.  An impossible program The Computer Journal, Volume 7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)

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



--
Copyright 2021 Pete Olcott

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


1
rocksolid light 0.7.2
clearneti2ptor