Validating the notion of a simulating halt decider

From	olcott <none-ya@beez-waxes.com>
Newsgroups	comp.theory, sci.logic, comp.lang.c++
Subject	Validating the notion of a simulating halt decider
Followup-To	comp.theory
Date	2022-11-10 13:31 -0600
Organization	Aioe.org NNTP Server
Message-ID	<tkjjj2$1ktn$1@gioia.aioe.org> (permalink)

Cross-posted to 3 groups.

Followups directed to: comp.theory

Show all headers | View raw

MIT Professor Michael Sipser has agreed that the following verbatim 
paragraph is correct (he has not agreed to anything else):

If simulating halt decider H correctly simulates its input D until H 
correctly determines that its simulated D would never stop running 
unless aborted then H can abort its simulation of D and correctly report 
that D specifies a non-halting sequence of configurations.

void D(void (*x)())
{
   int Halt_Status = H(x, x);
   if (Halt_Status)
     HERE: goto HERE;
   return;
}

int main()
{
   Output("Input_Halts = ", H(D, D));
}

Unless one rejects the notion of a universal Turing machine (UTM) then 
they already know that H can base its halt status decision on the 
behavior of D correctly simulated by H.

That theory of computation textbooks do not bother to mention this is 
only because they never considered the notion of a simulating halt decider.

void D(void (*x)())
{
   H(x, x);
}

It is dead obvious that (ignoring stack overflow) D correctly simulated 
by H will never stop running unless H aborts its simulation of D.


-- 
Copyright 2022 Pete Olcott

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

Back to comp.lang.c++ | Previous | Next | Find similar | Unroll thread

Thread

Validating the notion of a simulating halt decider olcott <none-ya@beez-waxes.com> - 2022-11-10 13:31 -0600

csiph-web