Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.c > #160193 > unrolled thread

Re: Infinite recursion detection criteria (correct C code)

Started byolcott <NoOne@NoWhere.com>
First post2021-04-18 12:19 -0500
Last post2021-04-19 10:40 -0500
Articles 20 — 7 participants

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 12:19 -0500
    Re: Infinite recursion detection criteria (correct C code) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 22:57 +0000
      Re: Infinite recursion detection criteria (correct C code) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-18 16:14 -0700
        Re: Infinite recursion detection criteria (correct C code) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 17:01 +0000
          Re: Infinite recursion detection criteria (correct C code) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-19 13:13 -0700
      Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 18:23 -0500
      Re: Infinite recursion detection criteria (correct C code) Jeff Barnett <jbb@notatt.com> - 2021-04-18 18:11 -0600
        Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 19:25 -0500
          Re: Infinite recursion detection criteria (correct C code) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 18:04 -0700
        Re: Infinite recursion detection criteria (correct C code) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-04-19 04:01 -0700
      Re: Infinite recursion detection criteria (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-18 20:13 -0500
        Re: Infinite recursion detection criteria (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-18 20:16 -0500
        Re: Infinite recursion detection criteria (agreement check) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 16:59 +0000
          Re: Infinite recursion detection criteria (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-19 12:27 -0500
            Re: Infinite recursion detection criteria (agreement check) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 17:40 +0000
      Re: Infinite recursion detection criteria (correct C code) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-04-19 04:06 -0700
    Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 21:16 -0500
      Re: Infinite recursion detection criteria (correct C code) Richard Damon <Richard@Damon-Family.org> - 2021-04-18 22:26 -0400
        Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 21:29 -0500
        Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-19 10:40 -0500

#160193 — Re: Infinite recursion detection criteria (correct C code)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 12:19 -0500
SubjectRe: Infinite recursion detection criteria (correct C code)
Message-ID<k9mdnakMZo6f9-H9nZ2dnUU7-T3NnZ2d@giganews.com>
On 4/18/2021 12:08 PM, Malcolm McLean wrote:
> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>> On 4/17/21 2:50 PM, olcott wrote:
>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>
>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>> has fudged
>>>>> this),
>>>>
>>>> It is not fudging to say that source code is interpreted rather than
>>>> compiled.
>>>
>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>> that is in the halt decider.
>>
>> Just remember that I have and continue to stipulate otherwise.
>>
> This is one of those things like insisting on putting the hat in the
> microwave before extracting the rabbit. It's legitimate in itself, but
> it's eccentric, and it opens the door wide open to cheating.
> 
> You can insist on x86 code instead of a Turing machine, you can even
> reference external subroutine calls in the code. But the arrangement
> means that is now extremely easy to use data that the Turing machine
> does not have.
> 

Look at it instead as C / x86 such that function X() in C that always 
simulates its input detects when itself is called in infinite recursion.

If the execution trace of function X() called by function Y() shows:
(1) Function X() is called twice in sequence from the same machine 
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().
then the function call from Y() to X() is infinitely recursive unless 
X() stops it.

Everything that has been alluded to as cheating is simply correct C code 
correctly deciding that it has been called in infinite recursion on the 
basis of examining the x86 execution trace of its caller according to 
the above criteria.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]


#160205

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-18 22:57 +0000
Message-ID<20210418152814.400@kylheku.com>
In reply to#160193
["Followup-To:" header set to comp.lang.c.]
On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>
>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>> has fudged
>>>>>> this),
>>>>>
>>>>> It is not fudging to say that source code is interpreted rather than
>>>>> compiled.
>>>>
>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>> that is in the halt decider.
>>>
>>> Just remember that I have and continue to stipulate otherwise.
>>>
>> This is one of those things like insisting on putting the hat in the
>> microwave before extracting the rabbit. It's legitimate in itself, but
>> it's eccentric, and it opens the door wide open to cheating.
>> 
>> You can insist on x86 code instead of a Turing machine, you can even
>> reference external subroutine calls in the code. But the arrangement
>> means that is now extremely easy to use data that the Turing machine
>> does not have.
>> 
>
> Look at it instead as C / x86 such that function X() in C that always 
> simulates its input detects when itself is called in infinite recursion.
>
> If the execution trace of function X() called by function Y() shows:
> (1) Function X() is called twice in sequence from the same machine 
> address of Y().
> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().
> then the function call from Y() to X() is infinitely recursive unless 
> X() stops it.

I have two remarks.


Remark 1:

This argument is irrefutable, because it is vacuously true.

Y has no power to stop the recursion because of (3). Therefore, the only
that there might be no recursion is if X stops it.

Thus, whenever (3) holds, the conclusion says, effectively, "the
function call is infinitely recursive, or else it is not infinitely
recursive", which is vacuously true.

THe only way we can disprove an argument is if we show that its
conclusion is false when the premises are true. If we hold the premises
true, (3) must be true since it is one of them, and in that situation,
the conclusion is vacuously true.

Remark 2:

There is no way for the premises to be true, and for there not to be
runaway recursion. Therefore the "unless X stops it" remark in the
conclusion is superfluous: it refers to an impossible situation.

Proof:

If all the premises are true, then (3) is true. Thus only X can stop
the recursion.

Hypothesis: suppose X does stop the recursion.

X is a function, which means it can only make a decision based on its
parameters and nothing else. Whenever it is called with the same
parameters, it performs the same computational steps. (2)
that X is called with the same parameters by Y.

Therefore if X stops the recursion, X does that on the first call
from Y. Y is not called again, and so there is no second call from
Y to X.

But this contradicts (1), which asserts that there are two calls to X.

Therefore, we must retract our hypothesis: X does not stop the
recursion. That leads to a contradiction.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [next] | [standalone]


#160206

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2021-04-18 16:14 -0700
Message-ID<8735vn18zq.fsf@nosuchdomain.example.com>
In reply to#160205
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> ["Followup-To:" header set to comp.lang.c.]

Why??

> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]


#160226

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-19 17:01 +0000
Message-ID<20210419100057.65@kylheku.com>
In reply to#160206
On 2021-04-18, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>> ["Followup-To:" header set to comp.lang.c.]
>
> Why??

My newsreader does that automatically; I usually don't pay attention to
it.

[toc] | [prev] | [next] | [standalone]


#160229

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2021-04-19 13:13 -0700
Message-ID<87y2deyqvu.fsf@nosuchdomain.example.com>
In reply to#160226
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> On 2021-04-18, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>>> ["Followup-To:" header set to comp.lang.c.]
>>
>> Why??
>
> My newsreader does that automatically; I usually don't pay attention to
> it.

Please start paying attention to it.  Stop cross-posting olcott-stuff
to comp.lang.c (or comp.lang.c++, or ...).

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]


#160207

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 18:23 -0500
Message-ID<B5CdnZ9rqLIfIuH9nZ2dnUU7-cvNnZ2d@giganews.com>
In reply to#160205
On 4/18/2021 5:57 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.lang.c.]
> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>
>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>>> has fudged
>>>>>>> this),
>>>>>>
>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>> compiled.
>>>>>
>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>> that is in the halt decider.
>>>>
>>>> Just remember that I have and continue to stipulate otherwise.
>>>>
>>> This is one of those things like insisting on putting the hat in the
>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>> it's eccentric, and it opens the door wide open to cheating.
>>>
>>> You can insist on x86 code instead of a Turing machine, you can even
>>> reference external subroutine calls in the code. But the arrangement
>>> means that is now extremely easy to use data that the Turing machine
>>> does not have.
>>>
>>
>> Look at it instead as C / x86 such that function X() in C that always
>> simulates its input detects when itself is called in infinite recursion.
>>
>> If the execution trace of function X() called by function Y() shows:
>> (1) Function X() is called twice in sequence from the same machine
>> address of Y().
>> (2) With the same parameters to X().
>> (3) With no conditional branch or indexed jump instructions in Y().
>> (4) With no function call returns from X().
>> then the function call from Y() to X() is infinitely recursive unless
>> X() stops it.
> 
> I have two remarks.
> 
> 
> Remark 1:
> 
> This argument is irrefutable, because it is vacuously true.
> 
> Y has no power to stop the recursion because of (3). Therefore, the only
> that there might be no recursion is if X stops it.
> 

void X(u32 P, i32 I)
{
  Simulate(P, I);
}

void Y(u32 P)
{
  X(P, P);
}

int main()
{
  X((u32)Y, (u32)Y);
}

When X() simulates the machine language of Y() and examines resulting 
execution trace after simulating each machine instruction of Y() then 
X() can apply the criteria provided in the prior answer to stop 
simulating Y() on the basis that Y() would otherwise cause X() have 
infinite execution.

Thus providing the software engineering basis that Halts() does 
correctly decide that it must abort the simulation of H_Hat() to prevent 
its own infinite execution.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160208

