Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

An algorithm must be seen to be believed. -- D. E. Knuth


tech / sci.math / Halting problem undecidability and infinitely nested simulation(V16a)

SubjectAuthor
o Halting problem undecidability and infinitely nested simulation(V16a)olcott

1
Halting problem undecidability and infinitely nested simulation(V16a)

<s9dgp2$kq5$1@dont-email.me>

  copy mid

https://www.novabbs.com/tech/article-flat.php?id=61609&group=sci.math#61609

  copy link   Newsgroups: comp.theory comp.software-eng comp.ai.philosophy sci.math
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory,comp.software-eng,comp.ai.philosophy,sci.math
Subject: Halting problem undecidability and infinitely nested simulation(V16a)
Date: Fri, 4 Jun 2021 10:27:21 -0500
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <s9dgp2$kq5$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 4 Jun 2021 15:27:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="7079525da0a88a7b737317f09699dfdc";
logging-data="21317"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+uQNywrjmQ37T3+FOAjRiP"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.11.0
Cancel-Lock: sha1:KJtz/rTPq2TZKMGze8aXvjctDAI=
Content-Language: en-US
X-Mozilla-News-Host: news://news.eternal-september.org:119
 by: olcott - Fri, 4 Jun 2021 15:27 UTC

int Simulate(u32 P, u32 I)
{ ((void(*)(u32))P)(I);
return 1;
}

// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P)
{ // Linz H as a simulating partial halt decider
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
}

void H_Hat2(u32 P)
{ u32 Input_Halts = Simulate(P, P);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{ H_Hat2((u32)H_Hat2);
H_Hat((u32)H_Hat);
}

Anyone that knows C programming very well will know that line 1 of main
won't halt and 2 of main will only halt if simulating partial halt
decider H stops simulating H_Hat(). A simulating halt decider that never
stops simulating its input is simply a simulator on this input.

When we know that the UTM simulation of TM Description P on input I
would never halt we know that the execution of TM P(I) would never halt.

On this basis we know that any computation that must have its simulation
aborted to prevent its otherwise infinite execution is correctly
rejected as non-halting.

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.

Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor