Does this criteria prove that Y calls X in infinite recursion?

[olcott]

#include <stdint.h>
typedef int(*ptr)();

int X(ptr P, ptr I)
{
P(I);
return 0;
}

int Y(ptr P)
{
X(P, P);
return 1;
}

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

Does this criteria prove that Y calls X in infinite recursion?
An examination its x86 machine language proves that Y calls X with its
same parameters and there are no conditional branch instructions between
the invocation of Y and its call to X.

_X()
[00001cf3] 55 push ebp
[00001cf4] 8bec mov ebp,esp
[00001cf6] 8b450c mov eax,[ebp+0c]
[00001cf9] 50 push eax ; push Y
[00001cfa] ff5508 call dword [ebp+08] ; call Y
[00001cfd] 83c404 add esp,+04
[00001d00] 33c0 xor eax,eax
[00001d02] 5d pop ebp
[00001d03] c3 ret
Size in bytes:(0017) [00001d03]

_Y()
[00001d13] 55 push ebp
[00001d14] 8bec mov ebp,esp
[00001d16] 8b4508 mov eax,[ebp+08]
[00001d19] 50 push eax ; push Y
[00001d1a] 8b4d08 mov ecx,[ebp+08]
[00001d1d] 51 push ecx ; push Y
[00001d1e] e8d0ffffff call 00001cf3 ; call X
[00001d23] 83c408 add esp,+08
[00001d26] b801000000 mov eax,00000001
[00001d2b] 5d pop ebp
[00001d2c] c3 ret
Size in bytes:(0026) [00001d2c]

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

[wij]

On Thu, 2024-02-01 at 11:17 -0600, olcott wrote:
> #include <stdint.h>
> typedef int(*ptr)();
>
> int X(ptr P, ptr I)
> {
>    P(I);
>    return 0;
> }
>
> int Y(ptr P)
> {
>    X(P, P);
>    return 1;
> }
>
> int main()
> {
>    X(Y, Y);
> }
>
> Does this criteria prove that Y calls X in infinite recursion?
> An examination its x86 machine language proves that Y calls X with
> its
> same parameters and there are no conditional branch instructions
> between
> the invocation of Y and its call to X.
>

There are several problems in this piece of program
I recommend this is posted in comp.lang.c

[olcott]

On 2/1/2024 8:31 PM, wij wrote:
> On Thu, 2024-02-01 at 11:17 -0600, olcott wrote:
>> #include <stdint.h>
>> typedef int(*ptr)();
>>
>> int X(ptr P, ptr I)
>> {
>>    P(I);
>>    return 0;
>> }
>>
>> int Y(ptr P)
>> {
>>    X(P, P);
>>    return 1;
>> }
>>
>> int main()
>> {
>>    X(Y, Y);
>> }
>>
>> Does this criteria prove that Y calls X in infinite recursion?
>> An examination its x86 machine language proves that Y calls X with
>> its
>> same parameters and there are no conditional branch instructions
>> between
>> the invocation of Y and its call to X.
>>
>
> There are several problems in this piece of program
> I recommend this is posted in comp.lang.c
>

It has been reviewed on another forum and agreed that:

You can easily do this by manually "expanding" the calls. X(Y,Y)
performs call P(I), where P=Y and I=Y, so it becomes Y(Y). This performs
call X(P, P), where P=Y. So it becomes X(Y,Y). So we are back to the
initial call.

[Richard Damon]

On 2/1/24 12:17 PM, olcott wrote:
> #include <stdint.h>
> typedef int(*ptr)();
>
> int X(ptr P, ptr I)
> {
>   P(I);
>   return 0;
> }
>
> int Y(ptr P)
> {
>   X(P, P);
>   return 1;
> }
>
> int main()
> {
>   X(Y, Y);
> }
>
> Does this criteria prove that Y calls X in infinite recursion?

Nope.

> An examination its x86 machine language proves that Y calls X with its
> same parameters and there are no conditional branch instructions between
> the invocation of Y and its call to X.

Which isn't a valid rule. The ACTUAL rule would be no conditional branch
in the FULL cycle to the point of repeating, thus Y calling X calling Y
is enough, or x calling y calling x.

Thus, when you try to expand to your "simulation" case, you need the
simulation to be also unconditional (and thus, NOT part of a decider
that might abort its simulation)

[Richard Damon]

So you need to look at BOTH X, and Y, not just Y.

And BOTH need to be without conditionals, so the fact that H might
decide to abort its simulation invalidates your criteria.

[Mikko]

On 2024-02-01 17:17:39 +0000, olcott said:

> #include <stdint.h>
> typedef int(*ptr)();
>
> int X(ptr P, ptr I)
> {
> P(I);
> return 0;
> }
>
> int Y(ptr P)
> {
> X(P, P);
> return 1;
> }
>
> int main()
> {
> X(Y, Y);
> }
>
> Does this criteria prove that Y calls X in infinite recursion?
> An examination its x86 machine language proves that Y calls X with its
> same parameters and there are no conditional branch instructions
> between the invocation of Y and its call to X.

