On 2/27/21 10:26 AM, olcott wrote:
On 2/27/2021 9:18 AM, Richard Damon wrote:
On 2/26/21 4:00 PM, olcott wrote:
On 2/26/2021 2:41 PM, Malcolm McLean wrote:
On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
(1) We know that every software function invoked with the same data >>>>>> mustYes, as long as by "data" we mean everything which the function reads, >>>>> not
have the same execution trace.
only parameters.
You don't need 4. If A calls itself with exactly the same data as it >>>>> was
(2) When a software function invokes itself this is recursive
invocation.
(3) When the second recursive invocation of a software function calls >>>>>> itself with the same data as the prior invocation then it must have >>>>>> the
same execution trace as the prior invocation.
(4) When the second recursive invocation of a software function calls >>>>>> itself with the same data has no conditional branch instructions
inbetween these two invocations then this is a case of infinite
recursion.
originally invoked with, then it must be infitely recursive, even if >>>>> there
are conditional branches. It always takes the same branches. The only >>>>> question is whether the first invocation makes the recursive call
(depending
how you are using the term "calls").
This would seem to be true.
Yes, you're right. But the caveat I would have is that this system is >>>>> wide open
(5) When the recursive invocation is replaced with a call to a
software
system that simulates the execution of the calling function with its >>>>>> same data, then this is equivalent to a recursive invocation.
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Does everyone agree?
to cheating, because it's hard to verify that Simulate() is not having >>>>> access to
data that varies by invocation level.
If we hypothetically assume that it is a "given" that Simulate() only
simulates its input then we should be able to conclude that any
invocation meeting the above conditions specifies the equivalent of
infinite recursion.
One important point is that these conclusions assume that the function
described actually exists and that (as stated) the 'software function'
is actually a true model of a mathematical function (i.e., all inputs
have been identified).
One key point is that if the function is NOT described as an actual
computation, but just as a description, then it is possible to make
contradictory or wrong conclusions if the function is not actually
finitely computable.
void Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
}
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Ignoring finite stack space then the above is infinitely recursive right?
Yes, because you haven't hit any of the limitations I mentioned.
Simulate is fully defined and can be seen to not depend on anything not declared as an input.
On 2/27/21 10:26 AM, olcott wrote:
On 2/27/2021 9:18 AM, Richard Damon wrote:
On 2/26/21 4:00 PM, olcott wrote:
On 2/26/2021 2:41 PM, Malcolm McLean wrote:
On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
(1) We know that every software function invoked with the same data >>>>>> mustYes, as long as by "data" we mean everything which the function reads, >>>>> not
have the same execution trace.
only parameters.
You don't need 4. If A calls itself with exactly the same data as it >>>>> was
(2) When a software function invokes itself this is recursive
invocation.
(3) When the second recursive invocation of a software function calls >>>>>> itself with the same data as the prior invocation then it must have >>>>>> the
same execution trace as the prior invocation.
(4) When the second recursive invocation of a software function calls >>>>>> itself with the same data has no conditional branch instructions
inbetween these two invocations then this is a case of infinite
recursion.
originally invoked with, then it must be infitely recursive, even if >>>>> there
are conditional branches. It always takes the same branches. The only >>>>> question is whether the first invocation makes the recursive call
(depending
how you are using the term "calls").
This would seem to be true.
Yes, you're right. But the caveat I would have is that this system is >>>>> wide open
(5) When the recursive invocation is replaced with a call to a
software
system that simulates the execution of the calling function with its >>>>>> same data, then this is equivalent to a recursive invocation.
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Does everyone agree?
to cheating, because it's hard to verify that Simulate() is not having >>>>> access to
data that varies by invocation level.
If we hypothetically assume that it is a "given" that Simulate() only
simulates its input then we should be able to conclude that any
invocation meeting the above conditions specifies the equivalent of
infinite recursion.
One important point is that these conclusions assume that the function
described actually exists and that (as stated) the 'software function'
is actually a true model of a mathematical function (i.e., all inputs
have been identified).
One key point is that if the function is NOT described as an actual
computation, but just as a description, then it is possible to make
contradictory or wrong conclusions if the function is not actually
finitely computable.
void Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
}
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Ignoring finite stack space then the above is infinitely recursive right?
Yes, because you haven't hit any of the limitations I mentioned.
Simulate is fully defined and can be seen to not depend on anything not declared as an input.
On 2/27/21 9:36 PM, olcott wrote:
On 2/27/2021 8:19 PM, Richard Damon wrote:
On 2/27/21 3:40 PM, olcott wrote:
On 2/27/2021 12:57 PM, Richard Damon wrote:
On 2/27/21 10:26 AM, olcott wrote:
On 2/27/2021 9:18 AM, Richard Damon wrote:
On 2/26/21 4:00 PM, olcott wrote:
On 2/26/2021 2:41 PM, Malcolm McLean wrote:
On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
(1) We know that every software function invoked with the same >>>>>>>>>> dataYes, as long as by "data" we mean everything which the function >>>>>>>>> reads,
must
have the same execution trace.
not
only parameters.
You don't need 4. If A calls itself with exactly the same data >>>>>>>>> as it
(2) When a software function invokes itself this is recursive >>>>>>>>>> invocation.
(3) When the second recursive invocation of a software function >>>>>>>>>> calls
itself with the same data as the prior invocation then it must >>>>>>>>>> have
the
same execution trace as the prior invocation.
(4) When the second recursive invocation of a software function >>>>>>>>>> calls
itself with the same data has no conditional branch instructions >>>>>>>>>> inbetween these two invocations then this is a case of infinite >>>>>>>>>> recursion.
was
originally invoked with, then it must be infitely recursive, >>>>>>>>> even if
there
are conditional branches. It always takes the same branches. The >>>>>>>>> only
question is whether the first invocation makes the recursive call >>>>>>>>> (depending
how you are using the term "calls").
This would seem to be true.
Yes, you're right. But the caveat I would have is that this
(5) When the recursive invocation is replaced with a call to a >>>>>>>>>> software
system that simulates the execution of the calling function >>>>>>>>>> with its
same data, then this is equivalent to a recursive invocation. >>>>>>>>>>
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Does everyone agree?
system is
wide open
to cheating, because it's hard to verify that Simulate() is not >>>>>>>>> having
access to
data that varies by invocation level.
If we hypothetically assume that it is a "given" that Simulate() >>>>>>>> only
simulates its input then we should be able to conclude that any >>>>>>>> invocation meeting the above conditions specifies the equivalent of >>>>>>>> infinite recursion.
One important point is that these conclusions assume that the
function
described actually exists and that (as stated) the 'software
function'
is actually a true model of a mathematical function (i.e., all inputs >>>>>>> have been identified).
One key point is that if the function is NOT described as an actual >>>>>>> computation, but just as a description, then it is possible to make >>>>>>> contradictory or wrong conclusions if the function is not actually >>>>>>> finitely computable.
void Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
}
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Ignoring finite stack space then the above is infinitely recursive >>>>>> right?
Yes, because you haven't hit any of the limitations I mentioned.
Simulate is fully defined and can be seen to not depend on anything not >>>>> declared as an input.
When simulate emulates the execution of the x86 machine language (shown >>>> below) then the execution trace of H_Hat() showing that Simulate() has >>>> been invoked a second time in sequence with the same input proves that >>>> H_Hat() is infinitely recursive. (Assuming that Simulate() only
simulates it input).
You are now getting on thin ice, since the code to Simulate isn't
provided, its obedience to the requirements isn't verifable.
I am not asking you to verify the code. The actual code and its full
execution trace is many hundreds of pages.
I am asking you whether or not code with the properties that I have
provided can be necessarily determined to be infinitely recursive.
First, a lot of the equivocation is because you have shown yourself in
the past to 'try to pull a fast one' by misusing quotes.
If the actual virtual execution path of the program under the simulation function is identical to that of the first program, then of course the
answer would be yes. The issue is that, based on past performance, you
are apt to some point in the future break one of those conditions and
wish to claim the answer has to be the same, but it doesn't.
// P has the machine address of H_Hat
void H_Hat2(u32 P)
{
Simulate(P, P);
}
_H_Hat()
[000008a8](01) 55 push ebp
[000008a9](02) 8bec mov ebp,esp
[000008ab](03) 8b4508 mov eax,[ebp+08]
[000008ae](01) 50 push eax
[000008af](03) 8b4d08 mov ecx,[ebp+08]
[000008b2](01) 51 push ecx
[000008b3](05) e8c0fbffff call 00000478
[000008b8](03) 83c408 add esp,+08
[000008bb](01) 5d pop ebp
[000008bc](01) c3 ret
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
Push instructions have pushed the value shown in their in the third
column. The two push instructions preceding the call to Simulate are its >>>> second and first parameters respectively.
...[000008a8][00011220][0001122c](01) 55 push ebp
...[000008a9][00011220][0001122c](02) 8bec mov ebp,esp
...[000008ab][00011220][0001122c](03) 8b4508 mov eax,[ebp+08]
...[000008ae][0001121c][000008a8](01) 50 push eax
...[000008af][0001121c][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][00011218][000008a8](01) 51 push ecx
Call Simulate(000008a8, 000008a8)
...[000008b3][00011214][000008b8](05) e8c0fbffff call 00000478 >>>>
...[000008a8][00011204][00011210](01) 55 push ebp
...[000008a9][00011204][00011210](02) 8bec mov ebp,esp
...[000008ab][00011204][00011210](03) 8b4508 mov eax,[ebp+08]
...[000008ae][00011200][000008a8](01) 50 push eax
...[000008af][00011200][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][000111fc][000008a8](01) 51 push ecx
Call Simulate(000008a8, 000008a8)
...[000008b3][000111f8][000008b8](05) e8c0fbffff call 00000478 >>>>
Now we can see that H_Hat's call to Simulate() causes H_Hat() to be
infinitely recursive because its execution trace shows two invocations >>>> of Simulate() from H_Hat() each with identical input.
Note here also that your trace become incomplete here, as we DON't have
a complete cycle, but need to work on assumptions of benign action of
the Simulate function.
Because the simulator only simulates it is functionally equivalent to
the original version shown above.
Yes. I don't care about your opinions on any of the other details. I
only want an objective assessment regarding whether or not the code that
I specified with the assumptions that I specified can be determined to
be necessarily infinitely recursive.
And as I said above, Yes, as long as your code meets the requirements
stated, and the usage is within those parameters, yes.
Note, the trace by itself is NOT sufficient, it needs to be combined
with the description and restriction of the simulator for it to provide
the 'proof' you are describing.
Note again, as you trimmed the remark, Simulate does NOT qualify as a
UTM equivalent as it ooes not run the simulation in an isolated memory
space, it mixing of the machine it is operationg on with the machine it
is simulating makes it unsuitable for that purpose.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 296 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 71:27:35 |
| Calls: | 6,656 |
| Calls today: | 2 |
| Files: | 12,201 |
| Messages: | 5,332,225 |
| Posted today: | 1 |