Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

MS-DOS, you can't live with it, you can live without it. -- from Lars Wirzenius' .sig


programming / comp.lang.asm.x86 / Re: It is known that a correct halt decider must return false (in

SubjectAuthor
o Re: It is known that a correct halt decider must return false (inolcott

1
Subject: Re: It is known that a correct halt decider must return false (in
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Fri, 27 Nov 2020 02:55 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!suck
Funky-Path: eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: NoO...@nospicedham.NoWhere.com (olcott)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.asm.x86
Subject: Re: It is known that a correct halt decider must return false (in
Date: Thu, 26 Nov 2020 20:55:01 -0600
Organization: A noiseless patient Spider
Lines: 192
Approved: fbkotler@myfairpoint.net - comp.lang.asm.x86 moderation team.
Message-ID: <KIOdnfRX6Okd913CnZ2dnUU7-RnNnZ2d@giganews.com>
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<p7SdnUWV3YT3rCLCnZ2dnUU7-KnNnZ2d@giganews.com>
<G9ednQR63dvHUyLCnZ2dnUU78QnNnZ2d@brightview.co.uk>
<PfmdnUdnnqhYTyLCnZ2dnUU7-c3NnZ2d@giganews.com>
<U8ednVm41KijRSLCnZ2dnUU78c_NnZ2d@brightview.co.uk>
<746dnWToYoc6RyLCnZ2dnUU7-N_NnZ2d@giganews.com>
<_eCdnSZdT4qMfCLCnZ2dnUU78I_NnZ2d@brightview.co.uk>
<Q9ydnbikEfeweiLCnZ2dnUU7-R_NnZ2d@giganews.com>
<KJidnf6fW8cunl3CnZ2dnUU78aGdnZ2d@brightview.co.uk>
<7qWdnVHa8r1DlV3CnZ2dnUU7-VHNnZ2d@giganews.com>
<WdOdnXv5dK9hkl3CnZ2dnUU78X3NnZ2d@brightview.co.uk>
<edqdnc-pcMl-jV3CnZ2dnUU7-QGdnZ2d@giganews.com>
<LY-dnbwpXbztjl3CnZ2dnUU78XfNnZ2d@brightview.co.uk>
<yrKdnbIeAtuZiF3CnZ2dnUU7-TGdnZ2d@giganews.com>
<vIGdnXPT4om4h13CnZ2dnUU78TXNnZ2d@brightview.co.uk>
<OPGdnZp2OtSrhl3CnZ2dnUU7-L3NnZ2d@giganews.com>
<SeWdnW8CLNAlgF3CnZ2dnUU78SmdnZ2d@brightview.co.uk>
<6P6dnY8rh70qv13CnZ2dnUU7-Y_NnZ2d@giganews.com>
<sKOdndkyD96Ex13CnZ2dnUU78a3NnZ2d@brightview.co.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Funky-Injection-Info: reader02.eternal-september.org; posting-host="44511580e44866a42e9abe3bfc3f51b7";
logging-data="2332"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+KuXIBp1GbPBCtXzvZVzMuCnRy8D83rlw="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
Cancel-Lock: sha1:bEeGrCj5U30icROajpsDIhhB+ss=
Funky-Xref: reader02.eternal-september.org comp.theory:34209 comp.ai.philosophy:30298 comp.lang.asm.x86:12357
View all headers
On 11/26/2020 7:44 PM, Mike Terry wrote:
On 26/11/2020 21:48, olcott wrote:
On 11/26/2020 3:27 PM, Mike Terry wrote:
On 26/11/2020 21:16, olcott wrote:
On 11/26/2020 3:12 PM, Mike Terry wrote:
On 26/11/2020 20:50, olcott wrote:
On 11/26/2020 2:43 PM, Mike Terry wrote:
On 26/11/2020 20:32, olcott wrote:
On 11/26/2020 2:28 PM, Mike Terry wrote:
<.. snip ..>

That's not the actual problem at hand.  The problem at hand is
whether
your test within Halts:

TEST:     [I've gone back to your own description.]

(1) Keep a global execution trace of every line of user code.

(2) Whenever any instruction is executed see if it is a function
call.

(3) If it is a function call find the prior call to this same
function
from the current machine address (if any) searching backward
through
the global execution trace and counting conditional branch
instructions.

(4) If found and conditional-branch-count == zero terminate the
input.

actually "works".  (i.e. only non-halting inputs are matched.)

Your "global execution trace" contain a mixture of x86 program
steps
AT DIFFERENT EMULATION LEVELS.

Not really they all call the same global DebugTrace() / Halts().


But your Halts() emulates its input (P,I), and then calls within the
EMULATED (P,I) call Halts, so there are calls to Halts at different
emulation levels.


Mike.



That could simply be thought of as recursive invocation

A kind of recursion, sure.  We can distinguish the following kinds:

-  Recursive CALL
    This is where function A /directly calls/ function A.  Or
    we could extend it to cover A calls B which calls A again, etc.

-  Recursive EMULATION.
    This is where function A /EMULATES/ function A.  Or
    we could extend it to cover A calls B which EMULATES A again, etc.

that is
functionally equivalent to this:

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

void H_Hat(u32 P)
{
  u32 Aborted = DebugTrace(P, P);
  if (Aborted)
    HALT
  else
    HERE: goto HERE;
}

int main()
{
  u32 P = (u32)H_Hat;
  DebugTrace(P, P);
  HALT;
}

No, that is RECURSIVE CALL, no emulation.  The behaviour regarding
infinite recursion is not the same, as I've been telling you.

So far, all your explanations have only applied to a recursive call
scenario....

Mike.


It is computationally equivalent.

What about the price of tea in China?
Maybe we should factor that in too.

It is not computationally equivalent, because in the case of recursive
EMULATION, the outer emulation code has the ability to monitor and
abort the inner emulations.  This is not possible in the case of
recursive CALL.

Mike.


Which you already agreed is only a difference in emulator behavior:
DebugTrace() or Halts() not a difference in emulated behavior: H_Hat().

You have already shown you don't understand what I said, so it's really pointless harping back to that.

What I said is that the SAME CALCULATION "comes out the same under different emulators".

OK What are you saying here is "the SAME CALCULATION"?  And what are the two emulators? 


void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}



void H_Hat(u32 P)
{
   u32 Aborted = Halts(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   Halts(P, P);
   HALT;
}


These two calculations are verifiably identical until the second one stops simulating H_Hat
(a) DebugTrace/H_Hat
(b) Halts/H_Hat


Don't just say DebugTrace() and Halts() because you've had so many versions of everything I haven't a clue which one you mean now.  Probably by now you can just cut and paste the code (or at least the description).

DebugTrace() is identical to Halts() except that Halts stops simulating its input and DebugTrace() does not stop simulating its input.


If there is not a difference in emulated behavior then the decision of
Halts() to abort H_Hat() is examining the exact same execution trace of
H_Hat provided by DebugTrace().

But IS there a difference in emulated behaviour? >
Hmm, and suppose there is no difference, because you really do have a single calculation being emulated by two emulators - why would that mean your TEST is sound?  (Neither of us wants to go down a blind alley here...)

Mike.




--
Copyright 2020 Pete Olcott

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



1
rocksolid light 0.7.2
clearneti2ptor