FromJeff Barnett <jbb@notatt.com>
Date2021-04-18 18:11 -0600
Message-ID<s5ihs4$fgp$1@dont-email.me>
In reply to#160205
On 4/18/2021 4:57 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.lang.c.]
> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>
>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>>> has fudged
>>>>>>> this),
>>>>>>
>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>> compiled.
>>>>>
>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>> that is in the halt decider.
>>>>
>>>> Just remember that I have and continue to stipulate otherwise.
>>>>
>>> This is one of those things like insisting on putting the hat in the
>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>> it's eccentric, and it opens the door wide open to cheating.
>>>
>>> You can insist on x86 code instead of a Turing machine, you can even
>>> reference external subroutine calls in the code. But the arrangement
>>> means that is now extremely easy to use data that the Turing machine
>>> does not have.
>>>
>>
>> Look at it instead as C / x86 such that function X() in C that always
>> simulates its input detects when itself is called in infinite recursion.
>>
>> If the execution trace of function X() called by function Y() shows:
>> (1) Function X() is called twice in sequence from the same machine
>> address of Y().
>> (2) With the same parameters to X().
>> (3) With no conditional branch or indexed jump instructions in Y().
>> (4) With no function call returns from X().
>> then the function call from Y() to X() is infinitely recursive unless
>> X() stops it.
> 
> I have two remarks.
> 
> 
> Remark 1:
> 
> This argument is irrefutable, because it is vacuously true.
> 
> Y has no power to stop the recursion because of (3). Therefore, the only
> that there might be no recursion is if X stops it.
> 
> Thus, whenever (3) holds, the conclusion says, effectively, "the
> function call is infinitely recursive, or else it is not infinitely
> recursive", which is vacuously true.
> 
> THe only way we can disprove an argument is if we show that its
> conclusion is false when the premises are true. If we hold the premises
> true, (3) must be true since it is one of them, and in that situation,
> the conclusion is vacuously true.
> 
> Remark 2:
> 
> There is no way for the premises to be true, and for there not to be
> runaway recursion. Therefore the "unless X stops it" remark in the
> conclusion is superfluous: it refers to an impossible situation.
> 
> Proof:
> 
> If all the premises are true, then (3) is true. Thus only X can stop
> the recursion.
> 
> Hypothesis: suppose X does stop the recursion.
> 
> X is a function, which means it can only make a decision based on its
> parameters and nothing else. Whenever it is called with the same
> parameters, it performs the same computational steps. (2)
> that X is called with the same parameters by Y.
> 
> Therefore if X stops the recursion, X does that on the first call
> from Y. Y is not called again, and so there is no second call from
> Y to X.
> 
> But this contradicts (1), which asserts that there are two calls to X.
> 
> Therefore, we must retract our hypothesis: X does not stop the
> recursion. That leads to a contradiction.

What about the following thoughts:

1) The architecture of the execution engine provides for traps 
(interrupts) to be signaled in cases of arithmetic errors such as divide 
by zero, under/over flow, etc. Thus, almost every arithmetic instruction 
is an instance of "conditional" execution. Also consider timer and 
external signal interrupts and it becomes quite clear that conditions 1 
thru 4 above need context in order to validate any inferences from them.

Interesting question given the use of a simulator: How much is really 
simulated?
-- 
Jeff Barnett

[toc] | [prev] | [next] | [standalone]


#160209

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 19:25 -0500
Message-ID<MridnQP9Rc55UOH9nZ2dnUU7-c3NnZ2d@giganews.com>
In reply to#160208
On 4/18/2021 7:11 PM, Jeff Barnett wrote:
> On 4/18/2021 4:57 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.lang.c.]
>> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>
>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I 
>>>>>>>> know PO
>>>>>>>> has fudged
>>>>>>>> this),
>>>>>>>
>>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>>> compiled.
>>>>>>
>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>>> that is in the halt decider.
>>>>>
>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>
>>>> This is one of those things like insisting on putting the hat in the
>>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>
>>>> You can insist on x86 code instead of a Turing machine, you can even
>>>> reference external subroutine calls in the code. But the arrangement
>>>> means that is now extremely easy to use data that the Turing machine
>>>> does not have.
>>>>
>>>
>>> Look at it instead as C / x86 such that function X() in C that always
>>> simulates its input detects when itself is called in infinite recursion.
>>>
>>> If the execution trace of function X() called by function Y() shows:
>>> (1) Function X() is called twice in sequence from the same machine
>>> address of Y().
>>> (2) With the same parameters to X().
>>> (3) With no conditional branch or indexed jump instructions in Y().
>>> (4) With no function call returns from X().
>>> then the function call from Y() to X() is infinitely recursive unless
>>> X() stops it.
>>
>> I have two remarks.
>>
>>
>> Remark 1:
>>
>> This argument is irrefutable, because it is vacuously true.
>>
>> Y has no power to stop the recursion because of (3). Therefore, the only
>> that there might be no recursion is if X stops it.
>>
>> Thus, whenever (3) holds, the conclusion says, effectively, "the
>> function call is infinitely recursive, or else it is not infinitely
>> recursive", which is vacuously true.
>>
>> THe only way we can disprove an argument is if we show that its
>> conclusion is false when the premises are true. If we hold the premises
>> true, (3) must be true since it is one of them, and in that situation,
>> the conclusion is vacuously true.
>>
>> Remark 2:
>>
>> There is no way for the premises to be true, and for there not to be
>> runaway recursion. Therefore the "unless X stops it" remark in the
>> conclusion is superfluous: it refers to an impossible situation.
>>
>> Proof:
>>
>> If all the premises are true, then (3) is true. Thus only X can stop
>> the recursion.
>>
>> Hypothesis: suppose X does stop the recursion.
>>
>> X is a function, which means it can only make a decision based on its
>> parameters and nothing else. Whenever it is called with the same
>> parameters, it performs the same computational steps. (2)
>> that X is called with the same parameters by Y.
>>
>> Therefore if X stops the recursion, X does that on the first call
>> from Y. Y is not called again, and so there is no second call from
>> Y to X.
>>
>> But this contradicts (1), which asserts that there are two calls to X.
>>
>> Therefore, we must retract our hypothesis: X does not stop the
>> recursion. That leads to a contradiction.
> 
> What about the following thoughts:
> 
> 1) The architecture of the execution engine provides for traps 
> (interrupts) to be signaled in cases of arithmetic errors such as divide 
> by zero, under/over flow, etc. Thus, almost every arithmetic instruction 
> is an instance of "conditional" execution. Also consider timer and 
> external signal interrupts and it becomes quite clear that conditions 1 
> thru 4 above need context in order to validate any inferences from them.

That is really great that is your very first 100% legitimate and 
technically correct reply to the actual technical question that was asked.

> 
> Interesting question given the use of a simulator: How much is really 
> simulated?

I will try to divide by zero and see how this is handled.
It looks like that blows up the simulator.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160210

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-04-18 18:04 -0700
Message-ID<s5iku0$bvf$1@gioia.aioe.org>
In reply to#160209
On 4/18/2021 5:25 PM, olcott wrote:
> On 4/18/2021 7:11 PM, Jeff Barnett wrote:
>> On 4/18/2021 4:57 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.lang.c.]
>>> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>
>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I 
>>>>>>>>> know PO
>>>>>>>>> has fudged
>>>>>>>>> this),
>>>>>>>>
>>>>>>>> It is not fudging to say that source code is interpreted rather 
>>>>>>>> than
>>>>>>>> compiled.
>>>>>>>
>>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the 
>>>>>>> version
>>>>>>> that is in the halt decider.
>>>>>>
>>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>>
>>>>> This is one of those things like insisting on putting the hat in the
>>>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>>
>>>>> You can insist on x86 code instead of a Turing machine, you can even
>>>>> reference external subroutine calls in the code. But the arrangement
>>>>> means that is now extremely easy to use data that the Turing machine
>>>>> does not have.
>>>>>
>>>>
>>>> Look at it instead as C / x86 such that function X() in C that always
>>>> simulates its input detects when itself is called in infinite 
>>>> recursion.
>>>>
>>>> If the execution trace of function X() called by function Y() shows:
>>>> (1) Function X() is called twice in sequence from the same machine
>>>> address of Y().
>>>> (2) With the same parameters to X().
>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>> (4) With no function call returns from X().
>>>> then the function call from Y() to X() is infinitely recursive unless
>>>> X() stops it.
>>>
>>> I have two remarks.
>>>
>>>
>>> Remark 1:
>>>
>>> This argument is irrefutable, because it is vacuously true.
>>>
>>> Y has no power to stop the recursion because of (3). Therefore, the only
>>> that there might be no recursion is if X stops it.
>>>
>>> Thus, whenever (3) holds, the conclusion says, effectively, "the
>>> function call is infinitely recursive, or else it is not infinitely
>>> recursive", which is vacuously true.
>>>
>>> THe only way we can disprove an argument is if we show that its
>>> conclusion is false when the premises are true. If we hold the premises
>>> true, (3) must be true since it is one of them, and in that situation,
>>> the conclusion is vacuously true.
>>>
>>> Remark 2:
>>>
>>> There is no way for the premises to be true, and for there not to be
>>> runaway recursion. Therefore the "unless X stops it" remark in the
>>> conclusion is superfluous: it refers to an impossible situation.
>>>
>>> Proof:
>>>
>>> If all the premises are true, then (3) is true. Thus only X can stop
>>> the recursion.
>>>
>>> Hypothesis: suppose X does stop the recursion.
>>>
>>> X is a function, which means it can only make a decision based on its
>>> parameters and nothing else. Whenever it is called with the same
>>> parameters, it performs the same computational steps. (2)
>>> that X is called with the same parameters by Y.
>>>
>>> Therefore if X stops the recursion, X does that on the first call
>>> from Y. Y is not called again, and so there is no second call from
>>> Y to X.
>>>
>>> But this contradicts (1), which asserts that there are two calls to X.
>>>
>>> Therefore, we must retract our hypothesis: X does not stop the
>>> recursion. That leads to a contradiction.
>>
>> What about the following thoughts:
>>
>> 1) The architecture of the execution engine provides for traps 
>> (interrupts) to be signaled in cases of arithmetic errors such as 
>> divide by zero, under/over flow, etc. Thus, almost every arithmetic 
>> instruction is an instance of "conditional" execution. Also consider 
>> timer and external signal interrupts and it becomes quite clear that 
>> conditions 1 thru 4 above need context in order to validate any 
>> inferences from them.
> 
> That is really great that is your very first 100% legitimate and 
> technically correct reply to the actual technical question that was asked.
> 
>>
>> Interesting question given the use of a simulator: How much is really 
>> simulated?
> 
> I will try to divide by zero and see how this is handled.
> It looks like that blows up the simulator.
> 