The recursion is indirect so the criteria above are insufficient. The
folowing satisfies these criteria but there is no infinite recursion:

#include <stdint.h>
typedef int(*ptr)();

static int c = 3;

int X(ptr P, ptr I)
{

if (c-- > 0) P(I);

return 0;
}

int Y(ptr P)
{
X(P, P);
return 1;
}

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

You may compile that and examine the machine code but it is
actually easier to examine the C code.

--
Mikko

[olcott]

Both functions must be pure functions, thus globals are not allowed.

[Mikko]

It is allowed as the C language allows that and the criteria don't
prohibit.

The variable c is static, not global. With

int X(ptr P, ptr I)
{

static int c = 3;

  if (c-- > 0) P(I);
  return 0;
}

the same effect would be achieved.

--
Mikko

[Richard Damon]

Which is effectively violated by your H, that conditionally simulates
its input.

This conditional is equivalent to that global state.


The fact that you are trying to establish that ONE input could be
correctly detected doesn't show that the rule works for ALL inputs.

A proper condition for showing X/Y have infinite recursion requires
criteria on BOTH X and Y.

Changine X from calling to simulating isn't isomorphic unless the
simulation is UNCONDITIONAL, and that doesn't includes simulates until
..., only actual unconditional simulation.

Any "conditions" on the simulation become equivalent state passed from
invocations of X to its indirectly called X, which you are trying to
prohibit, because it shows the "trick" your H is trying to use.

Your H wants to presume the H it sees is somehow different then itself,
but it can't be and be the proof case.

[olcott]

*IT IS STIPULATED THAT X AND Y ARE PURE FUNCTIONS*
*IT IS STIPULATED THAT X AND Y ARE PURE FUNCTIONS*
*IT IS STIPULATED THAT X AND Y ARE PURE FUNCTIONS*

>
> The variable c is static, not global. With
>
> int X(ptr P, ptr I)
> {
>  static int c = 3;
>   if (c-- > 0) P(I);
>   return 0;
> }
>
> the same effect would be achieved.
>

--

[Richard Damon]

Then not applicable to your H.

Fallacy of proof by example being used to try to claim the general case.

[olcott]

*Your ADD prevents you from paying attention*
*I DID NOT MENTION ANY FREAKING H*
*The question is about X and Y*

[Mikko]

On 2024-02-01 17:17:39 +0000, olcott said:

OP does not stipulate that.

--
Mikko

[olcott]

Stipulate what?
You cannot erase what you are responding to.

[Richard Damon]

As a precursor for you comparing it to H.

Right?

Or do you stipulate that you will never try to migrate this observation
to your Halt Decider?

The fact that I am a couple of steps ahead of your should give you pause
for how dumb you think I am.

It isn't that surprising that I can see this future, as you have done it
in the past.

YOU are the one stuck in an infinite recursion, and you don't know how
to get out,

[Richard Damon]

Are you forgetting what you just claimed to have stipulated, when you
didn't?

That X was a pure function.

You didn't stipulate it in the first place, and when using hidden state
(as you H effectively does) you the when back and tried to re-con that
you meant to stipulate that the functions were pure functions.

I guess you mind has just gone all mushy.

[Mikko]

On 2024-02-02 20:36:05 +0000, olcott said:

> On 2/2/2024 12:20 PM, Mikko wrote:

>> OP does not stipulate that.

> Stipulate what?

Actually, OP did not stipulate anything, just asked a
question:

> Does this criteria prove that Y calls X in infinite recursion?
> An examination its x86 machine language proves that Y calls X with its
> same parameters and there are no conditional branch instructions
> between the invocation of Y and its call to X.

That question has been answered: no, those criteria don't prove it.

> You cannot erase what you are responding to.

Sorry, my mistake.

--
Mikko

[immibis]

On 1/02/24 18:17, olcott wrote:
> #include <stdint.h>
> typedef int(*ptr)();
>
> int X(ptr P, ptr I)
> {
>   P(I);
>   return 0;
> }
>
> int Y(ptr P)
> {
>   X(P, P);
>   return 1;
> }
>
> int main()
> {
>   X(Y, Y);
> }
>
> Does this criteria prove that Y calls X in infinite recursion?

Irrelevant. This is different from the halting decider because it calls
Y(Y) instead of beginning a simulating of Y(Y) and stepping the
simulation and making a termination decision after each step.

[immibis]

Is this meant to apply to your halting decider code? Globals are not
allowed because they are undeclared inputs which mean that your program
is different from Linz's counterexample which has no other inputs. Your
halting decider code uses an execution trace as an undeclared input so
it is different from Linz's counterexample.