Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

COBOL is for morons. -- E. W. Dijkstra

computers / / Concise refutation of halting problem proofs V26 [ defined sets ]

o Concise refutation of halting problem proofs V26 [ defined sets ]olcott

Subject: Concise refutation of halting problem proofs V26 [ defined sets ]
From: olcott
Newsgroups: comp.theory,, sci.math, sci.logic
Followup: comp.theory
Date: Mon, 22 Nov 2021 19:29 UTC
NNTP-Posting-Date: Mon, 22 Nov 2021 13:29:25 -0600
Date: Mon, 22 Nov 2021 13:29:24 -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.math,sci.logic
Content-Language: en-US
Followup-To: comp.theory
From: (olcott)
Subject: Concise refutation of halting problem proofs V26 [ defined sets ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <>
Lines: 73
X-Trace: sv3-zBU233ynsIwyaFPP+AYz+HujZsO56IN2BH1dSmtE2hSK48ULq3I9HyhbGP+Qz4IjtbdeqHBJyaZBxU9!6efRHOd0tcgf+WxzuOPV1CwR3o8Niy9uDmIodNhYEiIJe/l+dCfq4Wb00Qp5nODCGrcdaU87XAMi!cQ==
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: 3613
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);

Computation that halts
a computation is said to halt whenever it enters a final state. (Linz:1990:234)

[PSR_set] Combinations of H/P having pathological self-reference
Every H of H(P,P) invoked from main() where P(P) calls this same H(P,P) and H simulates or executes its input and aborts or does not abort its input P never reaches its last instruction.
∀H ∊ PSR_set ∀P ∊ PSR_set (Input_Never_Halts(H(P,P)))

[PSR_subset] Because we know that the input to H(P,P) never halts for the whole PSR_set and a subset of these H/P combinations aborts the execution or simulation of its input then we know that for this entire PSR subset the input to H(P,P) never halts and H(P,P) halts.
PSR_Subset ⊆ PSR_set ∀H ∊ PSR_Subset (Halts(H(P,P)))

[PSR_subset + P(P)_set] Appending the computation int main(void) { P(P); } to the PSR_subset we derive another set having the exact same H/P pairs. In this set the input to H(P,P) never halts and P(P) halts. This proves that no contradiction is formed.
∃H ∊ [PSR_subset + P(P)_set]    ∃P ∊ [PSR_subset + P(P)_set]
((Input_Never_Halts(H(P,P))) ∧ Halts(P(P)))

[Decidable_PSR_subset] The subset of the PSR_subset where H returns 0 on the basis that H correctly detects that P specifies infinite recursion defines the decidable domain of function H.

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.
H is a correct decider and H has a correct halt deciding basis.

The above H could detect that its simulated P is calling H(P,P) with the same parameters that it was called with, thus specifying infinite recursion.

See Page 3 of:
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