Wait a minute... Are you coding the simulator, or not?

[toc] | [prev] | [next] | [standalone]


#160217

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2021-04-19 04:01 -0700
Message-ID<86pmyqh72i.fsf@linuxsc.com>
In reply to#160208
Jeff Barnett <jbb@notatt.com> writes:

[...]

> What about the following thoughts:
>
> 1) The architecture of the execution engine provides for traps
> (interrupts) to be signaled in cases of arithmetic errors such as
> divide by zero, under/over flow, etc.  Thus, almost every arithmetic
> instruction is an instance of "conditional" execution.  Also
> consider timer and external signal interrupts and it becomes quite
> clear that conditions 1 thru 4 above need context in order to
> validate any inferences from them.
>
> Interesting question given the use of a simulator:  How much is
> really simulated?

Since neither the thoughts nor the discussion preceding them has
anything to do with the C programming language, they should be
posted somewhere else, and not in comp.lang.c.

[toc] | [prev] | [next] | [standalone]


#160211 — Re: Infinite recursion detection criteria (agreement check)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 20:13 -0500
SubjectRe: Infinite recursion detection criteria (agreement check)
Message-ID<HZednf4MHaCoROH9nZ2dnUU7-dPNnZ2d@giganews.com>
In reply to#160205
On 4/18/2021 5:57 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.lang.c.]
> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>
>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>>> has fudged
>>>>>>> this),
>>>>>>
>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>> compiled.
>>>>>
>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>> that is in the halt decider.
>>>>
>>>> Just remember that I have and continue to stipulate otherwise.
>>>>
>>> This is one of those things like insisting on putting the hat in the
>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>> it's eccentric, and it opens the door wide open to cheating.
>>>
>>> You can insist on x86 code instead of a Turing machine, you can even
>>> reference external subroutine calls in the code. But the arrangement
>>> means that is now extremely easy to use data that the Turing machine
>>> does not have.
>>>
>>
>> Look at it instead as C / x86 such that function X() in C that always
>> simulates its input detects when itself is called in infinite recursion.
>>
>> If the execution trace of function X() called by function Y() shows:
>> (1) Function X() is called twice in sequence from the same machine
>> address of Y().
>> (2) With the same parameters to X().
>> (3) With no conditional branch or indexed jump instructions in Y().
>> (4) With no function call returns from X().
>> then the function call from Y() to X() is infinitely recursive unless
>> X() stops it.
> 
> I have two remarks.
> 
> 
> Remark 1:
> 
> This argument is irrefutable, because it is vacuously true.
I am rephrasing what I am saying to make it more clear:

(1) Function X() is called twice in sequence from the same machine 
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().

void X(u32 P, i32 I)
{
  Simulate(P, I);
}

void Y(u32 P)
{
  X(P, P);
}

int main()
{
  X((u32)Y, (u32)Y);
}

When X() simulates the machine language of Y() and examines resulting 
execution trace after simulating each machine instruction of Y() then 
X() can apply the criteria provided in the above to stop simulating Y() 
on the basis that Y() would otherwise cause X() have infinite execution.

Do you agree with all that?

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160212 — Re: Infinite recursion detection criteria (agreement check)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 20:16 -0500
SubjectRe: Infinite recursion detection criteria (agreement check)
Message-ID<e9ednaGdfchBROH9nZ2dnUU7-dednZ2d@giganews.com>
In reply to#160211
On 4/18/2021 8:13 PM, olcott wrote:
> On 4/18/2021 5:57 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.lang.c.]
>> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>
>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I 
>>>>>>>> know PO
>>>>>>>> has fudged
>>>>>>>> this),
>>>>>>>
>>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>>> compiled.
>>>>>>
>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>>> that is in the halt decider.
>>>>>
>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>
>>>> This is one of those things like insisting on putting the hat in the
>>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>
>>>> You can insist on x86 code instead of a Turing machine, you can even
>>>> reference external subroutine calls in the code. But the arrangement
>>>> means that is now extremely easy to use data that the Turing machine
>>>> does not have.
>>>>
>>>
>>> Look at it instead as C / x86 such that function X() in C that always
>>> simulates its input detects when itself is called in infinite recursion.
>>>
>>> If the execution trace of function X() called by function Y() shows:
>>> (1) Function X() is called twice in sequence from the same machine
>>> address of Y().
>>> (2) With the same parameters to X().
>>> (3) With no conditional branch or indexed jump instructions in Y().
>>> (4) With no function call returns from X().
>>> then the function call from Y() to X() is infinitely recursive unless
>>> X() stops it.
>>
>> I have two remarks.
>>
>>
>> Remark 1:
>>
>> This argument is irrefutable, because it is vacuously true.


I am rephrasing what I am saying to make it more clear:

Infinite recursion detection criteria:
(1) Function X() is called twice in sequence from the same machine 
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().

void X(u32 P, i32 I)
{
   Simulate(P, I);
}

void Y(u32 P)
{
   X(P, P);
}

int main()
{
   X((u32)Y, (u32)Y);
}

When X() simulates the machine language of Y() and examines resulting 
execution trace after simulating each machine instruction of Y() then 
X() can apply the criteria provided in the above to stop simulating Y() 
on the basis that Y() would otherwise cause X() have infinite execution.

Do you agree with all that?


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160225 — Re: Infinite recursion detection criteria (agreement check)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-19 16:59 +0000
SubjectRe: Infinite recursion detection criteria (agreement check)
Message-ID<20210419093129.383@kylheku.com>
In reply to#160211
["Followup-To:" header set to comp.lang.c.]
On 2021-04-19, olcott <NoOne@NoWhere.com> wrote:
> On 4/18/2021 5:57 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.lang.c.]
>> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>
>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>>>> has fudged
>>>>>>>> this),
>>>>>>>
>>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>>> compiled.
>>>>>>
>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>>> that is in the halt decider.
>>>>>
>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>
>>>> This is one of those things like insisting on putting the hat in the
>>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>
>>>> You can insist on x86 code instead of a Turing machine, you can even
>>>> reference external subroutine calls in the code. But the arrangement
>>>> means that is now extremely easy to use data that the Turing machine
>>>> does not have.
>>>>
>>>
>>> Look at it instead as C / x86 such that function X() in C that always
>>> simulates its input detects when itself is called in infinite recursion.
>>>
>>> If the execution trace of function X() called by function Y() shows:
>>> (1) Function X() is called twice in sequence from the same machine
>>> address of Y().
>>> (2) With the same parameters to X().
>>> (3) With no conditional branch or indexed jump instructions in Y().
>>> (4) With no function call returns from X().
>>> then the function call from Y() to X() is infinitely recursive unless
>>> X() stops it.
>> 
>> I have two remarks.
>> 
>> 
>> Remark 1:
>> 
>> This argument is irrefutable, because it is vacuously true.
> I am rephrasing what I am saying to make it more clear:
>
> (1) Function X() is called twice in sequence from the same machine 
> address of Y().
> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().

These conditions imply runaway recursion. Since X was called with
certain arguments, and that resulted in Y being called, such that X can
be called again with those same arguments, it means that X doesn't stop
the recursion.

(I wouldn't say infinite recursion, since we are talking about a conrete
implementation with concepts like "machine address". It is actually
infinite if X and Y tail call each other, otherwise it is runaway
recursion that will exhaust the stack.)
>
> When X() simulates the machine language of Y() and examines resulting 
> execution trace

If X has access to accumulated instruction traces from a prior
invocation of X, then it is not a function. It is an imperative
procedure with side effects.

To be a function, X must instantiate a new trace context each time it is
called, which contains no prior traces.

If you'd like to discuss an imperative procedure in the context of
computability theoiry, it behooves you to convert it to an equivalent
function.

This is easily doable: you identify all of the state which the procedure
mutates, and turn that into a pure calculation, mapping the prior state
to the new state. Then you make the old state a function parameter, and
the new state part of the return value.

If you'd like X to have access to past execution traces, they must be
bundled in an argument, which Y passes to X. X can re turn the newly
updated execution traces back to Y, which can pass them to X again.
However, then we see that (2) is violated "with the same parameters
to X". If Y passes two different states to X with different execution
trace contents, (2) does not hold.

That's the point of the exercise! By insisting on pure functions, we
flush out errors of reasoning of this sort, whereby there are
"invisible" inputs that we re not taking into account.

Because all imperative procedures can be refactored into functions,
every theoretical result that we prove about functions holds for
imperative procedures. We do not lose any generality; rather, we gain
analytic ability.

[toc] | [prev] | [next] | [standalone]


#160227 — Re: Infinite recursion detection criteria (agreement check)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-19 12:27 -0500
SubjectRe: Infinite recursion detection criteria (agreement check)
Message-ID<SaSdnftHTa_xIOD9nZ2dnUU7-VnNnZ2d@giganews.com>
In reply to#160225
On 4/19/2021 11:59 AM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.lang.c.]
> On 2021-04-19, olcott <NoOne@NoWhere.com> wrote:
>> On 4/18/2021 5:57 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.lang.c.]
>>> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:
>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>
>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO
>>>>>>>>> has fudged
>>>>>>>>> this),
>>>>>>>>
>>>>>>>> It is not fudging to say that source code is interpreted rather than
>>>>>>>> compiled.
>>>>>>>
>>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the version
>>>>>>> that is in the halt decider.
>>>>>>
>>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>>
>>>>> This is one of those things like insisting on putting the hat in the
>>>>> microwave before extracting the rabbit. It's legitimate in itself, but
>>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>>
>>>>> You can insist on x86 code instead of a Turing machine, you can even
>>>>> reference external subroutine calls in the code. But the arrangement
>>>>> means that is now extremely easy to use data that the Turing machine
>>>>> does not have.
>>>>>
>>>>
>>>> Look at it instead as C / x86 such that function X() in C that always
>>>> simulates its input detects when itself is called in infinite recursion.
>>>>
>>>> If the execution trace of function X() called by function Y() shows:
>>>> (1) Function X() is called twice in sequence from the same machine
>>>> address of Y().
>>>> (2) With the same parameters to X().
>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>> (4) With no function call returns from X().
>>>> then the function call from Y() to X() is infinitely recursive unless
>>>> X() stops it.
>>>
>>> I have two remarks.
>>>
>>>
>>> Remark 1:
>>>
>>> This argument is irrefutable, because it is vacuously true.
>> I am rephrasing what I am saying to make it more clear:
>>
>> (1) Function X() is called twice in sequence from the same machine
>> address of Y().
>> (2) With the same parameters to X().
>> (3) With no conditional branch or indexed jump instructions in Y().
>> (4) With no function call returns from X().
> 
> These conditions imply runaway recursion. Since X was called with
> certain arguments, and that resulted in Y being called, such that X can
> be called again with those same arguments, it means that X doesn't stop
> the recursion.
> 
> (I wouldn't say infinite recursion, since we are talking about a conrete
> implementation with concepts like "machine address". It is actually
> infinite if X and Y tail call each other, otherwise it is runaway
> recursion that will exhaust the stack.)
>>
>> When X() simulates the machine language of Y() and examines resulting
>> execution trace
> 
> If X has access to accumulated instruction traces from a prior
> invocation of X, then it is not a function. It is an imperative
> procedure with side effects.
> 
> To be a function, X must instantiate a new trace context each time it is
> called, which contains no prior traces.
> 
> If you'd like to discuss an imperative procedure in the context of
> computability theoiry, it behooves you to convert it to an equivalent
> function.
> 
> This is easily doable: you identify all of the state which the procedure
> mutates, and turn that into a pure calculation, mapping the prior state
> to the new state. Then you make the old state a function parameter, and
> the new state part of the return value.
> 
> If you'd like X to have access to past execution traces, they must be
> bundled in an argument, which Y passes to X. X can re turn the newly
> updated execution traces back to Y, which can pass them to X again.
> However, then we see that (2) is violated "with the same parameters
> to X". If Y passes two different states to X with different execution
> trace contents, (2) does not hold.
> 
> That's the point of the exercise! By insisting on pure functions, we
> flush out errors of reasoning of this sort, whereby there are
> "invisible" inputs that we re not taking into account.
> 
> Because all imperative procedures can be refactored into functions,
> every theoretical result that we prove about functions holds for
> imperative procedures. We do not lose any generality; rather, we gain
> analytic ability.
> 

Although it may be true that all pure functions are computations it is 
apparently not true that computations are limited to only pure functions.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160228 — Re: Infinite recursion detection criteria (agreement check)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-19 17:40 +0000
SubjectRe: Infinite recursion detection criteria (agreement check)
Message-ID<20210419103306.292@kylheku.com>
In reply to#160227
On 2021-04-19, olcott <NoOne@NoWhere.com> wrote:
> Although it may be true that all pure functions are computations it is 
> apparently not true that computations are limited to only pure functions.

In the context in which we find ourselves, "computation" and "pure
function" are synonymous. A computation is a transformation of a
specific input (that is defined in every detail, down to the last bit)
to an output.

The only way in which we can regard an imperative procedure as a
computation is by regarding regard the global, mutating state which it
works with to be part of the input.

Note that I am not looking for comments in regard to what I am writing
here; I am simply a messenger, passing on a small bit of standard
education that you are lacking.

I didn't invent that education, so if you have a problem with it, I
invite you to take it up with the tomes laying on the shelves of your
nearest computer science or mathematics library.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [next] | [standalone]


#160218

FromTim Rentsch <tr.17687@z991.linuxsc.com>
Date2021-04-19 04:06 -0700
Message-ID<86lf9eh6tw.fsf@linuxsc.com>
In reply to#160205
Kaz Kylheku <563-365-8930@kylheku.com> writes:

> On 2021-04-18, olcott <NoOne@NoWhere.com> wrote:

[...]

> I have two remarks.  [...]

If you are going to keep responding to this idiot, please limit
the posted responses to newsgroups where they are topical, which
does not include either comp.lang.c or comp.lang.c++.

[toc] | [prev] | [next] | [standalone]


