Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

In specifications, Murphy's Law supersedes Ohm's.


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V21 [ precisely defined sets ]

SubjectAuthor
o Concise refutation of halting problem proofs V21 [ precisely definedolcott

1
Concise refutation of halting problem proofs V21 [ precisely defined sets ]

<peOdndvm_ZK9rgT8nZ2dnUU7-dvNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Followup: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 20 Nov 2021 11:40:48 -0600
Date: Sat, 20 Nov 2021 11:40:47 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.3.2
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V21 [ precisely defined
sets ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <peOdndvm_ZK9rgT8nZ2dnUU7-dvNnZ2d@giganews.com>
Lines: 64
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-RVHpilv/YdtR7x38cVng8FEmDbplqzZAy/+xMMEdmehwxMuOLeWTnzkFKCxUX9ueUqIo3XGIcNH+fl4!wiLHhbvb1DQ4Y8YbFr0ac0X29RDGgOdtlYPqYJTIlZXO5ZlYZoWPBbqnGgVQXBKC3ypszz7s6yZK!cg==
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: 3188
 by: olcott - Sat, 20 Nov 2021 17:40 UTC

#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
For every possible 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.

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
subset the input to H(P,P) never halts and H(P,P) halts.

When int main(void) { P(P); } is invoked on H/P elements of the above
PSR subset, then we have a cases where the input to H(P,P) never halts
and P(P) halts.

The above cases conclusively prove that when the input to H(P,P) never
halts and the same P(P) does halt that this does not form any
contradiction.

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 function that correctly maps every element of its domain to {0,1}
on the basis of whether or not these elements reach their final state
and halt. On this basis H is a halt decider.

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.

--
Copyright 2021 Pete Olcott

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

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor