Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Are we running light with overbyte?


computers / comp.ai.philosophy / Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language)

SubjectAuthor
* It is known that a correct halt decider must return false (in thisolcott
+* Re: It is known that a correct halt decider must return false (in this casolcott
|+* Re: It is known that a correct halt decider must return false (inMike Terry
||`* Re: It is known that a correct halt decider must return false (inolcott
|| +* Re: It is known that a correct halt decider must return false (inolcott
|| |`* Re: It is known that a correct halt decider must return false (in this casolcott
|| | `- Re: It is known that a correct halt decider must return false (in this casolcott
|| +* Re: It is known that a correct halt decider must return false (inolcott
|| |`- Re: It is known that a correct halt decider must return false (in this casolcott
|| `- Re: It is known that a correct halt decider must return false (inolcott
|`- Re: It is known that a correct halt decider must return false (inolcott
`* Re: It is known that a correct halt decider must return false (inolcott
 +- Re: It is known that a correct halt decider must return false (inolcott
 `* Re: It is known that a correct halt decider must return false (inolcott
  +* Re: It is known that a correct halt decider must return false (in this casolcott
  |+* Re: It is known that a correct halt decider must return false (in this casolcott
  ||`* Re: It is known that a correct halt decider must return false (inolcott
  || +- Re: It is known that a correct halt decider must return false (in this casolcott
  || +* Re: It is known that a correct halt decider must return false (in this casolcott
  || |`- Re: It is known that a correct halt decider must return false (in this casolcott
  || `* Re: It is known that a correct halt decider must return false (in this casolcott
  ||  +- Re: It is known that a correct halt decider must return false (in this casolcott
  ||  `- Re: It is known that a correct halt decider must return false (in this casolcott
  |`* Re: It is known that a correct halt decider must return false (inolcott
  | `* Re: It is known that a correct halt decider must return false (inolcott
  |  `* Re: It is known that a correct halt decider must return false (inolcott
  |   `* Re: It is known that a correct halt decider must return false (inolcott
  |    `* Re: It is known that a correct halt decider must return false (in this casolcott
  |     `* Re: It is known that a correct halt decider must return false (inolcott
  |      `* Re: It is known that a correct halt decider must return false (inolcott
  |       `* Re: It is known that a correct halt decider must return false (inolcott
  |        +* Re: It is known that a correct halt decider must return false (inolcott
  |        |`* Re: It is known that a correct halt decider must return false (inolcott
  |        | `* Re: It is known that a correct halt decider must return false (inolcott
  |        |  +- Re: It is known that a correct halt decider must return false (inolcott
  |        |  `* Re: It is known that a correct halt decider must return false (inolcott
  |        |   +* Re: It is known that a correct halt decider must return false (in this casolcott
  |        |   |`* Re: It is known that a correct halt decider must return false (inolcott
  |        |   | `* Re: It is known that a correct halt decider must return false (inolcott
  |        |   |  `* Re: It is known that a correct halt decider must return false (inolcott
  |        |   |   `- Re: It is known that a correct halt decider must return falseolcott
  |        |   +* Re: It is known that a correct halt decider must return false (inolcott
  |        |   |+- Re: It is known that a correct halt decider must return false (inolcott
  |        |   |`* Re: It is known that a correct halt decider must return false (in this casolcott
  |        |   | +* Re: It is known that a correct halt decider must return false (inolcott
  |        |   | |`* Re: It is known that a correct halt decider must return false (inolcott
  |        |   | | +- Re: It is known that a correct halt decider must return false (inolcott
  |        |   | | `- Re: It is known that a correct halt decider must return false (in this casolcott
  |        |   | `* Re: It is known that a correct halt decider must return false (inolcott
  |        |   |  `* Re: It is known that a correct halt decider must return false (in this casolcott
  |        |   |   `* Re: It is known that a correct halt decider must return false (inMr Flibble
  |        |   |    `- Re: It is known that a correct halt decider must return false (inolcott
  |        |   `- Re: It is known that a correct halt decider must return false (inolcott
  |        `* Re: _It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_caolcott
  |         `* Re: _It_is_known_that_a_correct_halt_decider_must_returnolcott
  |          `* Re: _It_is_known_that_a_correct_halt_decider_must_returnolcott
  |           +* Re: _It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_caolcott
  |           |+- Re: _It_is_known_that_a_correct_halt_decider_must_returnJeff Barnett
  |           |`- Re: It is known that a correct halt decider must return false (inolcott
  |           `- Re: _It_is_known_that_a_correct_halt_decider_must_returnolcott
  `* Re: It is known that a correct halt decider must return false (in this casolcott
   `* Re: It is known that a correct halt decider must return false (inolcott
    +* Re: It is known that a correct halt decider must return false (This is theolcott
    |`* Re: It is known that a correct halt decider must return false (Thisolcott
    | `* Re: It is known that a correct halt decider must return false (Thisolcott
    |  `- Re: It is known that a correct halt decider must return false (Thisolcott
    `* Re: It is known that a correct halt decider must return false (in this casolcott
     +* Re: It is known that a correct halt decider must return false (in this casolcott
     |`* Re: It is known that a correct halt decider must return false (in this casolcott
     | `- Re: It is known that a correct halt decider must return false (in this casolcott
     +- Re: It is known that a correct halt decider must return false (inolcott
     `* Re: It is known that a correct halt decider must return false (inolcott
      +- Re: It is known that a correct halt decider must return false (inolcott
      `* Re: It is known that a correct halt decider must return false (inolcott
       `* Re: It is known that a correct halt decider must return false (in this casolcott
        +- Re: It is known that a correct halt decider must return false (inolcott
        +- Re: It is known that a correct halt decider must return false (in this casolcott
        `* Re: It is known that a correct halt decider must return false (inolcott
         +* Re: It is known that a correct halt decider must return false (in this casolcott
         |`* Re: It is known that a correct halt decider must return false (in this casolcott
         | `- Re: It is known that a correct halt decider must return false (in this casolcott
         `- Re: It is known that a correct halt decider must return false (inolcott

Pages:1234
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Thu, 26 Nov 2020 21:48 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!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 26 Nov 2020 15:48:39 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](x86 as a formal language)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
From: NoO...@NoWhere.com (olcott)
Date: Thu, 26 Nov 2020 15:48:45 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <SeWdnW8CLNAlgF3CnZ2dnUU78SmdnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <6P6dnY8rh70qv13CnZ2dnUU7-Y_NnZ2d@giganews.com>
Lines: 621
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-yclK3CrcW6RhShoVBzfdmjL/BaIGLmKcuGLR8WQuQF+Bz2UhYD5CYC4qyApYG2jlI9mOad6zscT9nPF!BkcrvbgdprSi/cndUNr63gnkFaOI+SS39RXGQc3H0GIeA/J7e2cgtTZOiMqFT+O+sj81GPs69fNI!zg==
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: 27218
View all headers
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:
On 26/11/2020 19:58, olcott wrote:
On 11/26/2020 1:36 PM, Mike Terry wrote:
On 26/11/2020 17:34, olcott wrote:
On 11/26/2020 11:08 AM, Mike Terry wrote:
On 26/11/2020 16:41, olcott wrote:
On 11/26/2020 10:30 AM, Mike Terry wrote:
On 26/11/2020 16:07, olcott wrote:
On 11/26/2020 9:48 AM, Mike Terry wrote:
On 26/11/2020 04:39, olcott wrote:
On 11/25/2020 10:27 PM, Mike Terry wrote:
On 26/11/2020 02:14, olcott wrote:
On 11/25/2020 7:38 PM, Mike Terry wrote:
On 26/11/2020 00:51, olcott wrote:
On 11/25/2020 6:33 PM, Mike Terry wrote:
On 25/11/2020 23:47, olcott wrote:
On 11/25/2020 5:31 PM, Mike Terry wrote:
On 25/11/2020 21:55, olcott wrote:
On 11/25/2020 3:25 PM, Mike Terry wrote:
On 25/11/2020 17:21, olcott wrote:
On 11/25/2020 10:45 AM, Mike Terry wrote:
On 24/11/2020 15:41, Mike Terry wrote:
On 24/11/2020 04:18, olcott wrote:
<.. snip ..>

People can eventually look at all of my code
and
the
thousands of
lines
of code of the x86 emulator and they can
look at
the
hundreds of
pages
out output. It all boils down to this:

The simulator merely watches its simulation of
the
following
instructions until it sees a function call
to 377
from
503
the
second
time with no JCC (Jump-Condition_Code)
in-between.


I have told you many times that your test
must be
UNSOUND.
You
have
never responded to this, so I've assumed you
don't
really
know
whether
your test is sound or unsound (or probably, what
that
even
means,
although I've also explained that to you
before).

Now you are getting closer to actually coding
the
test
(which
you
claimed to have "fully coded" two years ago),
you
are
finally
giving
more details.

So...  what do you think.  Is the following
test a
SOUND
test
for
non-halting?

   TEST:  "monitor the simulation until there
is a
function
           call to 377 from 503 a second time,
with no
conditional
           branch inbetween"

Putting it more directly - if some calculation
P(I)
triggers the
TEST
(so it contains two calls from 377 from 503,
with no
conditional
branch
inbetween), does this genuinely imply that the
calculation
will
never
halt?

Bear in mind that the two calls in question
do not
necessarily
occur in
the same "virtual address space", that is to say
the two
calls can
[and
in the case of T_Hat(T_Hat) *do* ] occur at
/different
levels of
emulation/.   [Your trace notation obscures this
simple
fact,
making
everything appear to be in one single virtual
process,
when
it's
not.]

What do you think?  This seems to be your
primary
intuition
that
triggered all this "refuting" activity, BUT
IS IT
ACTUALLY
CORRECT?

Of course, you will say "All my intuitions are
correct by
definition -
I'm never wrong" but that doesn't make it
true!  :)

Is TEST *SOUND* ?


Noted: still no response to this basic question.

Mike.

<.. snip non-response to question ..>

I'm not sure if that non-response was
deliberate.  I
didn't ask
whether one specified implementation of [whatever]
exhibits
infinite
recursion!

In case it was just a misreading, here is the
question
again.


   So...  what do you think.  Is the following
test a
SOUND
test
for
   non-halting?

      TEST:  "monitor the simulation until there
is a
function
              call to 377 from 503 a second time,
with no
conditional
              branch in-between"

It is much more generic than that.
(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.

Copyright 2020 Pete Olcott (I just wrote that
algorithm
right
now).

OK, I always imagined the test would be more general
than
just
checking specifically for calls to 377 from 503.
:)  No
problem on
that front.

I'm thinking this is probably the basis of your
initial
intuition
that
you could actually detect and handle the type of
recursion in
your
fledgeling (at that time) halt decider design.

It is good that you've clarified the test, and yet it
seems
you're
reluctant to plainly say that you believe the test
works!

logical necessity speaks for itself it doesn't need me
for a
cheerleader.


LOL.  I knew you'd do something like that.

OK, so you are saying that if your test detects the
behaviour
described, then it's a "logical necessity" that the
input
being
examined is non-halting?

Yes that is what I am saying.

There - that wasn't so bad, was it?  :)


Can you find a counter-example?

Well, if it's a logical necessity I'm in for a hard
time on
that
one...

But here's the point:  logical necessity absolutely
/does/
need a
cheerleader!  Loads of things are "logically
necessary" in
that
they
must logically be true, and yet they are not /obviously/
true.
That's
why we have proofs.

This would be one of those scenarios, where even if your
claim is
correct, it's not trivially obvious that it's correct,
right?

Here is what we're saying:

TEST:
    If a calculation P(I) has a trace of steps
    (s0, s1, s2, s3, .....) and there are two steps s_i
    and s_j, such that si and sj are both unconditional
    branches from A to B, and none of the steps
in-between
    s_i and s_j are conditional branches, THEN
calculation
    P(I) never halts.

Well that's certainly not a "trivial restatement of word
meanings" or
similar, and so is not seen to correct just on a casual
glance.

So obviously where I'm going is : do you have a proof of
this?

Now I know you're not one for proofs, and maybe during
the
course of
discussion such a proof will fall out (provided the
underlying
logic
is correct...)

So to start with, perhaps you can just give your thinking
as to
/why/
you believe it to be logically necessary?  [You clearly
didn't
wake up
one day and think "hey, what about TEST - oh! it's a
logical
necessity, that's handy - I can use it in my halt
decider!".
There
was something that led you to consider TEST, and having
considered
it,
you decided for whatever reason it was true...]


Mike.


Let's look at it a little simpler:
HERE:  // current location
  Instructions that cannot possibly exit a loop
THERE: goto HERE;

Can you see how this definitely loops?

I can - and if this was relevant there would be a straight
forward
proof that such code loops.

But this isn't like the scenario you are dealing with AT
ALL!
What
you are showing here is a kind of "in-process" loop
detection.
What
you need is some kind of recursive EMULATION detection.
(Emulation
works differently in this respect.)

I'm pretty sure I explained the difference in a post a
couple of
weeks
ago but you never responded.

We are trying to determine whether or not a specific
sequence
of x86
machine code bytes specify an infinite loop as if this
machine
code
was
a mathematical formalism.

The only thing that matters is: WHAT DO THE BYTES THEMSELVES
SAY?


Well, I understand that the code bytes that you presented, if
executed
by a processor within one single logical thread of execution,
would
never terminate - there is an obvious loop.

But that's ignoring the issue of RECURSION, where
behaviour is
not so
simple.  So what's the next step?  (So far what you've said
is no
justification for the RECUSION scenario, which is what you
TEST is
concerned with.)

Mike.


The sequences of instructions from HERE to THERE and HERE to
HERE
are
from actual execution traces. The x86 emulator screens out all
dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

To form a mathematical proof on the basis of the x86 language
being
construed as a formal language we only have to derive the
complete
list
of every instruction that can possibly exit the above loop
and if
there
are none of these between the labels HERE and THERE then we
know
that
the loop is infinite.

Like I said, that is ok for a "contiguous thread of execution",
i.e.
if an x86 processor starts at HERE, and then steps its
execution,
executing the instructions, then the processor will go round
and
round
the loop. The proof is easy.



Click here to read the complete article
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Thu, 26 Nov 2020 22:05 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 26 Nov 2020 16:05:44 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](x86 as a formal language)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk>
<NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Thu, 26 Nov 2020 16:05:50 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
Lines: 120
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-OOnIf1EBW4T+9g5hUB4xhY5ZLQE01+iSid4hcuM6PfC95O2gQN01tBqTqx4St6qrdUsNiJb/uvDlddk!kJP6Zmcd6uU+/8car85Fiwvx7+zJrGWvDnQSnTCfRFwni6tV+SOuswd5Pv/dLLWsgVEN8nhysjjs!Dg==
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: 6661
View all headers
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your 'trace' of
execution NEEDS to include, or at least acknowledge the operation of the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least the
fact that is didn't abort / did abort indication (with an indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break out
of this infinite recursion knows the infinite recursion has been detected.


WRONG.  I keep telling you this, and you just say "it's right, it's right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same emulation level.  It is not the same as "recursive CALL" where a direct branch is made.  When A begins emulating B, you generate trace entries for B, but A is still executing - it is monitoring B, and may decide to abort B for whatever reason.  This is the key difference between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete list
of every instruction that can possibly exit the above loop and if there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you have some further argument to present.


None of any of this makes any difference to the correctness of the halting decision which is made on the basis of the global execution trace.

It used to be the case that the inner invocation did not see as much of the execution trace as the outer invocation thus the outer invocation was able to decide to abort sooner than the inner one. This is no longer the case. The inner invocation can see everything in the whole invocation sequence long before it was ever invoked.


--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Thu, 26 Nov 2020 23:01 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 26 Nov 2020 17:01:16 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](x86 as a formal language)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk>
<NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<RhWvH.11062$lP1.8733@fx37.iad>
From: NoO...@NoWhere.com (olcott)
Date: Thu, 26 Nov 2020 17:01:22 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <RhWvH.11062$lP1.8733@fx37.iad>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <BuSdneS69aMhrl3CnZ2dnUU7-bXNnZ2d@giganews.com>
Lines: 63
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vv2u06yTpDxoyF+/H0vfxWKS59Z+kX6tnKLXIEFRjuW4d1m1V8+FyoBerrJMJuQLGIylKPLgeVVs4VQ!uCoJxuolAhcq7UZ4h7u6US9erZn3HVzqjdiMjhx+tQ1s5r0Y0dXbxZwrEh9Mz+jy1X+si9zHx5/O!ow==
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: 4249
View all headers
On 11/26/2020 4:49 PM, Richard Damon wrote:
On 11/26/20 4:31 PM, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your 'trace' of
execution NEEDS to include, or at least acknowledge the operation of the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

But it creates it. H_Hat in its basic definition is NOT recursiove, it
is self-referential. It is only the fact that your particular Halt
decider works by pure execution that causes ANY recursion to occur, let
alone the infinite recursion that it needs to fix itself.

Any input (TMD / DATA) that would never halt unless its (UTM) stopped simulating it expresses behavior that is not halting behavior.

When Halts() simulates its input (playing the exact same role as the above UTM) then any "not halting" decision that it makes according to the above criteria would be necessarily correct.

Halts(H_Hat, H_Hat) is such a "not halting" decision.



--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](x86 as a formal language)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 03:04 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!aioe.org!peer02.ams4!peer.am4.highwinds-media.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!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 26 Nov 2020 21:04:28 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](x86 as a formal language)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Thu, 26 Nov 2020 21:04:34 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <oKidnXVHj4Eh8V3CnZ2dnUU7-TnNnZ2d@giganews.com>
Lines: 164
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-O4gWGb0bCU29EK+9Xhf7vNn3eRR5ZZoUPPUHDn0TQ4IDpqdiaF9LxhhrlLGzjdxSf1tSpq0KQtrts3L!8AfU/eEF/0eN+ele7gi4ab5/hhkBJmbrdZ9w/rfBwFnb4HgR2eLp8bCr4OT3OP1e/3wBSmkr4ywU!Yg==
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: 8503
X-Received-Bytes: 8715
X-Received-Body-CRC: 2974638916
View all headers
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least the
fact that is didn't abort / did abort indication (with an indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete list
of every instruction that can possibly exit the above loop and if there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an outer emulation CAN abort an inner emulation.  If you spot your "pattern of behaviour" it may not mean infinite recursion, because the breaking of the recursion is LATER ON, AFTER the block of code you've found, and the breaking occurs at some outer level.

If your TEST is unsound, that means you can abort a calculation on the grounds that TEST matched, and yet the calculation in fact halts.

So of course it all has an impact.


It used to be the case that the inner invocation did not see as much of
the execution trace as the outer invocation thus the outer invocation
was able to decide to abort sooner than the inner one. This is no longer
the case. The inner invocation can see everything in the whole
invocation sequence long before it was ever invoked.

Well, that would seem to be making your job of refuting Linz proof even harder, since now your computing environment doesn't directly match up with the TM computing model, making it harder to faithfully translate to-and-fro between Linz proof concepts like H, H^ and /your/ constructs.   Just saying "my H is like Linz's H and my H_Hat is like Linz's H^" won't cut it.  (But that's the sort of thing you'd try, no doubt.) Hehe, let's here the one about TM-equivalant computations!


Mike.


If I say that my car will start when I turn on the ignition then we have 100% infallible proof that I was right when I turn on the ignition and my car starts.

If Halts says that H_Hat will never stop unless it stops emulating it and H_Hat never stops when Halts does not stop emulating it then we have 100% infallible proof Halts was correct.

I see no possible way that anyone can disagree with this and be sincere.




--
Copyright 2020 Pete Olcott

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


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



Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 15:23 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!aioe.org!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 09:22:54 -0600
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk> <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> <MUUvH.221490$gR8.150244@fx45.iad> <epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com> <NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk> <VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com> <BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 09:23:01 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
Lines: 138
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-KIXjJ0uDZjcS6dUposUwmjlx/byySGh6MOhInUD1BH9qToCbVA+PlyGkPauh6alcRT4NGlOwl/eVH9U!gEjJlEOyExY4e9o0tVXtAwZ3QX05ne9DplIROCjRFAYK4H3Y4ZY+2045jL5KNe/CTLHiycD19+Vx!wA==
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: 7328
X-Received-Bytes: 7486
X-Received-Body-CRC: 1582612969
View all headers
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least the
fact that is didn't abort / did abort indication (with an indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete list
of every instruction that can possibly exit the above loop and if there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an

If you understand the basic principle that a TMD simulated by a UTM is computationally equivalent to the direct execution of a TM then you would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the actual computation.

Because of this I simply screen out all of the emulation instructions and only keep track of the emulated instructions. This reduces a 200 page execution trace down to one half of one page. (25 text lines).



--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 16:43 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 10:43:09 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](line-of-demarcation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<0P9wH.143428$xe4.139914@fx41.iad>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 10:43:05 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <0P9wH.143428$xe4.139914@fx41.iad>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Message-ID: <EqqdnZ8_5PAAsVzCnZ2dnUU7-Q3NnZ2d@giganews.com>
Lines: 48
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-UyL24+8ugJEfkOgek3BcmNdh1OxpS+AOTWloirNDJAlsqmIjEWv7kA/g2JMda8JM2eFGD0EopJGXGpG!WnX3wfQ66V5JAAQl6pHQgsZLhxncj70kCt0LKB0vh0QZ9YMhDTuMLYQXcrq/BA9ZfRzuzAPxJT/j!rw==
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: 4197
View all headers
On 11/27/2020 10:28 AM, Richard Damon wrote:
On 11/27/20 10:23 AM, olcott wrote:

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

Because of this I simply screen out all of the emulation instructions
and only keep track of the emulated instructions. This reduces a 200
page execution trace down to one half of one page. (25 text lines).




Yes, you can screen out the instructions that are just UTM, but when the
UTM is modified to be a Halt Decider, the parts of the execution that is
Halt Decider should be shown, as that DOES effect the execution.  In
particular, its decision point to continue or abort. The fact that it
decided to continue IS a conditional in the path.


It turns out that the decision to abort infinite recursion that is multiple levels deep or a single level deep is the same very simple algorithm. I was also pleased to find out that checking for infinite loops is very easy too.

Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.

With this line-of-demarcation drawn between the simulator and the input we can know that any decision by the simulator to abort the otherwise infinite execution of its input does not involve any conditional branch instructions in the input. All of these conditional branch instructions are in the simulator.




--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](Step 1a)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 18:28 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!3.eu.feeder.erje.net!feeder.erje.net!goblin1!goblin3!goblin.stu.neva.ru!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 12:28:21 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](Step 1a)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<he6dnVxcwNcfviHCnZ2dnUU78IfNnZ2d@brightview.co.uk>
<ndKdnaIe-v9PtCHCnZ2dnUU7-XPNnZ2d@giganews.com>
<5eGdndmbxcGA1iHCnZ2dnUU78enNnZ2d@brightview.co.uk>
<WcCdncOumL5JyCHCnZ2dnUU7-Y3NnZ2d@giganews.com> <87im9vpg0e.fsf@bsb.me.uk>
<qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> <87sg8yah0c.fsf@bsb.me.uk>
<Weqdnbjny8LJqSDCnZ2dnUU7-d_NnZ2d@giganews.com> <87tute8f4h.fsf@bsb.me.uk>
<2aidnV9e3qQaOCDCnZ2dnUU7-c3NnZ2d@giganews.com> <87zh355bfu.fsf@bsb.me.uk>
<6Y6dnaUGHOdNRCPCnZ2dnUU7-fPNnZ2d@giganews.com> <87r1og6fd0.fsf@bsb.me.uk>
<g4udnSi9pZyZiSLCnZ2dnUU7-VvNnZ2d@giganews.com> <87h7pa4sfp.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 12:28:29 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <87h7pa4sfp.fsf@bsb.me.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <S5WdnU3dSYfY2FzCnZ2dnUU7-cPNnZ2d@giganews.com>
Lines: 124
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-c8blX6ufDFg/xiDtFFKcoWZCbfOfYgP7ZjBzvPfmZ8DgHQXQGqAyFuXs1COttC9PUuF+veU1oegME8q!P9WECYnYnXeAbQYr2G+SNaW6on53K09A1TVBDV0kCZzBrOP8DdV5Uo4lQ29UXW7e/A6Z2rkIenF1!1g==
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: 6079
View all headers
On 11/27/2020 11:31 AM, Ben Bacarisse wrote:
olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:

On 11/25/2020 8:06 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/25/2020 4:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/24/2020 6:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

<cut>
08 bool Halts(u32 P, u32 I)
09 {
10   bool Halted  = false;
11   bool Aborted = false;
12   while (!Halted && !Aborted)
13   {
14     Halted  = DebugStep(P, I);
15     Aborted = Needs_To_Be_Aborted();
16   }
17   return !Aborted;
18 }

Given

      void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

The confounding example for Halts is the computation
Confound_Halts(Confound_Halts) whose halting status is not correctly
determined by the function call Halts(Confound_Halts, Confound_Halts).

Halts(Confound_Halts, Confound_Halts) returns false.

But Confound_Halts(Confound_Halts) is a finite computation, so that's
the wrong answer (as you know perfectly well).

You start with the assumption: "Pete is wrong".

I start with the definition of what a halt decider is (in your model
using quasi-C): a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

To actually understand me you have to start with the first step by
understanding that in the following code DebugTrace() never returns a
value to to H_Hat().

Yes, it's obvious, and I've said so on at least two occasions, though
sometimes the function names were different.  (You love to give
different function the same name, and similar functions different names.
It all adds the swirling mass of confusion in which you try to hide your
ruse.)


Progressive refinement makes my words easier to understand.
Sometimes this progressive refinement to make my words easier to understand requires reformulting what I am saying.

I note you declined another opportunity say you know what the halting
problem and you have also never denied the facts that you cut from the
post you are replying to:

As you as I encounter your first crucial misunderstanding I igrore all of your words after that and focus on correctly this key misunderstanding.

A halt decider is a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

Do you agree?

(a) Halts(Confound_Halts, Confound_Halts) returns false, and
(b) Confound_Halts(Confound_Halts) is a finite computation.

Your failure to understand that this is a logical necessity is no actual rebuttal what-so-ever that it is not a logical necessity:

    Any input (TMD / DATA) that would never halt unless
    its simulator stopped simulating it expresses behavior
    that is not halting behavior.

When Halts simulates Confound_Halts(Confound_Halts) Halts it decides that Confound_Halts(Confound_Halts) would never halt unless Halts stopped simulating it.


Therefore Halts is not a halt decider.  Which of the these do you
disagree with?

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;
}

In case you missed it the previous times I told you, yes, this code is
non-halting.  See the difference between an honest interlocutor and
yourself?  If your question is clear, I will answer it.  You, on the
other hand, duck and dive, evade and distract.  Maybe you will change
and ANSWER THE QUESTIONS ABOVE.



--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 18:32 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 12:32:13 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](line-of-demarcation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<0P9wH.143428$xe4.139914@fx41.iad>
<EqqdnZ8_5PAAsVzCnZ2dnUU7-Q3NnZ2d@giganews.com>
<G%awH.79627$ql4.18346@fx39.iad>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 12:32:21 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <G%awH.79627$ql4.18346@fx39.iad>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <S5WdnUzdSYew21zCnZ2dnUU7-cOdnZ2d@giganews.com>
Lines: 73
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vAyNQIw5ScrUhQvZtw32SrWAAlQVxgeI+PtVZ5o72sUaV5MCm9DcacAHEzc6elH1DXrOZ3tyPJXKLnG!WtACAsghwa8VsTXSUq4PYf5+nYytayEcoqbJMHvCCswH3GUnuLP8Wvv5R1swbRmCMhRHcUgFKITn!Bw==
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: 5295
View all headers
On 11/27/2020 11:50 AM, Richard Damon wrote:
On 11/27/20 11:43 AM, olcott wrote:
On 11/27/2020 10:28 AM, Richard Damon wrote:
On 11/27/20 10:23 AM, olcott wrote:

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

Because of this I simply screen out all of the emulation instructions
and only keep track of the emulated instructions. This reduces a 200
page execution trace down to one half of one page. (25 text lines).




Yes, you can screen out the instructions that are just UTM, but when the
UTM is modified to be a Halt Decider, the parts of the execution that is
Halt Decider should be shown, as that DOES effect the execution.  In
particular, its decision point to continue or abort. The fact that it
decided to continue IS a conditional in the path.


It turns out that the decision to abort infinite recursion that is
multiple levels deep or a single level deep is the same very simple
algorithm. I was also pleased to find out that checking for infinite
loops is very easy too.

Any input (TMD / DATA) that would never halt unless its simulator
stopped simulating it expresses behavior that is not halting behavior.

With this line-of-demarcation drawn between the simulator and the input
we can know that any decision by the simulator to abort the otherwise
infinite execution of its input does not involve any conditional branch
instructions in the input. All of these conditional branch instructions
are in the simulator.


The issue you don't seem to understand is that the decision to 'abort'
in nested calls to halts IS part of the computation being analysed by
the outer nalt decider. By neglecting that, you come up with the wrong
answer. Yes, at the OUTER level, it isn't part of the computation, but
within it, it is.


If you understand the basic principle that a TMD simulated by a UTM is computationally equivalent to the direct execution of a TM then you would understand that:

(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to

(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the actual computation.

Because of this I simply screen out all of the emulation instructions and only keep track of the emulated instructions. This reduces a 200 page execution trace down to one half of one page. (25 text lines).




--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 18:36 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 12:36:19 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](line-of-demarcation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<0P9wH.143428$xe4.139914@fx41.iad>
<EqqdnZ8_5PAAsVzCnZ2dnUU7-Q3NnZ2d@giganews.com>
<G%awH.79627$ql4.18346@fx39.iad>
<S5WdnUzdSYew21zCnZ2dnUU7-cOdnZ2d@giganews.com>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 12:36:26 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <S5WdnUzdSYew21zCnZ2dnUU7-cOdnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <gNudnUa5Jvm-2lzCnZ2dnUU7-VvNnZ2d@giganews.com>
Lines: 102
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-89Q++n5IeS9D/YYDuGHJIaX4737JDN52AoNYsHNDrcXOfZEpSR9P95txFfi+ssEnYbqqsgq8fTF0eTI!laAkKTKdMTHRAboSvaushb7Q9VeGwfiMTt6PG159EskVaR33uD3GH8LwtlIhnmQtq0f7YXfOlIzR!EA==
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: 6800
View all headers
On 11/27/2020 12:32 PM, olcott wrote:
On 11/27/2020 11:50 AM, Richard Damon wrote:
On 11/27/20 11:43 AM, olcott wrote:
On 11/27/2020 10:28 AM, Richard Damon wrote:
On 11/27/20 10:23 AM, olcott wrote:

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

Because of this I simply screen out all of the emulation instructions
and only keep track of the emulated instructions. This reduces a 200
page execution trace down to one half of one page. (25 text lines).




Yes, you can screen out the instructions that are just UTM, but when the
UTM is modified to be a Halt Decider, the parts of the execution that is
Halt Decider should be shown, as that DOES effect the execution.  In
particular, its decision point to continue or abort. The fact that it
decided to continue IS a conditional in the path.


It turns out that the decision to abort infinite recursion that is
multiple levels deep or a single level deep is the same very simple
algorithm. I was also pleased to find out that checking for infinite
loops is very easy too.

Any input (TMD / DATA) that would never halt unless its simulator
stopped simulating it expresses behavior that is not halting behavior.

With this line-of-demarcation drawn between the simulator and the input
we can know that any decision by the simulator to abort the otherwise
infinite execution of its input does not involve any conditional branch
instructions in the input. All of these conditional branch instructions
are in the simulator.


The issue you don't seem to understand is that the decision to 'abort'
in nested calls to halts IS part of the computation being analysed by
the outer nalt decider. By neglecting that, you come up with the wrong
answer. Yes, at the OUTER level, it isn't part of the computation, but
within it, it is.


If you understand the basic principle that a TMD simulated by a UTM is computationally equivalent to the direct execution of a TM then you would understand that:

(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to

(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the actual computation.

Because of this I simply screen out all of the emulation instructions and only keep track of the emulated instructions. This reduces a 200 page execution trace down to one half of one page. (25 text lines).

Output_Debug_Trace() [00010bc4]  size(148)  capacity(65536)
[000005a4](01)  55                  push ebp
[000005a5](02)  8bec                mov ebp,esp
[000005a7](01)  51                  push ecx
[000005a8](07)  c745fc74050000      mov [ebp-04],00000574
[000005af](03)  8b45fc              mov eax,[ebp-04]
[000005b2](01)  50                  push eax
[000005b3](03)  8b4dfc              mov ecx,[ebp-04]
[000005b6](01)  51                  push ecx
[000005b7](05)  e898fdffff          call 00000354   ----CALL[00000354]
[00000574](01)  55                  push ebp
[00000575](02)  8bec                mov ebp,esp
[00000577](01)  51                  push ecx
[00000578](03)  8b4508              mov eax,[ebp+08]
[0000057b](01)  50                  push eax
[0000057c](03)  8b4d08              mov ecx,[ebp+08]
[0000057f](01)  51                  push ecx
[00000580](05)  e8cffdffff          call 00000354   ----CALL[00000354]
[00000574](01)  55                  push ebp
[00000575](02)  8bec                mov ebp,esp
[00000577](01)  51                  push ecx
[00000578](03)  8b4508              mov eax,[ebp+08]
[0000057b](01)  50                  push eax
[0000057c](03)  8b4d08              mov ecx,[ebp+08]
[0000057f](01)  51                  push ecx
[00000580](05)  e8cffdffff          call 00000354   ----CALL[00000354]



--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 19:23 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.uzoreto.com!tr1.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 13:23:42 -0600
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](line-of-demarcation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <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> <MUUvH.221490$gR8.150244@fx45.iad> <epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com> <NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk> <VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com> <BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk> <C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com> <0P9wH.143428$xe4.139914@fx41.iad> <EqqdnZ8_5PAAsVzCnZ2dnUU7-Q3NnZ2d@giganews.com> <G%awH.79627$ql4.18346@fx39.iad> <S5WdnUzdSYew21zCnZ2dnUU7-cOdnZ2d@giganews.com> <FRbwH.222044$gR8.59913@fx45.iad>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 13:23:50 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <FRbwH.222044$gR8.59913@fx45.iad>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <vOednaIzcMOjz1zCnZ2dnUU7-cPNnZ2d@giganews.com>
Lines: 90
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-TE2Gyx/uq8Sa/XhLN6jsjmXiN5WzU9OOHlEv/IB1LXSwg/Hj7Ns8huQoF5H1FdiMEEpksZ9tROW7tob!A0n1y7rq44W0cAvI2TzMivQBk+jINpBwsK+Wrh1O5dsiyreUECmRD7zn2KrmmD3xu4aE9068YfJr!4A==
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: 6075
View all headers
On 11/27/2020 12:48 PM, Richard Damon wrote:
On 11/27/20 1:32 PM, olcott wrote:
On 11/27/2020 11:50 AM, Richard Damon wrote:
On 11/27/20 11:43 AM, olcott wrote:
On 11/27/2020 10:28 AM, Richard Damon wrote:
On 11/27/20 10:23 AM, olcott wrote:

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

Because of this I simply screen out all of the emulation instructions
and only keep track of the emulated instructions. This reduces a 200
page execution trace down to one half of one page. (25 text lines).




Yes, you can screen out the instructions that are just UTM, but when
the
UTM is modified to be a Halt Decider, the parts of the execution
that is
Halt Decider should be shown, as that DOES effect the execution.  In
particular, its decision point to continue or abort. The fact that it
decided to continue IS a conditional in the path.


It turns out that the decision to abort infinite recursion that is
multiple levels deep or a single level deep is the same very simple
algorithm. I was also pleased to find out that checking for infinite
loops is very easy too.

Any input (TMD / DATA) that would never halt unless its simulator
stopped simulating it expresses behavior that is not halting behavior.

With this line-of-demarcation drawn between the simulator and the input
we can know that any decision by the simulator to abort the otherwise
infinite execution of its input does not involve any conditional branch
instructions in the input. All of these conditional branch instructions
are in the simulator.


The issue you don't seem to understand is that the decision to 'abort'
in nested calls to halts IS part of the computation being analysed by
the outer nalt decider. By neglecting that, you come up with the wrong
answer. Yes, at the OUTER level, it isn't part of the computation, but
within it, it is.


If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:

(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to

(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

Because of this I simply screen out all of the emulation instructions
and only keep track of the emulated instructions. This reduces a 200
page execution trace down to one half of one page. (25 text lines).


As I have said, yes, you can exclude the steps that are just the
emulation, but need to include the steps that are part of a Halt
Decision that is part of a call to a Halts within the trace being made.


No that is not true.

When the simlator decides to stop simulating its input this is a decision by the simulator and not a decision by the input:

Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.



--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 20:24 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!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 14:24:21 -0600
Subject: Re: It is known that a correct halt decider must return false (in
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<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>
<KIOdnfRX6Okd913CnZ2dnUU7-RnNnZ2d@giganews.com>
<iuudnUtPRJ81wFzCnZ2dnUU78YHNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 14:24:28 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <iuudnUtPRJ81wFzCnZ2dnUU78YHNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <voKdnd0YRfvo_VzCnZ2dnUU7-b3NnZ2d@giganews.com>
Lines: 274
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-B922bvVR7CJcyieETSUGHhqdB/JVs6Jd9xtd4S6gy7pcxFLc7SMwsfQD/dIO3UEteQVXgSi3x5dsJIS!9OzYVzLaMFy4pb78VCEcTcWS7n3D6NJDs+UixyIt0tYKF5n/P85RStHtLBB86OTggIyuSLyh27lK!wg==
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: 11061
View all headers
On 11/27/2020 2:12 PM, Mike Terry wrote:
On 27/11/2020 02:55, olcott wrote:
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?

ok, so the following are two different calculations.  (I didn't say anything about DIFFERENT calculations running under different emulators.)

Also, the H_Hats are different.  As I know you like to confuse different programs by giving them the same name to make it appear there is only one program involved, I'll rename them to H_HatD (calls DebugTrace) and H_HatH (calls Halts)



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;
}


The above caclulation has infinite recursive EMULATION.  It never halts.

A selective trace of the calculation would show

DebugTrace emulates (H_HatD, H_HatD)
    EL1:   H_HatD calls DebugTrace
           DebugTrace emulates (H_HatD, H_HatD)
       EL2:   H_HatD calls DebugTrace
              DebugTrace emulates (H_HatD, H_HatD)
          EL3:   H_HatD calls DebugTrace
                 DebugTrace emulates (H_HatD, H_HatD)
             EL4:   H_HatD calls DebugTrace
                    DebugTrace emulates (H_HatD, H_HatD)
  .... etc. - infinite recursive EMULATION

In a full trace of course, the outer level emulations continue generating trace data, since they are single-stepping their inner emulations.  This is a simplified trace to aid readability.

And what of the calculation H_HatD(H_HatD)?

H_HatD calls DebugTrace
DebugTrace emulates (H_HatD, H_HatD)
    EL1:   H_HatD calls DebugTrace
           DebugTrace emulates (H_HatD, H_HatD)
       EL2:   H_HatD calls DebugTrace
              DebugTrace emulates (H_HatD, H_HatD)
          EL3:   H_HatD calls DebugTrace
                 DebugTrace emulates (H_HatD, H_HatD)
             EL4:   H_HatD calls DebugTrace
                    DebugTrace emulates (H_HatD, H_HatD)
  .... etc. - also infinite recursive EMULATION


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;
}

The above caclulation halts.  There is no infinite recursion.
Also, just as a reminder, this H_HatH isn't the same H_HatD as the first calculation.


Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.

When Halts() simulates its input (playing the exact same role as the above UTM) then any "not halting" decision that it makes according to the above criteria would be necessarily correct.

Halts(H_Hat, H_Hat) is such a "not halting" decision.

A selected trace of this calculation would show

Halts emulates (H_HatH, H_HatH)
    EL1:   H_HatH calls Halts
           Halts emulates (H_HatH, H_HatH)
       EL2:   H_HatH calls Halts
Halts TEST matches  [but TEST is unsound and in this case
                      the input calculation halts - see
                      below]
Halts returns false, deciding non-halting.


And what of the calculation H_HatH(H_HatH)

H_HatH calls Halts
Halts emulates (H_HatH, H_HatH)
    EL1:   H_HatH calls Halts
           Halts emulates (H_HatH, H_HatH)
       EL2:   H_HatH calls Halts
Halts TEST matches
Halts returns false, deciding non-halting.
H_HatH halts

(The caclulation halts)


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

The calculations are not "identical" because the "TMs" being traced are not even functionally the same.

As I have proved very many times and you keep ignoring: The execution of H_Hat under Halts() is provably identical (exact same machine code byes in the exact same sequence) to the execution of H_Hat under DebugTrace()

The only difference between these two computations:

a) DebugTrace/H_Hat
b) Halts/H_Hat

is that in the latter one Halts correctly decides "not halting" for H_Hat and stops simulating it according to this correct criteria:

Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.




--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (logical foundation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 20:29 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!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 14:29:46 -0600
Subject: Re: It is known that a correct halt decider must return false
(logical foundation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@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>
<KIOdnfRX6Okd913CnZ2dnUU7-RnNnZ2d@giganews.com>
<iuudnUtPRJ81wFzCnZ2dnUU78YHNnZ2d@brightview.co.uk>
<voKdnd0YRfvo_VzCnZ2dnUU7-b3NnZ2d@giganews.com>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 14:29:54 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <voKdnd0YRfvo_VzCnZ2dnUU7-b3NnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <HKSdnR9b8oIn_FzCnZ2dnUU7-dHNnZ2d@giganews.com>
Lines: 285
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-w7HKVAMKVgijL2WCfQyej9B+2KWgxd1NJ4KrhiBviCSsfryY0/6w5sHdGxTw0HteboJlsahuRW960zk!CcK8qAAFPOSb/2GG58J49sDsl/6E6LH1FweA6VHCBNQVEzZXA61UbFwHkMZrzp2Ml1B1OLoq0dIk!iw==
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: 11802
View all headers
On 11/27/2020 2:24 PM, olcott wrote:
On 11/27/2020 2:12 PM, Mike Terry wrote:
On 27/11/2020 02:55, olcott wrote:
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?

ok, so the following are two different calculations.  (I didn't say anything about DIFFERENT calculations running under different emulators.)

Also, the H_Hats are different.  As I know you like to confuse different programs by giving them the same name to make it appear there is only one program involved, I'll rename them to H_HatD (calls DebugTrace) and H_HatH (calls Halts)



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;
}


The above caclulation has infinite recursive EMULATION.  It never halts.

A selective trace of the calculation would show

DebugTrace emulates (H_HatD, H_HatD)
    EL1:   H_HatD calls DebugTrace
           DebugTrace emulates (H_HatD, H_HatD)
       EL2:   H_HatD calls DebugTrace
              DebugTrace emulates (H_HatD, H_HatD)
          EL3:   H_HatD calls DebugTrace
                 DebugTrace emulates (H_HatD, H_HatD)
             EL4:   H_HatD calls DebugTrace
                    DebugTrace emulates (H_HatD, H_HatD)
  .... etc. - infinite recursive EMULATION

In a full trace of course, the outer level emulations continue generating trace data, since they are single-stepping their inner emulations.  This is a simplified trace to aid readability.

And what of the calculation H_HatD(H_HatD)?

H_HatD calls DebugTrace
DebugTrace emulates (H_HatD, H_HatD)
    EL1:   H_HatD calls DebugTrace
           DebugTrace emulates (H_HatD, H_HatD)
       EL2:   H_HatD calls DebugTrace
              DebugTrace emulates (H_HatD, H_HatD)
          EL3:   H_HatD calls DebugTrace
                 DebugTrace emulates (H_HatD, H_HatD)
             EL4:   H_HatD calls DebugTrace
                    DebugTrace emulates (H_HatD, H_HatD)
  .... etc. - also infinite recursive EMULATION


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;
}

The above caclulation halts.  There is no infinite recursion.
Also, just as a reminder, this H_HatH isn't the same H_HatD as the first calculation.


Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.

When Halts() simulates its input (playing the exact same role as the above UTM) then any "not halting" decision that it makes according to the above criteria would be necessarily correct.

Halts(H_Hat, H_Hat) is such a "not halting" decision.

A selected trace of this calculation would show

Halts emulates (H_HatH, H_HatH)
    EL1:   H_HatH calls Halts
           Halts emulates (H_HatH, H_HatH)
       EL2:   H_HatH calls Halts
Halts TEST matches  [but TEST is unsound and in this case
                      the input calculation halts - see
                      below]
Halts returns false, deciding non-halting.


And what of the calculation H_HatH(H_HatH)

H_HatH calls Halts
Halts emulates (H_HatH, H_HatH)
    EL1:   H_HatH calls Halts
           Halts emulates (H_HatH, H_HatH)
       EL2:   H_HatH calls Halts
Halts TEST matches
Halts returns false, deciding non-halting.
H_HatH halts

(The caclulation halts)


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

The calculations are not "identical" because the "TMs" being traced are not even functionally the same.

As I have proved very many times and you keep ignoring: The execution of H_Hat under Halts() is provably identical (exact same machine code byes in the exact same sequence) to the execution of H_Hat under DebugTrace()

The only difference between these two computations:

a) DebugTrace/H_Hat
b) Halts/H_Hat

is that in the latter one Halts correctly decides "not halting" for H_Hat and stops simulating it according to this correct criteria:

Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior.

Basically the "rebuttals" now come down to this:
People really really believe that the halting problem has been proved to be undecidable therefore anything and everything that I say must necessarily be incorrect entirely on the basis of their strongly held belief.

It never occurs to anyone that strongly held beliefs are not themselves any logical foundation what-so-ever.


--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 20:36 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 14:36:44 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](emulation levels)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<eqidnQ9vzaZS_FzCnZ2dnUU78QmdnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 14:36:51 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <eqidnQ9vzaZS_FzCnZ2dnUU78QmdnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <P4KdncmJssHB_lzCnZ2dnUU7-f3NnZ2d@giganews.com>
Lines: 164
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-JAPbTOl3Y4hTqTFoLPvENrhqqNRPMB5krGQDiMNpPmLbNrjYsRgFxcKu1miJ2JwPl1yXxFtxIBb+bKN!RlFOktaQYhViKz89Ol1C7InugbYsJMiiVh7lzes/rZKgHCE8hjt15uttnrCPXrMCIVv4Tr0LgwOy!rw==
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: 8399
View all headers
On 11/27/2020 2:28 PM, Mike Terry wrote:
On 27/11/2020 15:23, olcott wrote:
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least
the
fact that is didn't abort / did abort indication (with an
indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to
the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break
out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution
trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

No, that's PLAIN WRONG.  It indicates that you haven't thought through how emulation works.

When A emulates <A> the emulated <A> matches the calculation A ONLY UP TO THE POINT WHERE EMULATION STOPS.  This is EMULATION recursion.

When A calls A, there is no stopping of execution until the inner A returns.  This is CALL recursion.

Different scenarios - your TEST works for CALL recursion, because there is no breaking out of the loop so the loop continues forever.  Therefore the CALL recursion never halts.  You cannot apply this argument for EMULATION recurtion, because the emulation can stop without there being any conditional code in the code block of your TEST.


Mike.


Ignoring everything else besides the details that are specified here:
When A emulates B emulates A
this is computationally equivalent to
A calls B calls A

--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 20:40 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!aioe.org!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 14:40:34 -0600
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <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> <MUUvH.221490$gR8.150244@fx45.iad> <epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com> <NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk> <VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com> <BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk> <C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com> <eqidnQ9vzaZS_FzCnZ2dnUU78QmdnZ2d@brightview.co.uk> <P4KdncmJssHB_lzCnZ2dnUU7-f3NnZ2d@giganews.com>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 14:40:42 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <P4KdncmJssHB_lzCnZ2dnUU7-f3NnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <-eWdnY9KTarf-VzCnZ2dnUU7-UPNnZ2d@giganews.com>
Lines: 180
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-3YsR/Q/C1yCXqW7pnuL87mDf5haIHzsrp2SO5PC+38abjHCbJDEi/1jb7rCqxSX7npvhlntJ15GgAuL!EeaX4U6EnQIRtFo0Jn4AHvUNyVAMu9SiPZPe1fHXboUUg3t+vB2Xa9XmWYerJJnYcaoLYu6cEtcZ!4Q==
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: 8781
X-Received-Bytes: 8908
X-Received-Body-CRC: 797083877
View all headers
On 11/27/2020 2:36 PM, olcott wrote:
On 11/27/2020 2:28 PM, Mike Terry wrote:
On 27/11/2020 15:23, olcott wrote:
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least
the
fact that is didn't abort / did abort indication (with an
indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to
the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break
out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution
trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

No, that's PLAIN WRONG.  It indicates that you haven't thought through how emulation works.

When A emulates <A> the emulated <A> matches the calculation A ONLY UP TO THE POINT WHERE EMULATION STOPS.  This is EMULATION recursion.

When A calls A, there is no stopping of execution until the inner A returns.  This is CALL recursion.

Different scenarios - your TEST works for CALL recursion, because there is no breaking out of the loop so the loop continues forever.  Therefore the CALL recursion never halts.  You cannot apply this argument for EMULATION recurtion, because the emulation can stop without there being any conditional code in the code block of your TEST.


Mike.


Ignoring everything else besides the details that are specified here:
When A emulates B emulates A
this is computationally equivalent to
A calls B calls A


When <A> emulates <B> emulates <A>
this is computationally equivalent to
A calls B calls A


--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Organization: Jupiter Mining Corporation
Date: Fri, 27 Nov 2020 21:03 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!aioe.org!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx42.ams4.POSTED!not-for-mail
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](emulation levels)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<eqidnQ9vzaZS_FzCnZ2dnUU78QmdnZ2d@brightview.co.uk>
<P4KdncmJssHB_lzCnZ2dnUU7-f3NnZ2d@giganews.com>
<-eWdnY9KTarf-VzCnZ2dnUU7-UPNnZ2d@giganews.com>
From: flibbleR...@i42.co.uk (Mr Flibble)
Organization: Jupiter Mining Corporation
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <-eWdnY9KTarf-VzCnZ2dnUU7-UPNnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-GB
Content-Transfer-Encoding: 8bit
Lines: 164
Message-ID: <AQdwH.47651$J736.12637@fx42.ams4>
X-Complaints-To: abuse@newsdemon.com
NNTP-Posting-Date: Fri, 27 Nov 2020 21:03:28 UTC
Date: Fri, 27 Nov 2020 21:03:29 +0000
X-Received-Bytes: 8392
X-Received-Body-CRC: 1133819279
View all headers
On 27/11/2020 20:40, olcott wrote:
On 11/27/2020 2:36 PM, olcott wrote:
On 11/27/2020 2:28 PM, Mike Terry wrote:
On 27/11/2020 15:23, olcott wrote:
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least
the
fact that is didn't abort / did abort indication (with an
indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to
the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break
out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution
trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

No, that's PLAIN WRONG.  It indicates that you haven't thought through how emulation works.

When A emulates <A> the emulated <A> matches the calculation A ONLY UP TO THE POINT WHERE EMULATION STOPS.  This is EMULATION recursion.

When A calls A, there is no stopping of execution until the inner A returns.  This is CALL recursion.

Different scenarios - your TEST works for CALL recursion, because there is no breaking out of the loop so the loop continues forever. Therefore the CALL recursion never halts.  You cannot apply this argument for EMULATION recurtion, because the emulation can stop without there being any conditional code in the code block of your TEST.


Mike.


Ignoring everything else besides the details that are specified here:
When A emulates B emulates A
this is computationally equivalent to
A calls B calls A


When <A> emulates <B> emulates <A>
this is computationally equivalent to
A calls B calls A

No it isn't: the first A and the second A are different entities even if they are the same "type".

/Flibble

--
¬


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](emulation levels)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Fri, 27 Nov 2020 21:12 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 27 Nov 2020 15:12:22 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](emulation levels)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<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>
<MUUvH.221490$gR8.150244@fx45.iad>
<epmdnUjtztBag13CnZ2dnUU7-L3NnZ2d@giganews.com>
<NJmdnRAhuNQvuV3CnZ2dnUU78fGdnZ2d@brightview.co.uk>
<VYadnffHC4Mlu13CnZ2dnUU7-W3NnZ2d@giganews.com>
<BZednVuDNNJlzF3CnZ2dnUU78VnNnZ2d@brightview.co.uk>
<C_2dnX-7gJxThFzCnZ2dnUU7-T_NnZ2d@giganews.com>
<eqidnQ9vzaZS_FzCnZ2dnUU78QmdnZ2d@brightview.co.uk>
<P4KdncmJssHB_lzCnZ2dnUU7-f3NnZ2d@giganews.com>
<-eWdnY9KTarf-VzCnZ2dnUU7-UPNnZ2d@giganews.com>
<AQdwH.47651$J736.12637@fx42.ams4>
From: NoO...@NoWhere.com (olcott)
Date: Fri, 27 Nov 2020 15:12:29 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <AQdwH.47651$J736.12637@fx42.ams4>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <RvudneisyJYr9lzCnZ2dnUU7-c_NnZ2d@giganews.com>
Lines: 208
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-gwar2BaIH4exNVMmAWOWlj/6HHf3jHhX4skUmdC2J71Sk5PZk8PhnZNBme55q2Uja8Blyp7+YT3Djoh!hAles3qdu3PXbOzrrS/xQod1q4pxJEmaiBIiCDu3PXsAYKp1aeRQQkEfETc713XLcsK/gJbVbVhD!fw==
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: 9714
View all headers
On 11/27/2020 3:03 PM, Mr Flibble wrote:
On 27/11/2020 20:40, olcott wrote:
On 11/27/2020 2:36 PM, olcott wrote:
On 11/27/2020 2:28 PM, Mike Terry wrote:
On 27/11/2020 15:23, olcott wrote:
On 11/26/2020 7:10 PM, Mike Terry wrote:
On 26/11/2020 22:05, olcott wrote:
On 11/26/2020 3:57 PM, Mike Terry wrote:
On 26/11/2020 21:31, olcott wrote:
On 11/26/2020 3:14 PM, Richard Damon wrote:
On 11/26/20 3:50 PM, olcott wrote:


That could simply be thought of as recursive invocation 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;
}

One thing that I have realized as I am thinking on this, your
'trace' of
execution NEEDS to include, or at least acknowledge the operation of
the
Halts code when that call occurs when under emulation.

That is part of the issue with your logic, by removing that from the
trace, you are loosing come of the actions that are actually part of
the
computations being traced.

The operating system already knows that it does not have any infinite
execution.

Maybe it doesn't need to show all the gritty details, but at least
the
fact that is didn't abort / did abort indication (with an
indication of
what level was making that decision, so multiple lines might report)

Any person looking at an execution trace that includes two calls to
the
same function from the same machine address that does not have any
conditional branch instruction in-between that could possibly break
out
of this infinite recursion knows the infinite recursion has been
detected.


WRONG.  I keep telling you this, and you just say "it's right, it's
right, recursive EMULATION is the same as recursive CALL"

BUT IT'S NOT - your test is unsound.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

In the traces of interest, those trace entries are not within the same
emulation level.  It is not the same as "recursive CALL" where a
direct branch is made.  When A begins emulating B, you generate trace
entries for B, but A is still executing - it is monitoring B, and may
decide to abort B for whatever reason.  This is the key difference
between recursive CALL and recursive EMULATION.

(Your argument applies ok with recursive calls rather than emulations.)

So, say again who is the one who doesn't understand recursion?  :)

Mike.



To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

The case for infinite recursion is similar.

-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

Not so - an outer level of recursion can abort execution in the case
of recursive EMULATION.

I will probably start a new thread on this, but will wait in case you
have some further argument to present.


None of any of this makes any difference to the correctness of the
halting decision which is made on the basis of the global execution
trace.

Um, well that would be a global trace of RECURSIVE EMULATIONS, so an

If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.

No, that's PLAIN WRONG.  It indicates that you haven't thought through how emulation works.

When A emulates <A> the emulated <A> matches the calculation A ONLY UP TO THE POINT WHERE EMULATION STOPS.  This is EMULATION recursion.

When A calls A, there is no stopping of execution until the inner A returns.  This is CALL recursion.

Different scenarios - your TEST works for CALL recursion, because there is no breaking out of the loop so the loop continues forever. Therefore the CALL recursion never halts.  You cannot apply this argument for EMULATION recurtion, because the emulation can stop without there being any conditional code in the code block of your TEST.


Mike.


Ignoring everything else besides the details that are specified here:
When A emulates B emulates A
this is computationally equivalent to
A calls B calls A


When <A> emulates <B> emulates <A>
this is computationally equivalent to
A calls B calls A

No it isn't: the first A and the second A are different entities even if they are the same "type".

/Flibble


The first <A> and the second <A> are the exact same sequence of tape elements of the master UTM tape in the same way that the following function has only a single sequence of bytes comprising its x86 machine code:

void Recursive_Function()
{
   Recursive_Function();
}

--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c++, comp.lang.c
Followup: comp.theory
Date: Sat, 28 Nov 2020 03:53 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.alt.net!feeder.usenetexpress.com!tr1.iad1.usenetexpress.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, 27 Nov 2020 21:53:23 -0600
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c++,comp.lang.c
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <he6dnVxcwNcfviHCnZ2dnUU78IfNnZ2d@brightview.co.uk> <ndKdnaIe-v9PtCHCnZ2dnUU7-XPNnZ2d@giganews.com> <5eGdndmbxcGA1iHCnZ2dnUU78enNnZ2d@brightview.co.uk> <WcCdncOumL5JyCHCnZ2dnUU7-Y3NnZ2d@giganews.com> <87im9vpg0e.fsf@bsb.me.uk> <qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> <87sg8yah0c.fsf@bsb.me.uk> <Weqdnbjny8LJqSDCnZ2dnUU7-d_NnZ2d@giganews.com> <87tute8f4h.fsf@bsb.me.uk> <2aidnV9e3qQaOCDCnZ2dnUU7-c3NnZ2d@giganews.com> <87zh355bfu.fsf@bsb.me.uk> <6Y6dnaUGHOdNRCPCnZ2dnUU7-fPNnZ2d@giganews.com> <87r1og6fd0.fsf@bsb.me.uk> <g4udnSi9pZyZiSLCnZ2dnUU7-VvNnZ2d@giganews.com> <87h7pa4sfp.fsf@bsb.me.uk> <S5WdnU3dSYfY2FzCnZ2dnUU7-cPNnZ2d@giganews.com> <87zh322ngm.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
Followup-To: comp.theory
Date: Fri, 27 Nov 2020 21:53:30 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <87zh322ngm.fsf@bsb.me.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <6eSdnYuLBrIuVFzCnZ2dnUU7-cPNnZ2d@giganews.com>
Lines: 217
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-HE7XyVWTbYE/gBiSgGnyJY+dNZtar0wK8dOrTcABttvJStI+91Bi2f5tHVPK3uG9JfBKvJjI8HL19xO!Ipq9MikfpFkvhEKanqfXyjrFIFjWeqAQLH4a2PtpTQgHqQJ3OM3SWMF3NMOYcn7XXcSVngSPMKvA!SQ==
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: 10212
View all headers
On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/27/2020 11:31 AM, Ben Bacarisse wrote:
olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:

On 11/25/2020 8:06 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/25/2020 4:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/24/2020 6:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

<cut>
08 bool Halts(u32 P, u32 I)
09 {
10   bool Halted  = false;
11   bool Aborted = false;
12   while (!Halted && !Aborted)
13   {
14     Halted  = DebugStep(P, I);
15     Aborted = Needs_To_Be_Aborted();
16   }
17   return !Aborted;
18 }

Given

       void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

The confounding example for Halts is the computation
Confound_Halts(Confound_Halts) whose halting status is not correctly
determined by the function call Halts(Confound_Halts, Confound_Halts).

Halts(Confound_Halts, Confound_Halts) returns false.

But Confound_Halts(Confound_Halts) is a finite computation, so that's
the wrong answer (as you know perfectly well).

You start with the assumption: "Pete is wrong".

I start with the definition of what a halt decider is (in your model
using quasi-C): a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

To actually understand me you have to start with the first step by
understanding that in the following code DebugTrace() never returns a
value to to H_Hat().

Yes, it's obvious, and I've said so on at least two occasions, though
sometimes the function names were different.
<cut>
I note you declined another opportunity say you know what the halting
problem and you have also never denied the facts that you cut from the
post you are replying to:

As you as I encounter your first crucial misunderstanding I igrore all
of your words after that and focus on correctly this key
misunderstanding.

This is a feeble excuse to avoid answering a few simple questions.  Why
must avoid answering?  The trouble is that you don't disagree with me,
but you dare not say so explicitly or game will be up.  Let's see how
that works:

A halt decider is a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

Do you agree?


I never answer yes or no questions with a yes or no answer.
I always answer yes or no questions with a complete explanation that derives a yes or no answer. I answered the above question this way in my next answer.

Ignored yet again.  That's because you know this is what a halt decider
is (in this context) and that your proposed function isn't one.

(a) Halts(Confound_Halts, Confound_Halts) returns false, and
(b) Confound_Halts(Confound_Halts) is a finite computation.

Your failure to understand that this is a logical necessity is no
actual rebuttal what-so-ever that it is not a logical necessity:

    Any input (TMD / DATA) that would never halt unless
    its simulator stopped simulating it expresses behavior
    that is not halting behavior.

Again an evasion, and for the same reason.  You gave (a) so you can't
retract it, and you know (b) is also a fact.

It is not an evasion it is a step-by-step proof that I am correct and you always skip these steps and leap to the conclusion that I am incorrect.

By the way, you are correct.  My failure to understand that something is
a logical necessity is in no way a rebuttal that it is one.  But why
would I? 

A computation that would not halt if its simulation were not
halted is indeed a non-halting computation.  But a computation that
would not halt and one that is halted are different computations.

Yes, that is the exact dichotomy required by the actual halting problem.


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

Halts(H_Hat, H_Hat) does correctly decide that its input would not halt unless Halts stopped simulating it, then Halts(H_Hat, H_Hat) itself halts.

Confound_Halts(Confound_Halts) is a computation that does halt.  It's
just a word game to say that it only halts because it's simulation had
to be halted in the course of determining the return value from Halts.

Not so much. In this case H_Hat never gets any return value from Halts so it can't possibly do the opposite of whatever Halts decides and Halts does have to stop simulating H_Hat or H_Hat would have never halted.

The halting status (and therefore the correct halting decision) is not
dependent on why a computation is finite, only that it is.

When Halts simulates Confound_Halts(Confound_Halts) Halts it decides
that Confound_Halts(Confound_Halts) would never halt unless Halts
stopped simulating it.

Halts(Confound_Halts, Confound_Halts) returns false, according to you,
making Confound_Halts(Confound_Halts) a finite computation. 

No not at all. Halts is a finite computation. The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite.

How this
determination is made by Halts makes no difference.  The determination

The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite.

was made and false returned (again, according to you).  You would love
it if readers took the fact that Halts has a particular /reason/ for
returning false, namely that the execution would not otherwise
terminate, as excusing the fact that false is the wrong answer.

The input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite.

Therefore Halts is not a halt decider.  Which of the these do you
disagree with?

No answer?  What a surprise!

I just proved that Halts does decide (H_Hat, H_Hat) correctly because the input to Halts is only finite because Halts forced it to be finite, otherwise it is infinite.

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;
}

In case you missed it the previous times I told you, yes, this code is
non-halting.  See the difference between an honest interlocutor and
yourself?  If your question is clear, I will answer it.  You, on the
other hand, duck and dive, evade and distract.  Maybe you will change
and ANSWER THE QUESTIONS ABOVE.

Not a single one of my questions answered.


I answer yes or no questions with a complete explanation.

If you can have the discipline to very very carefully analyze my answers as if there was a real chance that I am correct then it should be quite easy to verify in your own mind that I am actually correct.

This is the key to understanding that I am correct.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

When the simulator stops simulating H_Hat before H_Hat ever gets any return value from Halts this makes it impossible for H_Hat to do the opposite of whatever Halts decides, thus making all the conventional HP proofs lose their entire basis.

--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Sat, 28 Nov 2020 16:14 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 28 Nov 2020 10:14:32 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](keys to understanding)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<he6dnVxcwNcfviHCnZ2dnUU78IfNnZ2d@brightview.co.uk>
<ndKdnaIe-v9PtCHCnZ2dnUU7-XPNnZ2d@giganews.com>
<5eGdndmbxcGA1iHCnZ2dnUU78enNnZ2d@brightview.co.uk>
<WcCdncOumL5JyCHCnZ2dnUU7-Y3NnZ2d@giganews.com> <87im9vpg0e.fsf@bsb.me.uk>
<qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> <87sg8yah0c.fsf@bsb.me.uk>
<Weqdnbjny8LJqSDCnZ2dnUU7-d_NnZ2d@giganews.com> <87tute8f4h.fsf@bsb.me.uk>
<2aidnV9e3qQaOCDCnZ2dnUU7-c3NnZ2d@giganews.com> <87zh355bfu.fsf@bsb.me.uk>
<6Y6dnaUGHOdNRCPCnZ2dnUU7-fPNnZ2d@giganews.com> <87r1og6fd0.fsf@bsb.me.uk>
<g4udnSi9pZyZiSLCnZ2dnUU7-VvNnZ2d@giganews.com> <87h7pa4sfp.fsf@bsb.me.uk>
<S5WdnU3dSYfY2FzCnZ2dnUU7-cPNnZ2d@giganews.com> <87zh322ngm.fsf@bsb.me.uk>
<6eSdnYuLBrIuVFzCnZ2dnUU7-cPNnZ2d@giganews.com>
<OZSdnZrs5rQf6V_CnZ2dnUU78RnNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 28 Nov 2020 10:14:40 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <OZSdnZrs5rQf6V_CnZ2dnUU78RnNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <9_edndwKu-T16l_CnZ2dnUU7-W_NnZ2d@giganews.com>
Lines: 147
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-9kZvWEV/Ur68WT0/WMaHIwgTv5NiF6Vyo4ZM/YFoNeRP3sC7wVhOTRIxigoK7zhv/Bs1NwK2kyP60Z7!EGfUdWqsFZDKuhRoXzU4DC6d+Zeg8UDgWysc3S0zCcr/b8z2YfQIi8jaSn3ckfObrDzaYcQik249!xA==
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: 8056
View all headers
On 11/28/2020 10:02 AM, Mike Terry wrote:
On 28/11/2020 03:53, olcott wrote:
On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/27/2020 11:31 AM, Ben Bacarisse wrote:
olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:

On 11/25/2020 8:06 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/25/2020 4:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/24/2020 6:16 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

<cut>
08 bool Halts(u32 P, u32 I)
09 {
10   bool Halted  = false;
11   bool Aborted = false;
12   while (!Halted && !Aborted)
13   {
14     Halted  = DebugStep(P, I);
15     Aborted = Needs_To_Be_Aborted();
16   }
17   return !Aborted;
18 }

Given

       void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

The confounding example for Halts is the computation
Confound_Halts(Confound_Halts) whose halting status is not
correctly
determined by the function call Halts(Confound_Halts,
Confound_Halts).

Halts(Confound_Halts, Confound_Halts) returns false.

But Confound_Halts(Confound_Halts) is a finite computation, so
that's
the wrong answer (as you know perfectly well).

You start with the assumption: "Pete is wrong".

I start with the definition of what a halt decider is (in your model
using quasi-C): a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

To actually understand me you have to start with the first step by
understanding that in the following code DebugTrace() never returns a
value to to H_Hat().

Yes, it's obvious, and I've said so on at least two occasions, though
sometimes the function names were different.
<cut>
I note you declined another opportunity say you know what the halting
problem and you have also never denied the facts that you cut from the
post you are replying to:

As you as I encounter your first crucial misunderstanding I igrore all
of your words after that and focus on correctly this key
misunderstanding.

This is a feeble excuse to avoid answering a few simple questions.  Why
must avoid answering?  The trouble is that you don't disagree with me,
but you dare not say so explicitly or game will be up.  Let's see how
that works:

A halt decider is a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

Do you agree?


I never answer yes or no questions with a yes or no answer.
I always answer yes or no questions with a complete explanation that
derives a yes or no answer. I answered the above question this way in my
next answer.


Well that's exactly what cranks do.  (And tricksters looking for ways to mislead their audience, while maintaining a pretense of "hey, I'm not lying!!  Show me exactly where I lied!!".)


Correctly answering questions that are based on fundamental misconceptions requires answering these questions outside the scope of the fundamental misconception.

I suggest you change this policy to
a)  Answer the question with yes or no
b)  If you feel the need to explain further, then explain further
c)  If you feel the question doesn't have a yes/no answer, just say
     so and explain why.

I can't do this because these people have a religious conviction that their yes or no question that is based on a fundamental misconception is a correct question.

I have to prove step-by-step detail-by-detail that their question is based on a fundamental misconception or they simply reject whatever I say out-of-hand without review.

Your refusal to say yes/no is a fear of commitment, because you know ultimately you will fail if forced into a logical debate, and just want to avoid being pinned down.  Why not at least have the intellectual honesty to answer questions put to you directly!

No this is not the case.

Besides, answering questions directly is part of normal civil discourse.   When you buy your burger and are asked "would you like chips with that?" do you respond with an explanation of how five years ago you were diagnosed with some medical condition (which implies you're allergic to starch)?  The civil way of behaving here is to just answer yes or no and move on.  Anything else is an attempt to stall proceedings and avoid genuine communication.


Mike.


If you can have the discipline to very very carefully analyze my answers as if there was a real chance that I am correct then it should be quite easy to verify in your own mind that I am actually correct.

This is the key to understanding that I am correct.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

When the simulator stops simulating H_Hat before H_Hat ever gets any return value from Halts this makes it impossible for H_Hat to do the opposite of whatever Halts decides, thus making all the conventional HP proofs lose their entire basis.

--
Copyright 2020 Pete Olcott

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


Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Sat, 28 Nov 2020 16:25 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.alt.net!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 28 Nov 2020 10:25:23 -0600
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <he6dnVxcwNcfviHCnZ2dnUU78IfNnZ2d@brightview.co.uk> <ndKdnaIe-v9PtCHCnZ2dnUU7-XPNnZ2d@giganews.com> <5eGdndmbxcGA1iHCnZ2dnUU78enNnZ2d@brightview.co.uk> <WcCdncOumL5JyCHCnZ2dnUU7-Y3NnZ2d@giganews.com> <87im9vpg0e.fsf@bsb.me.uk> <qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> <87sg8yah0c.fsf@bsb.me.uk> <Weqdnbjny8LJqSDCnZ2dnUU7-d_NnZ2d@giganews.com> <87tute8f4h.fsf@bsb.me.uk> <2aidnV9e3qQaOCDCnZ2dnUU7-c3NnZ2d@giganews.com> <87zh355bfu.fsf@bsb.me.uk> <6Y6dnaUGHOdNRCPCnZ2dnUU7-fPNnZ2d@giganews.com> <87r1og6fd0.fsf@bsb.me.uk> <g4udnSi9pZyZiSLCnZ2dnUU7-VvNnZ2d@giganews.com> <87h7pa4sfp.fsf@bsb.me.uk> <S5WdnU3dSYfY2FzCnZ2dnUU7-cPNnZ2d@giganews.com> <87zh322ngm.fsf@bsb.me.uk> <6eSdnYuLBrIuVFzCnZ2dnUU7-cPNnZ2d@giganews.com> <OZSdnZrs5rQf6V_CnZ2dnUU78RnNnZ2d@brightview.co.uk> <c8774d84-55d2-46cc-b69b-fae8ea88f4f7n@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 28 Nov 2020 10:25:31 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <c8774d84-55d2-46cc-b69b-fae8ea88f4f7n@googlegroups.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Message-ID: <c4udnT-PC4Nu5F_CnZ2dnUU7-e2dnZ2d@giganews.com>
Lines: 41
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-lps/kofgl4BJPVF0Fvn8h8sdLYxiCx20zKKaIbptNlJl9UPHKv9M9sS67B3/MzqxPqH1HU43DDhvztc!uyFOYhHirNAZ9VcwtKSU++tFVOsO/qvFbFL5/fbJpaLT3GYThl/F3LqS9aK9Ghpg9BhNBQ5Br5ZP!WQ==
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: 3994
View all headers
On 11/28/2020 10:18 AM, Malcolm McLean wrote:
On Saturday, 28 November 2020 at 16:02:13 UTC, Mike Terry wrote:

Besides, answering questions directly is part of normal civil discourse.
When you buy your burger and are asked "would you like chips with
that?" do you respond with an explanation of how five years ago you were
diagnosed with some medical condition (which implies you're allergic to
starch)? The civil way of behaving here is to just answer yes or no and
move on. Anything else is an attempt to stall proceedings and avoid
genuine communication.

The civil thing to do is to say "I'd love some chips with that, but I have
an allergy to starch". Then the "crew" member feels that they have done
their best and the attempt to sell chips was forlorn.

You'd understand that if you had ever worked for McDonald's.


THE ONLY REASON THAT MOST EVERYONE HERE DOES NOT ALREADY KNOW THAT I AM CORRECT IS THAT THEY MAKE SURE TO IGNORE THESE WORDS:

If you can have the discipline to very very carefully analyze my answers as if there was a real chance that I am correct then it should be quite easy to verify in your own mind that I am actually correct.

This is the key to understanding that I am correct.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

When the simulator stops simulating H_Hat before H_Hat ever gets any return value from Halts this makes it impossible for H_Hat to do the opposite of whatever Halts decides, thus making all the conventional HP proofs lose their entire basis.

--
Copyright 2020 Pete Olcott

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


Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Sun, 29 Nov 2020 22:33 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!aioe.org!peer01.ams4!peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 29 Nov 2020 16:33:05 -0600
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <QrqdnS61EOtetCDCnZ2dnUU78TPNnZ2d@brightview.co.uk> <qPCdnSYYdNW-FyPCnZ2dnUU78QHNnZ2d@brightview.co.uk> <EOudnWsbKL0RDyPCnZ2dnUU7-SudnZ2d@giganews.com> <M-GdnWrECtIvViPCnZ2dnUU78c_NnZ2d@brightview.co.uk> <ZridnafptIUjTyPCnZ2dnUU7-UXNnZ2d@giganews.com> <zIudnVpmqcfEdCPCnZ2dnUU78aOdnZ2d@brightview.co.uk> <_PidnS5eJ9eLcCPCnZ2dnUU7-LfNnZ2d@giganews.com> <Iqmdnbz55_xraiPCnZ2dnUU78V-dnZ2d@brightview.co.uk> <zf6dnTkZ6Pi-YSPCnZ2dnUU7-TudnZ2d@giganews.com> <OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk> <NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com> <-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk> <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>
From: NoO...@NoWhere.com (olcott)
Date: Sun, 29 Nov 2020 16:33:14 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <_eCdnSZdT4qMfCLCnZ2dnUU78I_NnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <3_ydnRQlSJY8vFnCnZ2dnUU7-L3NnZ2d@giganews.com>
Lines: 359
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Q1TOWdpfMDWNmJe/lFvkeDkIB+4llk3cx2x38i2TbcPTjkmdRpYslOQlXrUlwnhaAiXLM3lGRVbfS1D!GENvungutdpYnFUjqucsohAqRsiv+4u+fBpkc6+6Op2qpka9E7d+DTEZ/M9VsmYfsnRg+Xhz4MYU!7A==
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: 16831
X-Received-Bytes: 17055
X-Received-Body-CRC: 699853233
View all headers
On 11/26/2020 11:08 AM, Mike Terry wrote:
On 26/11/2020 16:41, olcott wrote:
On 11/26/2020 10:30 AM, Mike Terry wrote:
On 26/11/2020 16:07, olcott wrote:
On 11/26/2020 9:48 AM, Mike Terry wrote:
On 26/11/2020 04:39, olcott wrote:
On 11/25/2020 10:27 PM, Mike Terry wrote:
On 26/11/2020 02:14, olcott wrote:
On 11/25/2020 7:38 PM, Mike Terry wrote:
On 26/11/2020 00:51, olcott wrote:
On 11/25/2020 6:33 PM, Mike Terry wrote:
On 25/11/2020 23:47, olcott wrote:
On 11/25/2020 5:31 PM, Mike Terry wrote:
On 25/11/2020 21:55, olcott wrote:
On 11/25/2020 3:25 PM, Mike Terry wrote:
On 25/11/2020 17:21, olcott wrote:
On 11/25/2020 10:45 AM, Mike Terry wrote:
On 24/11/2020 15:41, Mike Terry wrote:
On 24/11/2020 04:18, olcott wrote:
<.. snip ..>

People can eventually look at all of my code and the
thousands of
lines
of code of the x86 emulator and they can look at the
hundreds of
pages
out output. It all boils down to this:

The simulator merely watches its simulation of the
following
instructions until it sees a function call to 377 from
503
the
second
time with no JCC (Jump-Condition_Code) in-between.


I have told you many times that your test must be UNSOUND.
You
have
never responded to this, so I've assumed you don't really
know
whether
your test is sound or unsound (or probably, what that even
means,
although I've also explained that to you before).

Now you are getting closer to actually coding the test
(which
you
claimed to have "fully coded" two years ago), you are
finally
giving
more details.

So...  what do you think.  Is the following test a SOUND
test
for
non-halting?

   TEST:  "monitor the simulation until there is a
function
           call to 377 from 503 a second time, with no
conditional
           branch inbetween"

Putting it more directly - if some calculation P(I)
triggers the
TEST
(so it contains two calls from 377 from 503, with no
conditional
branch
inbetween), does this genuinely imply that the calculation
will
never
halt?

Bear in mind that the two calls in question do not
necessarily
occur in
the same "virtual address space", that is to say the two
calls can
[and
in the case of T_Hat(T_Hat) *do* ] occur at /different
levels of
emulation/.   [Your trace notation obscures this simple
fact,
making
everything appear to be in one single virtual process,
when
it's
not.]

What do you think?  This seems to be your primary
intuition
that
triggered all this "refuting" activity, BUT IS IT ACTUALLY
CORRECT?

Of course, you will say "All my intuitions are correct by
definition -
I'm never wrong" but that doesn't make it true!  :)

Is TEST *SOUND* ?


Noted: still no response to this basic question.

Mike.

<.. snip non-response to question ..>

I'm not sure if that non-response was deliberate.  I
didn't ask
whether one specified implementation of [whatever] exhibits
infinite
recursion!

In case it was just a misreading, here is the question again.


   So...  what do you think.  Is the following test a SOUND
test
for
   non-halting?

      TEST:  "monitor the simulation until there is a
function
              call to 377 from 503 a second time, with no
conditional
              branch in-between"

It is much more generic than that.
(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.

Copyright 2020 Pete Olcott (I just wrote that algorithm right
now).

OK, I always imagined the test would be more general than just
checking specifically for calls to 377 from 503.  :)  No
problem on
that front.

I'm thinking this is probably the basis of your initial
intuition
that
you could actually detect and handle the type of recursion in
your
fledgeling (at that time) halt decider design.

It is good that you've clarified the test, and yet it seems
you're
reluctant to plainly say that you believe the test works!

logical necessity speaks for itself it doesn't need me for a
cheerleader.


LOL.  I knew you'd do something like that.

OK, so you are saying that if your test detects the behaviour
described, then it's a "logical necessity" that the input being
examined is non-halting?

Yes that is what I am saying.

There - that wasn't so bad, was it?  :)


Can you find a counter-example?

Well, if it's a logical necessity I'm in for a hard time on that
one...

But here's the point:  logical necessity absolutely /does/ need a
cheerleader!  Loads of things are "logically necessary" in that
they
must logically be true, and yet they are not /obviously/ true.
That's
why we have proofs.

This would be one of those scenarios, where even if your claim is
correct, it's not trivially obvious that it's correct, right?

Here is what we're saying:

TEST:
    If a calculation P(I) has a trace of steps
    (s0, s1, s2, s3, .....) and there are two steps s_i
    and s_j, such that si and sj are both unconditional
    branches from A to B, and none of the steps in-between
    s_i and s_j are conditional branches, THEN calculation
    P(I) never halts.

Well that's certainly not a "trivial restatement of word
meanings" or
similar, and so is not seen to correct just on a casual glance.

So obviously where I'm going is : do you have a proof of this?

Now I know you're not one for proofs, and maybe during the
course of
discussion such a proof will fall out (provided the underlying
logic
is correct...)

So to start with, perhaps you can just give your thinking as to
/why/
you believe it to be logically necessary?  [You clearly didn't
wake up
one day and think "hey, what about TEST - oh! it's a logical
necessity, that's handy - I can use it in my halt decider!".  There
was something that led you to consider TEST, and having considered
it,
you decided for whatever reason it was true...]


Mike.


Let's look at it a little simpler:
HERE:  // current location
  Instructions that cannot possibly exit a loop
THERE: goto HERE;

Can you see how this definitely loops?

I can - and if this was relevant there would be a straight forward
proof that such code loops.

But this isn't like the scenario you are dealing with AT ALL!  What
you are showing here is a kind of "in-process" loop detection.  What
you need is some kind of recursive EMULATION detection.  (Emulation
works differently in this respect.)

I'm pretty sure I explained the difference in a post a couple of
weeks
ago but you never responded.

We are trying to determine whether or not a specific sequence of x86
machine code bytes specify an infinite loop as if this machine code
was
a mathematical formalism.

The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY?


Well, I understand that the code bytes that you presented, if executed
by a processor within one single logical thread of execution, would
never terminate - there is an obvious loop.

But that's ignoring the issue of RECURSION, where behaviour is not so
simple.  So what's the next step?  (So far what you've said is no
justification for the RECUSION scenario, which is what you TEST is
concerned with.)

Mike.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete list
of every instruction that can possibly exit the above loop and if there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

Like I said, that is ok for a "contiguous thread of execution", i.e.
if an x86 processor starts at HERE, and then steps its execution,
executing the instructions, then the processor will go round and round
the loop. The proof is easy.


The case for infinite recursion is similar.

No it's not.  The easy proof for the contiguous thread of execution
does not work in the case where there is recursion.  Or, put more
accurately, it works WITHIN A SINGLE CONTIGUOUS THREAD OF EXECUTION
(the obvious proof still works for this), but *NOT WHEN THE TRACE
ENTRIES CROSS RECURSION LEVELS*.


-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then
recursion is infinite.

That doesn't work with recursive emulation, BECAUSE THE EMULATION CAN

Click here to read the complete article
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Mon, 30 Nov 2020 01:16 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!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 29 Nov 2020 19:15:58 -0600
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return
_false_(in_this_case)[V4](recursive_emulation_≡
_recursive_invocation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<EOudnWsbKL0RDyPCnZ2dnUU7-SudnZ2d@giganews.com>
<M-GdnWrECtIvViPCnZ2dnUU78c_NnZ2d@brightview.co.uk>
<ZridnafptIUjTyPCnZ2dnUU7-UXNnZ2d@giganews.com>
<zIudnVpmqcfEdCPCnZ2dnUU78aOdnZ2d@brightview.co.uk>
<_PidnS5eJ9eLcCPCnZ2dnUU7-LfNnZ2d@giganews.com>
<Iqmdnbz55_xraiPCnZ2dnUU78V-dnZ2d@brightview.co.uk>
<zf6dnTkZ6Pi-YSPCnZ2dnUU7-TudnZ2d@giganews.com>
<OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk>
<NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
<3_ydnRQlSJY8vFnCnZ2dnUU7-L3NnZ2d@giganews.com>
<lsednciM6c6VolnCnZ2dnUU78X_NnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Sun, 29 Nov 2020 19:16:07 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <lsednciM6c6VolnCnZ2dnUU78X_NnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <2s6dnehj0tVT2lnCnZ2dnUU7-IfNnZ2d@giganews.com>
Lines: 399
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-DlNkyWHlxMiOFpxeKwwF4S/y3zUfJ+V+gehNxMEFswl/h0yQSZdZeiitnSplpykdpNsz1yJAglocIR5!imEIhy+3NzemWBJskaccetiqmZi9/upFaxYYFKauLf7cl64XdIcJ5ZAo1WgO9Ftr32ZtOGardUlP!Gw==
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: 18453
View all headers
On 11/29/2020 6:38 PM, Mike Terry wrote:
On 29/11/2020 22:33, olcott wrote:
On 11/26/2020 11:08 AM, Mike Terry wrote:
On 26/11/2020 16:41, olcott wrote:
On 11/26/2020 10:30 AM, Mike Terry wrote:
On 26/11/2020 16:07, olcott wrote:
On 11/26/2020 9:48 AM, Mike Terry wrote:
On 26/11/2020 04:39, olcott wrote:
On 11/25/2020 10:27 PM, Mike Terry wrote:
On 26/11/2020 02:14, olcott wrote:
On 11/25/2020 7:38 PM, Mike Terry wrote:
On 26/11/2020 00:51, olcott wrote:
On 11/25/2020 6:33 PM, Mike Terry wrote:
On 25/11/2020 23:47, olcott wrote:
On 11/25/2020 5:31 PM, Mike Terry wrote:
On 25/11/2020 21:55, olcott wrote:
On 11/25/2020 3:25 PM, Mike Terry wrote:
On 25/11/2020 17:21, olcott wrote:
On 11/25/2020 10:45 AM, Mike Terry wrote:
On 24/11/2020 15:41, Mike Terry wrote:
On 24/11/2020 04:18, olcott wrote:
<.. snip ..>

People can eventually look at all of my code and the
thousands of
lines
of code of the x86 emulator and they can look at the
hundreds of
pages
out output. It all boils down to this:

The simulator merely watches its simulation of the
following
instructions until it sees a function call to 377 from
503
the
second
time with no JCC (Jump-Condition_Code) in-between.


I have told you many times that your test must be
UNSOUND.
You
have
never responded to this, so I've assumed you don't
really
know
whether
your test is sound or unsound (or probably, what that
even
means,
although I've also explained that to you before).

Now you are getting closer to actually coding the test
(which
you
claimed to have "fully coded" two years ago), you are
finally
giving
more details.

So...  what do you think.  Is the following test a SOUND
test
for
non-halting?

   TEST:  "monitor the simulation until there is a
function
           call to 377 from 503 a second time, with no
conditional
           branch inbetween"

Putting it more directly - if some calculation P(I)
triggers the
TEST
(so it contains two calls from 377 from 503, with no
conditional
branch
inbetween), does this genuinely imply that the
calculation
will
never
halt?

Bear in mind that the two calls in question do not
necessarily
occur in
the same "virtual address space", that is to say the two
calls can
[and
in the case of T_Hat(T_Hat) *do* ] occur at /different
levels of
emulation/.   [Your trace notation obscures this simple
fact,
making
everything appear to be in one single virtual process,
when
it's
not.]

What do you think?  This seems to be your primary
intuition
that
triggered all this "refuting" activity, BUT IS IT
ACTUALLY
CORRECT?

Of course, you will say "All my intuitions are
correct by
definition -
I'm never wrong" but that doesn't make it true!  :)

Is TEST *SOUND* ?


Noted: still no response to this basic question.

Mike.

<.. snip non-response to question ..>

I'm not sure if that non-response was deliberate.  I
didn't ask
whether one specified implementation of [whatever] exhibits
infinite
recursion!

In case it was just a misreading, here is the question
again.


   So...  what do you think.  Is the following test a SOUND
test
for
   non-halting?

      TEST:  "monitor the simulation until there is a
function
              call to 377 from 503 a second time, with no
conditional
              branch in-between"

It is much more generic than that.
(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.

Copyright 2020 Pete Olcott (I just wrote that algorithm
right
now).

OK, I always imagined the test would be more general than
just
checking specifically for calls to 377 from 503.  :)  No
problem on
that front.

I'm thinking this is probably the basis of your initial
intuition
that
you could actually detect and handle the type of recursion in
your
fledgeling (at that time) halt decider design.

It is good that you've clarified the test, and yet it seems
you're
reluctant to plainly say that you believe the test works!

logical necessity speaks for itself it doesn't need me for a
cheerleader.


LOL.  I knew you'd do something like that.

OK, so you are saying that if your test detects the behaviour
described, then it's a "logical necessity" that the input being
examined is non-halting?

Yes that is what I am saying.

There - that wasn't so bad, was it?  :)


Can you find a counter-example?

Well, if it's a logical necessity I'm in for a hard time on that
one...

But here's the point:  logical necessity absolutely /does/ need a
cheerleader!  Loads of things are "logically necessary" in that
they
must logically be true, and yet they are not /obviously/ true.
That's
why we have proofs.

This would be one of those scenarios, where even if your claim is
correct, it's not trivially obvious that it's correct, right?

Here is what we're saying:

TEST:
    If a calculation P(I) has a trace of steps
    (s0, s1, s2, s3, .....) and there are two steps s_i
    and s_j, such that si and sj are both unconditional
    branches from A to B, and none of the steps in-between
    s_i and s_j are conditional branches, THEN calculation
    P(I) never halts.

Well that's certainly not a "trivial restatement of word
meanings" or
similar, and so is not seen to correct just on a casual glance.

So obviously where I'm going is : do you have a proof of this?

Now I know you're not one for proofs, and maybe during the
course of
discussion such a proof will fall out (provided the underlying
logic
is correct...)

So to start with, perhaps you can just give your thinking as to
/why/
you believe it to be logically necessary?  [You clearly didn't
wake up
one day and think "hey, what about TEST - oh! it's a logical
necessity, that's handy - I can use it in my halt decider!".
There
was something that led you to consider TEST, and having
considered
it,
you decided for whatever reason it was true...]


Mike.


Let's look at it a little simpler:
HERE:  // current location
  Instructions that cannot possibly exit a loop
THERE: goto HERE;

Can you see how this definitely loops?

I can - and if this was relevant there would be a straight forward
proof that such code loops.

But this isn't like the scenario you are dealing with AT ALL!  What
you are showing here is a kind of "in-process" loop detection.
What
you need is some kind of recursive EMULATION detection.  (Emulation
works differently in this respect.)

I'm pretty sure I explained the difference in a post a couple of
weeks
ago but you never responded.

We are trying to determine whether or not a specific sequence of x86
machine code bytes specify an infinite loop as if this machine code
was
a mathematical formalism.

The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY?


Well, I understand that the code bytes that you presented, if
executed
by a processor within one single logical thread of execution, would
never terminate - there is an obvious loop.

But that's ignoring the issue of RECURSION, where behaviour is not so
simple.  So what's the next step?  (So far what you've said is no
justification for the RECUSION scenario, which is what you TEST is
concerned with.)

Mike.


The sequences of instructions from HERE to THERE and HERE to HERE are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know that
the loop is infinite.

Like I said, that is ok for a "contiguous thread of execution", i.e.
if an x86 processor starts at HERE, and then steps its execution,
executing the instructions, then the processor will go round and round
the loop. The proof is easy.


The case for infinite recursion is similar.

No it's not.  The easy proof for the contiguous thread of execution
does not work in the case where there is recursion.  Or, put more
accurately, it works WITHIN A SINGLE CONTIGUOUS THREAD OF EXECUTION
(the obvious proof still works for this), but *NOT WHEN THE TRACE
ENTRIES CROSS RECURSION LEVELS*.


-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

If there are no instructions that can possibly exit recursion between
invocations of the same function from the same machine address, then

Click here to read the complete article
Subject: Re: It is known that a correct halt decider must return false (in this case)[V4](keys to understanding)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Mon, 30 Nov 2020 02:26 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 29 Nov 2020 20:26:37 -0600
Subject: Re: It is known that a correct halt decider must return false (in
this case)[V4](keys to understanding)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<he6dnVxcwNcfviHCnZ2dnUU78IfNnZ2d@brightview.co.uk>
<ndKdnaIe-v9PtCHCnZ2dnUU7-XPNnZ2d@giganews.com>
<5eGdndmbxcGA1iHCnZ2dnUU78enNnZ2d@brightview.co.uk>
<WcCdncOumL5JyCHCnZ2dnUU7-Y3NnZ2d@giganews.com> <87im9vpg0e.fsf@bsb.me.uk>
<qoGdnW1Lz5qmByHCnZ2dnUU7-UPNnZ2d@giganews.com> <87sg8yah0c.fsf@bsb.me.uk>
<Weqdnbjny8LJqSDCnZ2dnUU7-d_NnZ2d@giganews.com> <87tute8f4h.fsf@bsb.me.uk>
<2aidnV9e3qQaOCDCnZ2dnUU7-c3NnZ2d@giganews.com> <87zh355bfu.fsf@bsb.me.uk>
<6Y6dnaUGHOdNRCPCnZ2dnUU7-fPNnZ2d@giganews.com> <87r1og6fd0.fsf@bsb.me.uk>
<g4udnSi9pZyZiSLCnZ2dnUU7-VvNnZ2d@giganews.com> <87h7pa4sfp.fsf@bsb.me.uk>
<S5WdnU3dSYfY2FzCnZ2dnUU7-cPNnZ2d@giganews.com> <87zh322ngm.fsf@bsb.me.uk>
<6eSdnYuLBrIuVFzCnZ2dnUU7-cPNnZ2d@giganews.com> <87blff1uyv.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
Date: Sun, 29 Nov 2020 20:26:46 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <87blff1uyv.fsf@bsb.me.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <YOKdnRHmh7_AxVnCnZ2dnUU7-QudnZ2d@giganews.com>
Lines: 66
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-5zx7OvqFn6GtXDsMpXQUQCPOpft6IcUPuSCfBnyPVYARDA7wJF75ZJkD08AmOiYRmNd7L0WJ3A+Q6te!l5CPW5iMCamVfTiPXB6zJLKnuehUJ31GUs48hX3/njbOLqRhhiZOEsviECaqko113JDx2akN1UDM!ng==
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: 4118
View all headers
On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
On 11/27/2020 11:31 AM, Ben Bacarisse wrote:
<cut>
A halt decider is a function F such that F(P, I) is true iff P(I) is a
finite computation and false otherwise.

Do you agree?

I never answer yes or no questions with a yes or no answer.

Let's skip this for the moment because, amazingly (and probably
unwisely), you are very clear later on.  Since that's crux, let's skip
to it.

For reference (moved from higher up) here is your code:

  08 bool Halts(u32 P, u32 I)
  09 {
  10   bool Halted  = false;
  11   bool Aborted = false;
  12   while (!Halted && !Aborted)
  13   {
  14     Halted  = DebugStep(P, I);
  15     Aborted = Needs_To_Be_Aborted();
  16   }
  17   return !Aborted;
  18 }

And here is my reply:

  void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

<cut>
Halts(Confound_Halts, Confound_Halts) returns false, according to you,
making Confound_Halts(Confound_Halts) a finite computation.

No not at all.  Halts is a finite computation.

As required and not in doubt.

The input to Halts is only finite because Halts forced it to be
finite, otherwise it is infinite.

The input to Halts is, as you say, finite.  You got there at last!  So
you do, in fact, agree with both these key facts:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

Just like there is no exception to this rule:
∀n ∈ ℕ ((n > 5) → (N > 3))

Every computation that would not halt if its simulation were not halted is by logical necessity a non-halting computation.


--
Copyright 2020 Pete Olcott

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


Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Mon, 30 Nov 2020 03:12 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!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 29 Nov 2020 21:12:09 -0600
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return
_false_(in_this_case)[V4](recursive_emulation_≡
_recursive_invocation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com>
<ZridnafptIUjTyPCnZ2dnUU7-UXNnZ2d@giganews.com>
<zIudnVpmqcfEdCPCnZ2dnUU78aOdnZ2d@brightview.co.uk>
<_PidnS5eJ9eLcCPCnZ2dnUU7-LfNnZ2d@giganews.com>
<Iqmdnbz55_xraiPCnZ2dnUU78V-dnZ2d@brightview.co.uk>
<zf6dnTkZ6Pi-YSPCnZ2dnUU7-TudnZ2d@giganews.com>
<OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk>
<NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com>
<-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<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>
<3_ydnRQlSJY8vFnCnZ2dnUU7-L3NnZ2d@giganews.com>
<lsednciM6c6VolnCnZ2dnUU78X_NnZ2d@brightview.co.uk>
<2s6dnehj0tVT2lnCnZ2dnUU7-IfNnZ2d@giganews.com>
<262dnU6IlqGNxlnCnZ2dnUU78dHNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Sun, 29 Nov 2020 21:12:18 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <262dnU6IlqGNxlnCnZ2dnUU78dHNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <eIydnXwgZaqU_lnCnZ2dnUU7-LPNnZ2d@giganews.com>
Lines: 488
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-PY7dUaaarhEfbNyEpI+rgqeTPbT2rkqZF6gKSgd87iLGj57JeH/r/wwcULo/P2nxl14m/im4aCSTanK!kFKR8I4GyyZfMFxYEqcyEM/j0WbAFcvcodsdlj9RhV73/wh3WCQBFcwb+GRs9PmQdP7YT8Ryb6kZ!Qg==
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: 22306
View all headers
On 11/29/2020 8:38 PM, Mike Terry wrote:
On 30/11/2020 01:16, olcott wrote:
On 11/29/2020 6:38 PM, Mike Terry wrote:
On 29/11/2020 22:33, olcott wrote:
On 11/26/2020 11:08 AM, Mike Terry wrote:
On 26/11/2020 16:41, olcott wrote:
On 11/26/2020 10:30 AM, Mike Terry wrote:
On 26/11/2020 16:07, olcott wrote:
On 11/26/2020 9:48 AM, Mike Terry wrote:
On 26/11/2020 04:39, olcott wrote:
On 11/25/2020 10:27 PM, Mike Terry wrote:
On 26/11/2020 02:14, olcott wrote:
On 11/25/2020 7:38 PM, Mike Terry wrote:
On 26/11/2020 00:51, olcott wrote:
On 11/25/2020 6:33 PM, Mike Terry wrote:
On 25/11/2020 23:47, olcott wrote:
On 11/25/2020 5:31 PM, Mike Terry wrote:
On 25/11/2020 21:55, olcott wrote:
On 11/25/2020 3:25 PM, Mike Terry wrote:
On 25/11/2020 17:21, olcott wrote:
On 11/25/2020 10:45 AM, Mike Terry wrote:
On 24/11/2020 15:41, Mike Terry wrote:
On 24/11/2020 04:18, olcott wrote:
<.. snip ..>

People can eventually look at all of my code and the
thousands of
lines
of code of the x86 emulator and they can look at the
hundreds of
pages
out output. It all boils down to this:

The simulator merely watches its simulation of the
following
instructions until it sees a function call to 377
from
503
the
second
time with no JCC (Jump-Condition_Code) in-between.


I have told you many times that your test must be
UNSOUND.
You
have
never responded to this, so I've assumed you don't
really
know
whether
your test is sound or unsound (or probably, what that
even
means,
although I've also explained that to you before).

Now you are getting closer to actually coding the test
(which
you
claimed to have "fully coded" two years ago), you are
finally
giving
more details.

So...  what do you think.  Is the following test a
SOUND
test
for
non-halting?

   TEST:  "monitor the simulation until there is a
function
           call to 377 from 503 a second time, with no
conditional
           branch inbetween"

Putting it more directly - if some calculation P(I)
triggers the
TEST
(so it contains two calls from 377 from 503, with no
conditional
branch
inbetween), does this genuinely imply that the
calculation
will
never
halt?

Bear in mind that the two calls in question do not
necessarily
occur in
the same "virtual address space", that is to say
the two
calls can
[and
in the case of T_Hat(T_Hat) *do* ] occur at /different
levels of
emulation/.   [Your trace notation obscures this
simple
fact,
making
everything appear to be in one single virtual process,
when
it's
not.]

What do you think?  This seems to be your primary
intuition
that
triggered all this "refuting" activity, BUT IS IT
ACTUALLY
CORRECT?

Of course, you will say "All my intuitions are
correct by
definition -
I'm never wrong" but that doesn't make it true!  :)

Is TEST *SOUND* ?


Noted: still no response to this basic question.

Mike.

<.. snip non-response to question ..>

I'm not sure if that non-response was deliberate.  I
didn't ask
whether one specified implementation of [whatever]
exhibits
infinite
recursion!

In case it was just a misreading, here is the question
again.


   So...  what do you think.  Is the following test a
SOUND
test
for
   non-halting?

      TEST:  "monitor the simulation until there is a
function
              call to 377 from 503 a second time, with no
conditional
              branch in-between"

It is much more generic than that.
(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.

Copyright 2020 Pete Olcott (I just wrote that algorithm
right
now).

OK, I always imagined the test would be more general than
just
checking specifically for calls to 377 from 503.  :)  No
problem on
that front.

I'm thinking this is probably the basis of your initial
intuition
that
you could actually detect and handle the type of
recursion in
your
fledgeling (at that time) halt decider design.

It is good that you've clarified the test, and yet it seems
you're
reluctant to plainly say that you believe the test works!

logical necessity speaks for itself it doesn't need me for a
cheerleader.


LOL.  I knew you'd do something like that.

OK, so you are saying that if your test detects the behaviour
described, then it's a "logical necessity" that the input
being
examined is non-halting?

Yes that is what I am saying.

There - that wasn't so bad, was it?  :)


Can you find a counter-example?

Well, if it's a logical necessity I'm in for a hard time on
that
one...

But here's the point:  logical necessity absolutely /does/
need a
cheerleader!  Loads of things are "logically necessary" in that
they
must logically be true, and yet they are not /obviously/ true.
That's
why we have proofs.

This would be one of those scenarios, where even if your
claim is
correct, it's not trivially obvious that it's correct, right?

Here is what we're saying:

TEST:
    If a calculation P(I) has a trace of steps
    (s0, s1, s2, s3, .....) and there are two steps s_i
    and s_j, such that si and sj are both unconditional
    branches from A to B, and none of the steps in-between
    s_i and s_j are conditional branches, THEN calculation
    P(I) never halts.

Well that's certainly not a "trivial restatement of word
meanings" or
similar, and so is not seen to correct just on a casual glance.

So obviously where I'm going is : do you have a proof of this?

Now I know you're not one for proofs, and maybe during the
course of
discussion such a proof will fall out (provided the underlying
logic
is correct...)

So to start with, perhaps you can just give your thinking as to
/why/
you believe it to be logically necessary?  [You clearly didn't
wake up
one day and think "hey, what about TEST - oh! it's a logical
necessity, that's handy - I can use it in my halt decider!".
There
was something that led you to consider TEST, and having
considered
it,
you decided for whatever reason it was true...]


Mike.


Let's look at it a little simpler:
HERE:  // current location
  Instructions that cannot possibly exit a loop
THERE: goto HERE;

Can you see how this definitely loops?

I can - and if this was relevant there would be a straight
forward
proof that such code loops.

But this isn't like the scenario you are dealing with AT ALL!
What
you are showing here is a kind of "in-process" loop detection.
What
you need is some kind of recursive EMULATION detection.
(Emulation
works differently in this respect.)

I'm pretty sure I explained the difference in a post a couple of
weeks
ago but you never responded.

We are trying to determine whether or not a specific sequence
of x86
machine code bytes specify an infinite loop as if this machine
code
was
a mathematical formalism.

The only thing that matters is: WHAT DO THE BYTES THEMSELVES SAY?


Well, I understand that the code bytes that you presented, if
executed
by a processor within one single logical thread of execution, would
never terminate - there is an obvious loop.

But that's ignoring the issue of RECURSION, where behaviour is
not so
simple.  So what's the next step?  (So far what you've said is no
justification for the RECUSION scenario, which is what you TEST is
concerned with.)

Mike.


The sequences of instructions from HERE to THERE and HERE to HERE
are
from actual execution traces. The x86 emulator screens out all dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

To form a mathematical proof on the basis of the x86 language being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know
that
the loop is infinite.

Like I said, that is ok for a "contiguous thread of execution", i.e.
if an x86 processor starts at HERE, and then steps its execution,
executing the instructions, then the processor will go round and
round
the loop. The proof is easy.


The case for infinite recursion is similar.

No it's not.  The easy proof for the contiguous thread of execution
does not work in the case where there is recursion.  Or, put more
accurately, it works WITHIN A SINGLE CONTIGUOUS THREAD OF EXECUTION
(the obvious proof still works for this), but *NOT WHEN THE TRACE
ENTRIES CROSS RECURSION LEVELS*.


-HERE: Call Function At Address X
-   Instructions that cannot possibly exit recursion
-HERE: Call Function At Address X

Click here to read the complete article
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.software-eng
Date: Mon, 30 Nov 2020 03:53 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!aioe.org!peer02.ams4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 29 Nov 2020 21:53:02 -0600
Subject: Re:_It_is_known_that_a_correct_halt_decider_must_return_false_(in_this_case)[V4](recursive_emulation_≡_recursive_invocation)
Newsgroups: comp.theory,comp.ai.philosophy,comp.software-eng
References: <TqWdnXCuh8jFkibCnZ2dnUU7-QfNnZ2d@giganews.com> <_PidnS5eJ9eLcCPCnZ2dnUU7-LfNnZ2d@giganews.com> <Iqmdnbz55_xraiPCnZ2dnUU78V-dnZ2d@brightview.co.uk> <zf6dnTkZ6Pi-YSPCnZ2dnUU7-TudnZ2d@giganews.com> <OPKdncr_54uPmiLCnZ2dnUU78QednZ2d@brightview.co.uk> <NfidnR1APKUFkiLCnZ2dnUU7-b_NnZ2d@giganews.com> <-rSdnShOi6s1syLCnZ2dnUU78X_NnZ2d@brightview.co.uk> <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> <3_ydnRQlSJY8vFnCnZ2dnUU7-L3NnZ2d@giganews.com> <lsednciM6c6VolnCnZ2dnUU78X_NnZ2d@brightview.co.uk> <2s6dnehj0tVT2lnCnZ2dnUU7-IfNnZ2d@giganews.com> <262dnU6IlqGNxlnCnZ2dnUU78dHNnZ2d@brightview.co.uk> <eIydnXwgZaqU_lnCnZ2dnUU7-LPNnZ2d@giganews.com> <Rp6dnb7ZyLcm-FnCnZ2dnUU78bHNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
Date: Sun, 29 Nov 2020 21:53:11 -0600
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <Rp6dnb7ZyLcm-FnCnZ2dnUU78bHNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <RaudnenhwPkD8VnCnZ2dnUU7-KfNnZ2d@giganews.com>
Lines: 542
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-eln6WMqeBQGgmvBDig8iPvXSed++jmRAsO9Ag3z9O+egFgO3w8Q4r3eOVuGxzKUyIQJPqoJt6SdrqLg!tIdvRgq4hCWW3egwu+X+HA3nkWAlPq1JtX5WnMQ6k1KZFM/1U4c7Xaoju5M8fU7YNS1V5a6q/RW3!Hw==
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: 24628
X-Received-Bytes: 24853
X-Received-Body-CRC: 1024441852
View all headers
On 11/29/2020 9:23 PM, Mike Terry wrote:
On 30/11/2020 03:12, olcott wrote:
On 11/29/2020 8:38 PM, Mike Terry wrote:
On 30/11/2020 01:16, olcott wrote:
On 11/29/2020 6:38 PM, Mike Terry wrote:
On 29/11/2020 22:33, olcott wrote:
On 11/26/2020 11:08 AM, Mike Terry wrote:
On 26/11/2020 16:41, olcott wrote:
On 11/26/2020 10:30 AM, Mike Terry wrote:
On 26/11/2020 16:07, olcott wrote:
On 11/26/2020 9:48 AM, Mike Terry wrote:
On 26/11/2020 04:39, olcott wrote:
On 11/25/2020 10:27 PM, Mike Terry wrote:
On 26/11/2020 02:14, olcott wrote:
On 11/25/2020 7:38 PM, Mike Terry wrote:
On 26/11/2020 00:51, olcott wrote:
On 11/25/2020 6:33 PM, Mike Terry wrote:
On 25/11/2020 23:47, olcott wrote:
On 11/25/2020 5:31 PM, Mike Terry wrote:
On 25/11/2020 21:55, olcott wrote:
On 11/25/2020 3:25 PM, Mike Terry wrote:
On 25/11/2020 17:21, olcott wrote:
On 11/25/2020 10:45 AM, Mike Terry wrote:
On 24/11/2020 15:41, Mike Terry wrote:
On 24/11/2020 04:18, olcott wrote:
<.. snip ..>

People can eventually look at all of my code and
the
thousands of
lines
of code of the x86 emulator and they can look at
the
hundreds of
pages
out output. It all boils down to this:

The simulator merely watches its simulation of the
following
instructions until it sees a function call to 377
from
503
the
second
time with no JCC (Jump-Condition_Code) in-between.


I have told you many times that your test must be
UNSOUND.
You
have
never responded to this, so I've assumed you don't
really
know
whether
your test is sound or unsound (or probably, what
that
even
means,
although I've also explained that to you before).

Now you are getting closer to actually coding the
test
(which
you
claimed to have "fully coded" two years ago), you
are
finally
giving
more details.

So...  what do you think.  Is the following test a
SOUND
test
for
non-halting?

   TEST:  "monitor the simulation until there is a
function
           call to 377 from 503 a second time,
with no
conditional
           branch inbetween"

Putting it more directly - if some calculation P(I)
triggers the
TEST
(so it contains two calls from 377 from 503, with no
conditional
branch
inbetween), does this genuinely imply that the
calculation
will
never
halt?

Bear in mind that the two calls in question do not
necessarily
occur in
the same "virtual address space", that is to say
the two
calls can
[and
in the case of T_Hat(T_Hat) *do* ] occur at
/different
levels of
emulation/.   [Your trace notation obscures this
simple
fact,
making
everything appear to be in one single virtual
process,
when
it's
not.]

What do you think?  This seems to be your primary
intuition
that
triggered all this "refuting" activity, BUT IS IT
ACTUALLY
CORRECT?

Of course, you will say "All my intuitions are
correct by
definition -
I'm never wrong" but that doesn't make it true!  :)

Is TEST *SOUND* ?


Noted: still no response to this basic question.

Mike.

<.. snip non-response to question ..>

I'm not sure if that non-response was deliberate.  I
didn't ask
whether one specified implementation of [whatever]
exhibits
infinite
recursion!

In case it was just a misreading, here is the question
again.


   So...  what do you think.  Is the following test a
SOUND
test
for
   non-halting?

      TEST:  "monitor the simulation until there is a
function
              call to 377 from 503 a second time,
with no
conditional
              branch in-between"

It is much more generic than that.
(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.

Copyright 2020 Pete Olcott (I just wrote that algorithm
right
now).

OK, I always imagined the test would be more general than
just
checking specifically for calls to 377 from 503.  :)  No
problem on
that front.

I'm thinking this is probably the basis of your initial
intuition
that
you could actually detect and handle the type of
recursion in
your
fledgeling (at that time) halt decider design.

It is good that you've clarified the test, and yet it
seems
you're
reluctant to plainly say that you believe the test works!

logical necessity speaks for itself it doesn't need me
for a
cheerleader.


LOL.  I knew you'd do something like that.

OK, so you are saying that if your test detects the
behaviour
described, then it's a "logical necessity" that the input
being
examined is non-halting?

Yes that is what I am saying.

There - that wasn't so bad, was it?  :)


Can you find a counter-example?

Well, if it's a logical necessity I'm in for a hard time on
that
one...

But here's the point:  logical necessity absolutely /does/
need a
cheerleader!  Loads of things are "logically necessary" in
that
they
must logically be true, and yet they are not /obviously/
true.
That's
why we have proofs.

This would be one of those scenarios, where even if your
claim is
correct, it's not trivially obvious that it's correct, right?

Here is what we're saying:

TEST:
    If a calculation P(I) has a trace of steps
    (s0, s1, s2, s3, .....) and there are two steps s_i
    and s_j, such that si and sj are both unconditional
    branches from A to B, and none of the steps in-between
    s_i and s_j are conditional branches, THEN calculation
    P(I) never halts.

Well that's certainly not a "trivial restatement of word
meanings" or
similar, and so is not seen to correct just on a casual
glance.

So obviously where I'm going is : do you have a proof of
this?

Now I know you're not one for proofs, and maybe during the
course of
discussion such a proof will fall out (provided the
underlying
logic
is correct...)

So to start with, perhaps you can just give your thinking
as to
/why/
you believe it to be logically necessary?  [You clearly
didn't
wake up
one day and think "hey, what about TEST - oh! it's a logical
necessity, that's handy - I can use it in my halt decider!".
There
was something that led you to consider TEST, and having
considered
it,
you decided for whatever reason it was true...]


Mike.


Let's look at it a little simpler:
HERE:  // current location
  Instructions that cannot possibly exit a loop
THERE: goto HERE;

Can you see how this definitely loops?

I can - and if this was relevant there would be a straight
forward
proof that such code loops.

But this isn't like the scenario you are dealing with AT ALL!
What
you are showing here is a kind of "in-process" loop detection.
What
you need is some kind of recursive EMULATION detection.
(Emulation
works differently in this respect.)

I'm pretty sure I explained the difference in a post a
couple of
weeks
ago but you never responded.

We are trying to determine whether or not a specific sequence
of x86
machine code bytes specify an infinite loop as if this machine
code
was
a mathematical formalism.

The only thing that matters is: WHAT DO THE BYTES THEMSELVES
SAY?


Well, I understand that the code bytes that you presented, if
executed
by a processor within one single logical thread of execution,
would
never terminate - there is an obvious loop.

But that's ignoring the issue of RECURSION, where behaviour is
not so
simple.  So what's the next step?  (So far what you've said is no
justification for the RECUSION scenario, which is what you
TEST is
concerned with.)

Mike.


The sequences of instructions from HERE to THERE and HERE to HERE
are
from actual execution traces. The x86 emulator screens out all
dead
code
and only shows us the code that is actually reached.

-HERE:  // current location
-   Instructions that cannot possibly exit a loop
-THERE: goto HERE;

To form a mathematical proof on the basis of the x86 language
being
construed as a formal language we only have to derive the complete
list
of every instruction that can possibly exit the above loop and if
there
are none of these between the labels HERE and THERE then we know
that
the loop is infinite.

Like I said, that is ok for a "contiguous thread of execution",
i.e.
if an x86 processor starts at HERE, and then steps its execution,
executing the instructions, then the processor will go round and
round
the loop. The proof is easy.


The case for infinite recursion is similar.

No it's not.  The easy proof for the contiguous thread of execution
does not work in the case where there is recursion.  Or, put more
accurately, it works WITHIN A SINGLE CONTIGUOUS THREAD OF EXECUTION
(the obvious proof still works for this), but *NOT WHEN THE TRACE

Click here to read the complete article
Pages:1234
rocksolid light 0.7.2
clearneti2ptor