#160213

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 21:16 -0500
Message-ID<_aGdnZQz64mFdeH9nZ2dnUU7-QGdnZ2d@giganews.com>
In reply to#160193
On 4/18/2021 9:13 PM, Richard Damon wrote:
> On 4/18/21 9:27 PM, olcott wrote:
>> On 4/18/2021 6:35 PM, Richard Damon wrote:
>>> On 4/18/21 7:16 PM, olcott wrote:
>>>> On 4/18/2021 4:58 PM, Richard Damon wrote:
>>>>> On 4/18/21 5:43 PM, olcott wrote:
>>>>>> On 4/18/2021 4:37 PM, Richard Damon wrote:
>>>>>>> On 4/18/21 4:17 PM, olcott wrote:
>>>>>>>> On 4/18/2021 2:59 PM, Richard Damon wrote:
>>>>>>>>> On 4/18/21 3:43 PM, olcott wrote:
>>>>>>>>>> On 4/18/2021 2:36 PM, Richard Damon wrote:
>>>>>>>>>>> On 4/18/21 1:19 PM, olcott wrote:
>>>>>>>>>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>>>>>>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>>>>>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>>>>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>>>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat
>>>>>>>>>>>>>>>>> itself (I
>>>>>>>>>>>>>>>>> know PO
>>>>>>>>>>>>>>>>> has fudged
>>>>>>>>>>>>>>>>> this),
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> It is not fudging to say that source code is interpreted
>>>>>>>>>>>>>>>> rather
>>>>>>>>>>>>>>>> than
>>>>>>>>>>>>>>>> compiled.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Just remember that H^ has a COPY of halt, not a 'call' to the
>>>>>>>>>>>>>>> version
>>>>>>>>>>>>>>> that is in the halt decider.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Just remember that I have and continue to stipulate otherwise.
>>>>>>>>>>>>>>
>>>>>>>>>>>>> This is one of those things like insisting on putting the
>>>>>>>>>>>>> hat in
>>>>>>>>>>>>> the
>>>>>>>>>>>>> microwave before extracting the rabbit. It's legitimate in
>>>>>>>>>>>>> itself,
>>>>>>>>>>>>> but
>>>>>>>>>>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>>>>>>>>>>
>>>>>>>>>>>>> You can insist on x86 code instead of a Turing machine, you can
>>>>>>>>>>>>> even
>>>>>>>>>>>>> reference external subroutine calls in the code. But the
>>>>>>>>>>>>> arrangement
>>>>>>>>>>>>> means that is now extremely easy to use data that the Turing
>>>>>>>>>>>>> machine
>>>>>>>>>>>>> does not have.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Look at it instead as C / x86 such that function X() in C that
>>>>>>>>>>>> always
>>>>>>>>>>>> simulates its input detects when itself is called in infinite
>>>>>>>>>>>> recursion.
>>>>>>>>>>>>
>>>>>>>>>>>> If the execution trace of function X() called by function Y()
>>>>>>>>>>>> shows:
>>>>>>>>>>>> (1) Function X() is called twice in sequence from the same
>>>>>>>>>>>> machine
>>>>>>>>>>>> address of Y().
>>>>>>>>>>>> (2) With the same parameters to X().
>>>>>>>>>>>> (3) With no conditional branch or indexed jump instructions in
>>>>>>>>>>>> Y().
>>>>>>>>>>>> (4) With no function call returns from X().
>>>>>>>>>>>> then the function call from Y() to X() is infinitely recursive
>>>>>>>>>>>> unless
>>>>>>>>>>>> X() stops it.
>>>>>>>>>>>>
>>>>>>>>>>>> Everything that has been alluded to as cheating is simply
>>>>>>>>>>>> correct C
>>>>>>>>>>>> code
>>>>>>>>>>>> correctly deciding that it has been called in infinite
>>>>>>>>>>>> recursion on
>>>>>>>>>>>> the
>>>>>>>>>>>> basis of examining the x86 execution trace of its caller
>>>>>>>>>>>> according to
>>>>>>>>>>>> the above criteria.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> The problem here is you are ignoring the definition of
>>>>>>>>>>> Computations.
>>>>>>>>>>
>>>>>>>>>> This is not a problem at all because I am only referring to the
>>>>>>>>>> simple
>>>>>>>>>> fact that my C code does do what I claim that it does do.
>>>>>>>>>
>>>>>>>>> No, you CLAIM that you are proving an error in Theories about
>>>>>>>>> Computation Theory. If you don't follow the rules of Computation
>>>>>>>>> Theory
>>>>>>>>> that is not true.
>>>>>>>>>>
>>>>>>>>>> The commercial purpose of a halt decider is to detect programs
>>>>>>>>>> that
>>>>>>>>>> would not otherwise halt and abort these programs to prevent
>>>>>>>>>> things
>>>>>>>>>> such
>>>>>>>>>> as a denial-of-service attack.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> But that is not the purpose of the Halting Theory of Conventional
>>>>>>>>> Computaiton Theory.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> My C code proves that the conventional halting problem
>>>>>>>>>> undecidability
>>>>>>>>>> proof counter-example does not prevent such a denial-of-service
>>>>>>>>>> attack
>>>>>>>>>> program from being created.
>>>>>>>>>
>>>>>>>>> The Conventional Halting Problem never claimed to prevent DOS
>>>>>>>>> attacks.
>>>>>>>>>
>>>>>>>>> It claimed that we can not always predict if a given potentially
>>>>>>>>> long
>>>>>>>>> running computation will eventually end.
>>>>>>>>>
>>>>>>>>
>>>>>>>> That a program X can correctly decide whether or not another
>>>>>>>> program Y
>>>>>>>> is calling X in what would otherwise be infinite recursion <is>
>>>>>>>> computationally equivalent to a halt decider whether you understand
>>>>>>>> this
>>>>>>>> or not.
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> Wrong. The fact that when Y() calls X() that X() will decide to limit
>>>>>>> the recursion makes Y() not have infinite-recursion.
>>>>>>>
>>>>>>> The fact that the outer X() can't deduce this properly is a
>>>>>>> failure of
>>>>>>> X().
>>>>>>>
>>>>>>
>>>>>> Yes of source you say very stupid things like this when you merely
>>>>>> glance at a few of my words before artificicially contriving a what
>>>>>> might appear to be a rebuttal to someone that is hardly paying any
>>>>>> attention at all.
>>>>>>
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>
>>>>>
>>>>> We don't care about 'otherwise...'
>>>>
>>>> "Otherwise" is an integral part of the criteria, if you don't care about
>>>> otherwise then you are simply ignoring my criteria rather than
>>>> critiquing it.
>>>>
>>>> I will try to formalize it a little better:
>>>> Does X() stop simulating Y() on the basis of:
>>>>
>>>> (1) Function X() is called twice in sequence from the same machine
>>>> address of Y().
>>>> (2) With the same parameters to X().
>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>> (4) With no function call returns from X().
>>>>
>>>
>>> It becomes a matter of definition, and because of the context of your
>>> comments that context is fairly obvious, especially since it is present
>>> upthread.
>> void X(u32 P, i32 I)
>> {
>> Simulate(P, I);
>> }
>>
>> void Y(u32 P)
>> {
>> X(P, P);
>> }
>>
>> int main()
>> {
>> X((u32)Y, (u32)Y);
>> }
>>
>> When X() simulates the machine language of Y() and examines resulting
>> execution trace after simulating each machine instruction of Y() then
>> X() can apply the criteria provided in the above to stop simulating Y()
>> on the basis that Y() would otherwise cause X() have infinite execution.
>>
>> Do you agree with this?
>>
>>
> 
> With the code provided here, X has no conditions at all, 

No try again you are not paying close enough attention, it never says 
that X() has no conditional code.


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160214

