Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Everyone's head is a cheap movie show." -- Jeff G. Bone


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V11

SubjectAuthor
o Concise refutation of halting problem proofs V11olcott

1
Concise refutation of halting problem proofs V11

<h-KdneSMqoL9ZxP8nZ2dnUU7-b_NnZ2d@giganews.com>

 copy mid

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

 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!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 12 Nov 2021 17:36:00 -0600
Date: Fri, 12 Nov 2021 17:35: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: Concise refutation of halting problem proofs V11
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <h-KdneSMqoL9ZxP8nZ2dnUU7-b_NnZ2d@giganews.com>
Lines: 72
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-M6IGsUaxRIZg8E4zI/V4L1Tgcm0R8Jee3s+l3o5JXEJyufkg7acd6787eKWBI5jQaVpap8cHQfnvrEE!opNPqg0BkSxl/5qsHMJyaElUlGqfts9DACn6ax7jwMSLCxeb2IQSz7dzYcj5AWoKV+ZwMHvJu7fb!yQ==
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: 3486
 by: olcott - Fri, 12 Nov 2021 23:35 UTC

#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
void P(ptr x)
{ H(x, x);
}

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

It is obvious that whether or not the above code is directly executed or
H performs a pure simulation of its input that the above code specifies
infinite recursion.

If H simulates its input in debug step mode it can correctly abort the
simulation of this input as soon as H sees its simulated P call itself
with the same parameters that it was called with. When it does this it
correctly returns 0 for not halting.

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

No computation halts (even if it stops running) unless it reaches its
final state

Because there is nothing that any 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.

Because the simulated or executed input to every H(P,P) invoked at
machine address 00001a7e with the byte sequence of the machine code of P
as its input never reaches the final address of P at 00001a72 it is
always correct for this H(P,P) to return 0.

All rebuttals must take this form:
Find an invocation of H(P,P) at machine address 00001a7e such that the
simulation or execution of (the exact byte sequence of) P reaches its
final address of 00001a72.

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)

--
Copyright 2021 Pete Olcott

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

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor