Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

The only thing cheaper than hardware is talk.

computers / / Concise refutation of halting problem proofs V33

o Concise refutation of halting problem proofs V33olcott

Subject: Concise refutation of halting problem proofs V33
From: olcott
Newsgroups: comp.theory,, sci.logic, sci.math
Followup: comp.theory
Date: Sat, 27 Nov 2021 14:44 UTC
NNTP-Posting-Date: Sat, 27 Nov 2021 08:44:47 -0600
Date: Sat, 27 Nov 2021 08:44:46 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Newsgroups: comp.theory,,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: (olcott)
Subject: Concise refutation of halting problem proofs V33
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <>
Lines: 76
X-Trace: sv3-w4xci9D06Id2nAsMB2GbpHTYHoYtMQNSuH/TPFOeXdyvzj8HS8xQ8qjDzcQwNC11cX8dOImzI2TTpEJ!mWaVYA0BCj/UJ6F5H+//3QvB1xQINOcjmNvBOq/4EEnBotoV1zVcEtd/FgokESka4oV4InXm6Hku!xA==
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: 3761
View all headers
#include <stdint.h>
#include <stdio.h>
typedef int (*ptr)();

int H(ptr x, ptr y)
   x(y); // direct execution of P(P)
   return 1;

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
int P(ptr x)
   H(x, x);
   return 1; // Give P a last instruction at the "c" level

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

The above program is obviously infinitely recursive. It is self evident that when 0 to ∞ steps of the input to H(P,P) are directly executed or correctly simulated that the input to H(P,P) never reaches its final instruction.

computation that halts a computation halts whenever it enters a final state (Linz:1990:234) thus none of the simulated or executed 0 to ∞ steps of the input to H(P,P) ever halt.

PSR set (pathological self-reference)
H1(P1,P1) Is the above code.
H2(P2,P2) Is the above code where H2 simulates rather than directly executes its input.
H3(P3,P3) Is the execution of N steps of the input of H1(P1,P1).
H4(P4,P4) Is the simulation of N steps of the input of H2(P2,P2).

Every Hn(Px,Py) that returns a value returns 1 except for instances of {H3, H4} that determine whether or not to return {0,1} on the basis of the behavior of their input.

The correct pure simulation of N steps of the input to H(P,P) by H is always a correct halt deciding basis where P has reached its final state or H has correctly detected that P would never reach its final state.

The point in the sequence of N steps where the execution trace of the simulation of P shows that P is about to call H(P,P) again with the same input that H was called with provides conclusive proof that P would be infinitely recursive unless H aborted its simulation.
*In this H4(P4,P4)==0 computation P4 is dependent on H4 altering the behavior of P4.*

When directly executed P(P) calls H(P,P) and the simulated P(P) reaches the point where it would call H(P,P) with the same parameters that H was called with H returns 0 to this directly executed P.
*In this H1(P4,P4)==1 computation P4 is independent of H1.*

H is a computable function that accepts or rejects inputs in its domain on the basis that these inputs specify a sequence of configurations that reach their final state.

Halting problem undecidability and infinitely nested simulation (V2)

Copyright 2021 Pete Olcott

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

rocksolid light 0.7.2