FromRichard Damon <Richard@Damon-Family.org>
Date2021-04-18 22:26 -0400
Message-ID<IT5fI.31805$lyv9.30753@fx35.iad>
In reply to#160213
On 4/18/21 10:16 PM, olcott wrote:
> On 4/18/2021 9:13 PM, Richard Damon wrote:
>> On 4/18/21 9:27 PM, olcott wrote:
>>> On 4/18/2021 6:35 PM, Richard Damon wrote:
>>>> On 4/18/21 7:16 PM, olcott wrote:
>>>>> On 4/18/2021 4:58 PM, Richard Damon wrote:
>>>>>> On 4/18/21 5:43 PM, olcott wrote:
>>>>>>> On 4/18/2021 4:37 PM, Richard Damon wrote:
>>>>>>>> On 4/18/21 4:17 PM, olcott wrote:
>>>>>>>>> On 4/18/2021 2:59 PM, Richard Damon wrote:
>>>>>>>>>> On 4/18/21 3:43 PM, olcott wrote:
>>>>>>>>>>> On 4/18/2021 2:36 PM, Richard Damon wrote:
>>>>>>>>>>>> On 4/18/21 1:19 PM, olcott wrote:
>>>>>>>>>>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>>>>>>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>>>>>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>>>>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat
>>>>>>>>>>>>>>>>>> itself (I
>>>>>>>>>>>>>>>>>> know PO
>>>>>>>>>>>>>>>>>> has fudged
>>>>>>>>>>>>>>>>>> this),
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> It is not fudging to say that source code is interpreted
>>>>>>>>>>>>>>>>> rather
>>>>>>>>>>>>>>>>> than
>>>>>>>>>>>>>>>>> compiled.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Just remember that H^ has a COPY of halt, not a 'call'
>>>>>>>>>>>>>>>> to the
>>>>>>>>>>>>>>>> version
>>>>>>>>>>>>>>>> that is in the halt decider.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Just remember that I have and continue to stipulate
>>>>>>>>>>>>>>> otherwise.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>> This is one of those things like insisting on putting the
>>>>>>>>>>>>>> hat in
>>>>>>>>>>>>>> the
>>>>>>>>>>>>>> microwave before extracting the rabbit. It's legitimate in
>>>>>>>>>>>>>> itself,
>>>>>>>>>>>>>> but
>>>>>>>>>>>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> You can insist on x86 code instead of a Turing machine,
>>>>>>>>>>>>>> you can
>>>>>>>>>>>>>> even
>>>>>>>>>>>>>> reference external subroutine calls in the code. But the
>>>>>>>>>>>>>> arrangement
>>>>>>>>>>>>>> means that is now extremely easy to use data that the Turing
>>>>>>>>>>>>>> machine
>>>>>>>>>>>>>> does not have.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Look at it instead as C / x86 such that function X() in C that
>>>>>>>>>>>>> always
>>>>>>>>>>>>> simulates its input detects when itself is called in infinite
>>>>>>>>>>>>> recursion.
>>>>>>>>>>>>>
>>>>>>>>>>>>> If the execution trace of function X() called by function Y()
>>>>>>>>>>>>> shows:
>>>>>>>>>>>>> (1) Function X() is called twice in sequence from the same
>>>>>>>>>>>>> machine
>>>>>>>>>>>>> address of Y().
>>>>>>>>>>>>> (2) With the same parameters to X().
>>>>>>>>>>>>> (3) With no conditional branch or indexed jump instructions in
>>>>>>>>>>>>> Y().
>>>>>>>>>>>>> (4) With no function call returns from X().
>>>>>>>>>>>>> then the function call from Y() to X() is infinitely recursive
>>>>>>>>>>>>> unless
>>>>>>>>>>>>> X() stops it.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Everything that has been alluded to as cheating is simply
>>>>>>>>>>>>> correct C
>>>>>>>>>>>>> code
>>>>>>>>>>>>> correctly deciding that it has been called in infinite
>>>>>>>>>>>>> recursion on
>>>>>>>>>>>>> the
>>>>>>>>>>>>> basis of examining the x86 execution trace of its caller
>>>>>>>>>>>>> according to
>>>>>>>>>>>>> the above criteria.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> The problem here is you are ignoring the definition of
>>>>>>>>>>>> Computations.
>>>>>>>>>>>
>>>>>>>>>>> This is not a problem at all because I am only referring to the
>>>>>>>>>>> simple
>>>>>>>>>>> fact that my C code does do what I claim that it does do.
>>>>>>>>>>
>>>>>>>>>> No, you CLAIM that you are proving an error in Theories about
>>>>>>>>>> Computation Theory. If you don't follow the rules of Computation
>>>>>>>>>> Theory
>>>>>>>>>> that is not true.
>>>>>>>>>>>
>>>>>>>>>>> The commercial purpose of a halt decider is to detect programs
>>>>>>>>>>> that
>>>>>>>>>>> would not otherwise halt and abort these programs to prevent
>>>>>>>>>>> things
>>>>>>>>>>> such
>>>>>>>>>>> as a denial-of-service attack.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> But that is not the purpose of the Halting Theory of Conventional
>>>>>>>>>> Computaiton Theory.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>> My C code proves that the conventional halting problem
>>>>>>>>>>> undecidability
>>>>>>>>>>> proof counter-example does not prevent such a denial-of-service
>>>>>>>>>>> attack
>>>>>>>>>>> program from being created.
>>>>>>>>>>
>>>>>>>>>> The Conventional Halting Problem never claimed to prevent DOS
>>>>>>>>>> attacks.
>>>>>>>>>>
>>>>>>>>>> It claimed that we can not always predict if a given potentially
>>>>>>>>>> long
>>>>>>>>>> running computation will eventually end.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> That a program X can correctly decide whether or not another
>>>>>>>>> program Y
>>>>>>>>> is calling X in what would otherwise be infinite recursion <is>
>>>>>>>>> computationally equivalent to a halt decider whether you
>>>>>>>>> understand
>>>>>>>>> this
>>>>>>>>> or not.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Wrong. The fact that when Y() calls X() that X() will decide to
>>>>>>>> limit
>>>>>>>> the recursion makes Y() not have infinite-recursion.
>>>>>>>>
>>>>>>>> The fact that the outer X() can't deduce this properly is a
>>>>>>>> failure of
>>>>>>>> X().
>>>>>>>>
>>>>>>>
>>>>>>> Yes of source you say very stupid things like this when you merely
>>>>>>> glance at a few of my words before artificicially contriving a what
>>>>>>> might appear to be a rebuttal to someone that is hardly paying any
>>>>>>> attention at all.
>>>>>>>
>>>>>>> what would otherwise be infinite recursion
>>>>>>> what would otherwise be infinite recursion
>>>>>>> what would otherwise be infinite recursion
>>>>>>> what would otherwise be infinite recursion
>>>>>>
>>>>>>
>>>>>> We don't care about 'otherwise...'
>>>>>
>>>>> "Otherwise" is an integral part of the criteria, if you don't care
>>>>> about
>>>>> otherwise then you are simply ignoring my criteria rather than
>>>>> critiquing it.
>>>>>
>>>>> I will try to formalize it a little better:
>>>>> Does X() stop simulating Y() on the basis of:
>>>>>
>>>>> (1) Function X() is called twice in sequence from the same machine
>>>>> address of Y().
>>>>> (2) With the same parameters to X().
>>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>>> (4) With no function call returns from X().
>>>>>
>>>>
>>>> It becomes a matter of definition, and because of the context of your
>>>> comments that context is fairly obvious, especially since it is present
>>>> upthread.
>>> void X(u32 P, i32 I)
>>> {
>>> Simulate(P, I);
>>> }
>>>
>>> void Y(u32 P)
>>> {
>>> X(P, P);
>>> }
>>>
>>> int main()
>>> {
>>> X((u32)Y, (u32)Y);
>>> }
>>>
>>> When X() simulates the machine language of Y() and examines resulting
>>> execution trace after simulating each machine instruction of Y() then
>>> X() can apply the criteria provided in the above to stop simulating Y()
>>> on the basis that Y() would otherwise cause X() have infinite execution.
>>>
>>> Do you agree with this?
>>>
>>>
>>
>> With the code provided here, X has no conditions at all, 
> 
> No try again you are not paying close enough attention, it never says
> that X() has no conditional code.
> 
> 

But X() was defined as:

>>> void X(u32 P, i32 I)
>>> {
>>> Simulate(P, I);
>>> }
>>>

You have previous defined that Simulate is a regular UTM function.

I see no conditional in that function.


Your logic in inconsistent.

[toc] | [prev] | [next] | [standalone]


