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 / / Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]

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

Subject: Re: Concise refutation of halting problem proofs V9 [ Simplest one yet ]
From: olcott
Newsgroups: comp.theory,, sci.logic, sci.math
Followup: comp.theory
Date: Fri, 12 Nov 2021 18:48 UTC
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,,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: (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: <>
Lines: 84
X-Trace: sv3-xcupQZK2CBLgRt02MWs99KpN/DyUE6wL4Y3ABmfTsAjCzR+7tPU5ey6oyLqVucXBtZuh9l5NBa4vxj5!78G4t/NnlwnV3CmeO5HLgHpZKtA9BLgOiayxVQsX+xqziQvYa7jNVsksFTrSozrcmMmHF2+k9zW1!8g==
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)
   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.

[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

Strachey, C 1965.  An impossible program The Computer Journal, Volume 7, Issue 4, January 1965, Page 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

rocksolid light 0.7.2