Message-ID:

"So why don't you make like a tree, and get outta here." -- Biff in "Back to the Future"

devel / comp.theory / Halting problem undecidability and infinitely nested simulation(V16)

Halting problem undecidability and infinitely nested simulation(V16)

<gOadndYr9skG3yf9nZ2dnUU7-VPNnZ2d@giganews.com>

https://www.novabbs.com/devel/article-flat.php?id=16326&group=comp.theory#16326

Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!peer01.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 04 Jun 2021 10:11:23 -0500
Newsgroups: comp.theory
X-Mozilla-News-Host: news://news.giganews.com:119
From: NoO...@NoWhere.com (olcott)
Subject: Halting problem undecidability and infinitely nested simulation(V16)
Date: Fri, 4 Jun 2021 10:11:14 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.11.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <gOadndYr9skG3yf9nZ2dnUU7-VPNnZ2d@giganews.com>
Lines: 52
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-mtA4KuMVzO/FvSovVTLceU5/ttUXUn+jCNnL72tQEecIJx+DRqMy2Klwp31UhyA2tcsf3M6FHXEgWY2!2eGrgd6Xio50MxqPIuqTLeWLji1x6tEF8pCr4n0bfjC2kNNc+jUXShSlMTDppdAxT18MZbb0EYI=
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: 2666
X-Received-Bytes: 2876

by: olcott - Fri, 4 Jun 2021 15:11 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()
{ Simulate((u32)H_Hat2, (u32)H_Hat2);
Simulate((u32)H_Hat, (u32)H_Hat);
}

Anyone that knows programming in C 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

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

Subject	Author
Halting problem undecidability and infinitely nested simulation(V16)	olcott