#160215

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 21:29 -0500
Message-ID<3vidnZPWgbNjd-H9nZ2dnUU7-WGdnZ2d@giganews.com>
In reply to#160214
On 4/18/2021 9:26 PM, Richard Damon wrote:
> On 4/18/21 10:16 PM, olcott wrote:
>> On 4/18/2021 9:13 PM, Richard Damon wrote:
>>> On 4/18/21 9:27 PM, olcott wrote:
>>>> On 4/18/2021 6:35 PM, Richard Damon wrote:
>>>>> On 4/18/21 7:16 PM, olcott wrote:
>>>>>> On 4/18/2021 4:58 PM, Richard Damon wrote:
>>>>>>> On 4/18/21 5:43 PM, olcott wrote:
>>>>>>>> On 4/18/2021 4:37 PM, Richard Damon wrote:
>>>>>>>>> On 4/18/21 4:17 PM, olcott wrote:
>>>>>>>>>> On 4/18/2021 2:59 PM, Richard Damon wrote:
>>>>>>>>>>> On 4/18/21 3:43 PM, olcott wrote:
>>>>>>>>>>>> On 4/18/2021 2:36 PM, Richard Damon wrote:
>>>>>>>>>>>>> On 4/18/21 1:19 PM, olcott wrote:
>>>>>>>>>>>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>>>>>>>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>>>>>>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>>>>>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat
>>>>>>>>>>>>>>>>>>> itself (I
>>>>>>>>>>>>>>>>>>> know PO
>>>>>>>>>>>>>>>>>>> has fudged
>>>>>>>>>>>>>>>>>>> this),
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> It is not fudging to say that source code is interpreted
>>>>>>>>>>>>>>>>>> rather
>>>>>>>>>>>>>>>>>> than
>>>>>>>>>>>>>>>>>> compiled.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Just remember that H^ has a COPY of halt, not a 'call'
>>>>>>>>>>>>>>>>> to the
>>>>>>>>>>>>>>>>> version
>>>>>>>>>>>>>>>>> that is in the halt decider.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Just remember that I have and continue to stipulate
>>>>>>>>>>>>>>>> otherwise.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> This is one of those things like insisting on putting the
>>>>>>>>>>>>>>> hat in
>>>>>>>>>>>>>>> the
>>>>>>>>>>>>>>> microwave before extracting the rabbit. It's legitimate in
>>>>>>>>>>>>>>> itself,
>>>>>>>>>>>>>>> but
>>>>>>>>>>>>>>> it's eccentric, and it opens the door wide open to cheating.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> You can insist on x86 code instead of a Turing machine,
>>>>>>>>>>>>>>> you can
>>>>>>>>>>>>>>> even
>>>>>>>>>>>>>>> reference external subroutine calls in the code. But the
>>>>>>>>>>>>>>> arrangement
>>>>>>>>>>>>>>> means that is now extremely easy to use data that the Turing
>>>>>>>>>>>>>>> machine
>>>>>>>>>>>>>>> does not have.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Look at it instead as C / x86 such that function X() in C that
>>>>>>>>>>>>>> always
>>>>>>>>>>>>>> simulates its input detects when itself is called in infinite
>>>>>>>>>>>>>> recursion.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> If the execution trace of function X() called by function Y()
>>>>>>>>>>>>>> shows:
>>>>>>>>>>>>>> (1) Function X() is called twice in sequence from the same
>>>>>>>>>>>>>> machine
>>>>>>>>>>>>>> address of Y().
>>>>>>>>>>>>>> (2) With the same parameters to X().
>>>>>>>>>>>>>> (3) With no conditional branch or indexed jump instructions in
>>>>>>>>>>>>>> Y().
>>>>>>>>>>>>>> (4) With no function call returns from X().
>>>>>>>>>>>>>> then the function call from Y() to X() is infinitely recursive
>>>>>>>>>>>>>> unless
>>>>>>>>>>>>>> X() stops it.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Everything that has been alluded to as cheating is simply
>>>>>>>>>>>>>> correct C
>>>>>>>>>>>>>> code
>>>>>>>>>>>>>> correctly deciding that it has been called in infinite
>>>>>>>>>>>>>> recursion on
>>>>>>>>>>>>>> the
>>>>>>>>>>>>>> basis of examining the x86 execution trace of its caller
>>>>>>>>>>>>>> according to
>>>>>>>>>>>>>> the above criteria.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> The problem here is you are ignoring the definition of
>>>>>>>>>>>>> Computations.
>>>>>>>>>>>>
>>>>>>>>>>>> This is not a problem at all because I am only referring to the
>>>>>>>>>>>> simple
>>>>>>>>>>>> fact that my C code does do what I claim that it does do.
>>>>>>>>>>>
>>>>>>>>>>> No, you CLAIM that you are proving an error in Theories about
>>>>>>>>>>> Computation Theory. If you don't follow the rules of Computation
>>>>>>>>>>> Theory
>>>>>>>>>>> that is not true.
>>>>>>>>>>>>
>>>>>>>>>>>> The commercial purpose of a halt decider is to detect programs
>>>>>>>>>>>> that
>>>>>>>>>>>> would not otherwise halt and abort these programs to prevent
>>>>>>>>>>>> things
>>>>>>>>>>>> such
>>>>>>>>>>>> as a denial-of-service attack.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> But that is not the purpose of the Halting Theory of Conventional
>>>>>>>>>>> Computaiton Theory.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>> My C code proves that the conventional halting problem
>>>>>>>>>>>> undecidability
>>>>>>>>>>>> proof counter-example does not prevent such a denial-of-service
>>>>>>>>>>>> attack
>>>>>>>>>>>> program from being created.
>>>>>>>>>>>
>>>>>>>>>>> The Conventional Halting Problem never claimed to prevent DOS
>>>>>>>>>>> attacks.
>>>>>>>>>>>
>>>>>>>>>>> It claimed that we can not always predict if a given potentially
>>>>>>>>>>> long
>>>>>>>>>>> running computation will eventually end.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> That a program X can correctly decide whether or not another
>>>>>>>>>> program Y
>>>>>>>>>> is calling X in what would otherwise be infinite recursion <is>
>>>>>>>>>> computationally equivalent to a halt decider whether you
>>>>>>>>>> understand
>>>>>>>>>> this
>>>>>>>>>> or not.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Wrong. The fact that when Y() calls X() that X() will decide to
>>>>>>>>> limit
>>>>>>>>> the recursion makes Y() not have infinite-recursion.
>>>>>>>>>
>>>>>>>>> The fact that the outer X() can't deduce this properly is a
>>>>>>>>> failure of
>>>>>>>>> X().
>>>>>>>>>
>>>>>>>>
>>>>>>>> Yes of source you say very stupid things like this when you merely
>>>>>>>> glance at a few of my words before artificicially contriving a what
>>>>>>>> might appear to be a rebuttal to someone that is hardly paying any
>>>>>>>> attention at all.
>>>>>>>>
>>>>>>>> what would otherwise be infinite recursion
>>>>>>>> what would otherwise be infinite recursion
>>>>>>>> what would otherwise be infinite recursion
>>>>>>>> what would otherwise be infinite recursion
>>>>>>>
>>>>>>>
>>>>>>> We don't care about 'otherwise...'
>>>>>>
>>>>>> "Otherwise" is an integral part of the criteria, if you don't care
>>>>>> about
>>>>>> otherwise then you are simply ignoring my criteria rather than
>>>>>> critiquing it.
>>>>>>
>>>>>> I will try to formalize it a little better:
>>>>>> Does X() stop simulating Y() on the basis of:
>>>>>>
>>>>>> (1) Function X() is called twice in sequence from the same machine
>>>>>> address of Y().
>>>>>> (2) With the same parameters to X().
>>>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>>>> (4) With no function call returns from X().
>>>>>>
>>>>>
>>>>> It becomes a matter of definition, and because of the context of your
>>>>> comments that context is fairly obvious, especially since it is present
>>>>> upthread.
>>>> void X(u32 P, i32 I)
>>>> {
>>>> Simulate(P, I);
>>>> }
>>>>
>>>> void Y(u32 P)
>>>> {
>>>> X(P, P);
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> X((u32)Y, (u32)Y);
>>>> }
>>>>
>>>> When X() simulates the machine language of Y() and examines resulting
>>>> execution trace after simulating each machine instruction of Y() then
>>>> X() can apply the criteria provided in the above to stop simulating Y()
>>>> on the basis that Y() would otherwise cause X() have infinite execution.
>>>>
>>>> Do you agree with this?
>>>>
>>>>
>>>
>>> With the code provided here, X has no conditions at all,
>>
>> No try again you are not paying close enough attention, it never says
>> that X() has no conditional code.
>>
>>
> 
> But X() was defined as:
> 
>>>> void X(u32 P, i32 I)
>>>> {
>>>> Simulate(P, I);
>>>> }
>>>>
> 
> You have previous defined that Simulate is a regular UTM function.
> 
> I see no conditional in that function.
> 
> 
> Your logic in inconsistent.
> 

I have never ever defined X() as a UTM anything. X has always only been 
C code. You have to pay attention to what I am actually saying not what 
you think that I mean.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#160224

Fromolcott <NoOne@NoWhere.com>
Date2021-04-19 10:40 -0500
Message-ID<7cydnaHmarHHOeD9nZ2dnUU7-b3NnZ2d@giganews.com>
In reply to#160214
On 4/19/2021 10:28 AM, Richard Damon wrote:
> On 4/19/21 11:12 AM, olcott wrote:
>> On 4/19/2021 6:16 AM, Richard Damon wrote:
>>> On 4/18/21 10:26 PM, Richard Damon wrote:
>>>> On 4/18/21 10:16 PM, olcott wrote:
>>>>> On 4/18/2021 9:13 PM, Richard Damon wrote:
>>>>>> On 4/18/21 9:27 PM, olcott wrote:
>>>>>>> On 4/18/2021 6:35 PM, Richard Damon wrote:
>>>>>>>> On 4/18/21 7:16 PM, olcott wrote:
>>>>>>>>> On 4/18/2021 4:58 PM, Richard Damon wrote:
>>>>>>>>>> On 4/18/21 5:43 PM, olcott wrote:
>>>>>>>>>>> On 4/18/2021 4:37 PM, Richard Damon wrote:
>>>>>>>>>>>> On 4/18/21 4:17 PM, olcott wrote:
>>>>>>>>>>>>> On 4/18/2021 2:59 PM, Richard Damon wrote:
>>>>>>>>>>>>>> On 4/18/21 3:43 PM, olcott wrote:
>>>>>>>>>>>>>>> On 4/18/2021 2:36 PM, Richard Damon wrote:
>>>>>>>>>>>>>>>> On 4/18/21 1:19 PM, olcott wrote:
>>>>>>>>>>>>>>>>> On 4/18/2021 12:08 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>>>>> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote:
>>>>>>>>>>>>>>>>>>> On 4/18/2021 6:44 AM, Richard Damon wrote:
>>>>>>>>>>>>>>>>>>>> On 4/17/21 2:50 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote:
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>> Because H deals with a notation for H_Hat, not H_Hat
>>>>>>>>>>>>>>>>>>>>>> itself (I
>>>>>>>>>>>>>>>>>>>>>> know PO
>>>>>>>>>>>>>>>>>>>>>> has fudged
>>>>>>>>>>>>>>>>>>>>>> this),
>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>> It is not fudging to say that source code is
>>>>>>>>>>>>>>>>>>>>> interpreted
>>>>>>>>>>>>>>>>>>>>> rather
>>>>>>>>>>>>>>>>>>>>> than
>>>>>>>>>>>>>>>>>>>>> compiled.
>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>> Just remember that H^ has a COPY of halt, not a 'call'
>>>>>>>>>>>>>>>>>>>> to the
>>>>>>>>>>>>>>>>>>>> version
>>>>>>>>>>>>>>>>>>>> that is in the halt decider.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> Just remember that I have and continue to stipulate
>>>>>>>>>>>>>>>>>>> otherwise.
>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> This is one of those things like insisting on putting the
>>>>>>>>>>>>>>>>>> hat in
>>>>>>>>>>>>>>>>>> the
>>>>>>>>>>>>>>>>>> microwave before extracting the rabbit. It's legitimate in
>>>>>>>>>>>>>>>>>> itself,
>>>>>>>>>>>>>>>>>> but
>>>>>>>>>>>>>>>>>> it's eccentric, and it opens the door wide open to
>>>>>>>>>>>>>>>>>> cheating.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> You can insist on x86 code instead of a Turing machine,
>>>>>>>>>>>>>>>>>> you can
>>>>>>>>>>>>>>>>>> even
>>>>>>>>>>>>>>>>>> reference external subroutine calls in the code. But the
>>>>>>>>>>>>>>>>>> arrangement
>>>>>>>>>>>>>>>>>> means that is now extremely easy to use data that the
>>>>>>>>>>>>>>>>>> Turing
>>>>>>>>>>>>>>>>>> machine
>>>>>>>>>>>>>>>>>> does not have.
>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Look at it instead as C / x86 such that function X() in
>>>>>>>>>>>>>>>>> C that
>>>>>>>>>>>>>>>>> always
>>>>>>>>>>>>>>>>> simulates its input detects when itself is called in
>>>>>>>>>>>>>>>>> infinite
>>>>>>>>>>>>>>>>> recursion.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> If the execution trace of function X() called by
>>>>>>>>>>>>>>>>> function Y()
>>>>>>>>>>>>>>>>> shows:
>>>>>>>>>>>>>>>>> (1) Function X() is called twice in sequence from the same
>>>>>>>>>>>>>>>>> machine
>>>>>>>>>>>>>>>>> address of Y().
>>>>>>>>>>>>>>>>> (2) With the same parameters to X().
>>>>>>>>>>>>>>>>> (3) With no conditional branch or indexed jump
>>>>>>>>>>>>>>>>> instructions in
>>>>>>>>>>>>>>>>> Y().
>>>>>>>>>>>>>>>>> (4) With no function call returns from X().
>>>>>>>>>>>>>>>>> then the function call from Y() to X() is infinitely
>>>>>>>>>>>>>>>>> recursive
>>>>>>>>>>>>>>>>> unless
>>>>>>>>>>>>>>>>> X() stops it.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> Everything that has been alluded to as cheating is simply
>>>>>>>>>>>>>>>>> correct C
>>>>>>>>>>>>>>>>> code
>>>>>>>>>>>>>>>>> correctly deciding that it has been called in infinite
>>>>>>>>>>>>>>>>> recursion on
>>>>>>>>>>>>>>>>> the
>>>>>>>>>>>>>>>>> basis of examining the x86 execution trace of its caller
>>>>>>>>>>>>>>>>> according to
>>>>>>>>>>>>>>>>> the above criteria.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The problem here is you are ignoring the definition of
>>>>>>>>>>>>>>>> Computations.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> This is not a problem at all because I am only referring
>>>>>>>>>>>>>>> to the
>>>>>>>>>>>>>>> simple
>>>>>>>>>>>>>>> fact that my C code does do what I claim that it does do.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> No, you CLAIM that you are proving an error in Theories about
>>>>>>>>>>>>>> Computation Theory. If you don't follow the rules of
>>>>>>>>>>>>>> Computation
>>>>>>>>>>>>>> Theory
>>>>>>>>>>>>>> that is not true.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The commercial purpose of a halt decider is to detect
>>>>>>>>>>>>>>> programs
>>>>>>>>>>>>>>> that
>>>>>>>>>>>>>>> would not otherwise halt and abort these programs to prevent
>>>>>>>>>>>>>>> things
>>>>>>>>>>>>>>> such
>>>>>>>>>>>>>>> as a denial-of-service attack.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> But that is not the purpose of the Halting Theory of
>>>>>>>>>>>>>> Conventional
>>>>>>>>>>>>>> Computaiton Theory.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> My C code proves that the conventional halting problem
>>>>>>>>>>>>>>> undecidability
>>>>>>>>>>>>>>> proof counter-example does not prevent such a
>>>>>>>>>>>>>>> denial-of-service
>>>>>>>>>>>>>>> attack
>>>>>>>>>>>>>>> program from being created.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> The Conventional Halting Problem never claimed to prevent DOS
>>>>>>>>>>>>>> attacks.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> It claimed that we can not always predict if a given
>>>>>>>>>>>>>> potentially
>>>>>>>>>>>>>> long
>>>>>>>>>>>>>> running computation will eventually end.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> That a program X can correctly decide whether or not another
>>>>>>>>>>>>> program Y
>>>>>>>>>>>>> is calling X in what would otherwise be infinite recursion <is>
>>>>>>>>>>>>> computationally equivalent to a halt decider whether you
>>>>>>>>>>>>> understand
>>>>>>>>>>>>> this
>>>>>>>>>>>>> or not.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Wrong. The fact that when Y() calls X() that X() will decide to
>>>>>>>>>>>> limit
>>>>>>>>>>>> the recursion makes Y() not have infinite-recursion.
>>>>>>>>>>>>
>>>>>>>>>>>> The fact that the outer X() can't deduce this properly is a
>>>>>>>>>>>> failure of
>>>>>>>>>>>> X().
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Yes of source you say very stupid things like this when you
>>>>>>>>>>> merely
>>>>>>>>>>> glance at a few of my words before artificicially contriving a
>>>>>>>>>>> what
>>>>>>>>>>> might appear to be a rebuttal to someone that is hardly paying
>>>>>>>>>>> any
>>>>>>>>>>> attention at all.
>>>>>>>>>>>
>>>>>>>>>>> what would otherwise be infinite recursion
>>>>>>>>>>> what would otherwise be infinite recursion
>>>>>>>>>>> what would otherwise be infinite recursion
>>>>>>>>>>> what would otherwise be infinite recursion
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> We don't care about 'otherwise...'
>>>>>>>>>
>>>>>>>>> "Otherwise" is an integral part of the criteria, if you don't care
>>>>>>>>> about
>>>>>>>>> otherwise then you are simply ignoring my criteria rather than
>>>>>>>>> critiquing it.
>>>>>>>>>
>>>>>>>>> I will try to formalize it a little better:
>>>>>>>>> Does X() stop simulating Y() on the basis of:
>>>>>>>>>
>>>>>>>>> (1) Function X() is called twice in sequence from the same machine
>>>>>>>>> address of Y().
>>>>>>>>> (2) With the same parameters to X().
>>>>>>>>> (3) With no conditional branch or indexed jump instructions in Y().
>>>>>>>>> (4) With no function call returns from X().
>>>>>>>>>
>>>>>>>>
>>>>>>>> It becomes a matter of definition, and because of the context of
>>>>>>>> your
>>>>>>>> comments that context is fairly obvious, especially since it is
>>>>>>>> present
>>>>>>>> upthread.
>>>>>>> void X(u32 P, i32 I)
>>>>>>> {
>>>>>>> Simulate(P, I);
>>>>>>> }
>>>>>>>
>>>>>>> void Y(u32 P)
>>>>>>> {
>>>>>>> X(P, P);
>>>>>>> }
>>>>>>>
>>>>>>> int main()
>>>>>>> {
>>>>>>> X((u32)Y, (u32)Y);
>>>>>>> }
>>>>>>>
>>>>>>> When X() simulates the machine language of Y() and examines resulting
>>>>>>> execution trace after simulating each machine instruction of Y() then
>>>>>>> X() can apply the criteria provided in the above to stop
>>>>>>> simulating Y()
>>>>>>> on the basis that Y() would otherwise cause X() have infinite
>>>>>>> execution.
>>>>>>>
>>>>>>> Do you agree with this?
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> With the code provided here, X has no conditions at all,
>>>>>
>>>>> No try again you are not paying close enough attention, it never says
>>>>> that X() has no conditional code.
>>>>>
>>>>>
>>>>
>>>> But X() was defined as:
>>>>
>>>>>>> void X(u32 P, u32 I)
>>>>>>> {
>>>>>>> Simulate(P, I);
>>>>>>> }
>>>>>>>
>>>>
>>>> You have previous defined that Simulate is a regular UTM function.
>>>>
>>>> I see no conditional in that function.
>>>>
>>>>
>>>> Your logic in inconsistent.
>>>>
>>>
>>> I never said X was a UTM anything. READ THE THREAD. I said X had no
>>> conditions in it.
>>>
>>>
>>> See THIS comment upthread?
>>>>> No try again you are not paying close enough attention, it never says
>>>>> that X() has no conditional code.
>>>
>>>
>>> Maybe YOU should stop and read a bit more.
>>>
>>> Maybe you should also watch about reusing names that mean different
>>> things or tryng to hide code
>>>
>>
>> I never ever said that X() was any kind of UTM this whole analysis with
>> X() and Y() is strictly a C program that analyzes the x86 execution
>> trace of its simulation of the machine pointed to by P with data pointed
>> to by I.
>>
> 
> You sure seem to like fighting straw men.
> 
> This sub-thread was NOT about X being a UTM. It was about you talking
> about conditional execution inside X when you provided a definition of
> X() that hand NO conditional execution.
> 

Do you have OCD? You keep getting key points incorrectly.

These four points are examined as the basis of determining that Y() is 
calling X() in infinite recursion.

I never said that X() does not have conditional branch instructions.

I only said that they are not part of the basis for correctly deciding 
that Y() has called X() in infinite recursion.

It turns out that these four points are a sufficient condition for 
correctly deciding that Y() is calling X() in infinite recursion.

(1) Function X() is called twice in sequence from the same machine 
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().

The following code (including an x86 emulator) is written in "C"

void X(u32 P, u32 I)
{
   Simulate(P, I);
}

void Y(u32 P)
{
   X(P, P);
}

int main()
{
   X((u32)Y, (u32)Y);
}

When X() simulates the x86 machine language of Y() and examines 
resulting execution trace after simulating each machine instruction of 
Y() then X() can apply the criteria provided above to correctly decide 
to stop simulating Y() on the basis that Y() would otherwise cause X() 
have infinite execution.



-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [standalone]


Back to top | Article view | comp.lang.c


csiph-web