Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Infinite recursion detection criteria (Please correct me if I am wrong)

36 views
Skip to first unread message

olcott

unread,
Apr 17, 2021, 10:18:02 AM4/17/21
to
If a function X() is called by function Y() twice in sequence from the
same machine address of Y() with the same parameters to X() and the
execution trace shows no conditional branch instructions in Y() or
function call returns in X() then the function call from Y() to X() is
infinitely recursive unless X() stops it.

The referenced execution trace is on x86 machine language, disassembled
for human consumption.

--
Copyright 2021 Pete Olcott

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

olcott

unread,
Apr 17, 2021, 8:19:01 PM4/17/21
to
On 4/17/2021 9:17 AM, olcott wrote:
> If a function X() is called by function Y() twice in sequence from the
> same machine address of Y() with the same parameters to X() and the
> execution trace shows no conditional branch instructions in Y() or
> function call returns in X() then the function call from Y() to X() is
> infinitely recursive unless X() stops it.
>
> The referenced execution trace is on x86 machine language, disassembled
> for human consumption.
>

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

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

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


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.


olcott

unread,
Apr 17, 2021, 8:50:07 PM4/17/21
to
On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>
> You mean like this:
>
> 0x000055555555517d <main+0>: endbr64
> 0x0000555555555181 <main+4>: push %rbp
> 0x0000555555555182 <main+5>: mov %rsp,%rbp
> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555515c <X+0>: endbr64
> 0x0000555555555160 <X+4>: push %rbp
> 0x0000555555555161 <X+5>: mov %rsp,%rbp
> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555515c <X+0>: endbr64
> 0x0000555555555160 <X+4>: push %rbp
> 0x0000555555555161 <X+5>: mov %rsp,%rbp
> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555515c <X+0>: endbr64
> 0x0000555555555160 <X+4>: push %rbp
> 0x0000555555555161 <X+5>: mov %rsp,%rbp
> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555515c <X+0>: endbr64
> 0x0000555555555160 <X+4>: push %rbp
> 0x0000555555555161 <X+5>: mov %rsp,%rbp
> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555516e <Z+0>: endbr64
> 0x0000555555555172 <Z+4>: push %rbp
> 0x0000555555555173 <Z+5>: mov %rsp,%rbp
> 0x0000555555555176 <Z+8>: mov $0x1,%eax
> ...
>
> Note how X is called from Y+44 more than once with no branching or
> returns.
>

Lets simply assume x86 architecture and Intel syntax.

This is my latest revised infinite recursion halt deciding criteria:

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.


Kaz Kylheku

unread,
Apr 17, 2021, 10:02:33 PM4/17/21
to
["Followup-To:" header set to comp.theory.]
On 2021-04-18, olcott <No...@NoWhere.com> wrote:
> On 4/17/2021 9:17 AM, olcott wrote:
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>>
>> The referenced execution trace is on x86 machine language, disassembled
>> for human consumption.
>>
>
> void X(u32 P, i32 I)
> {
> Simulate(P, I);
^^^^

This necessariy has a shitload of conditional execution in it.

> }
>
> void Y(u32 P)
> {
> X(P, P);
> }
>
> int main()
> {
> X((u32)Y, (u32)Y);
> }
>
>
> 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.

Wrong:

(3) a) With no conditional branch or indirect jump instructions
anywhere in the recursive loop, including the bodies of Y,
X, or any subroutine they call, or any child thereof.

b) There be no extensions to the Intel x86 instruction set.
which perpetrate conditional behavior inside the simulator
which subsequently affects the control flow.

The criterion that only Y has an basic block of instructions being
executed repeatedly are ridiculously insufficient for establishing that
there is a runaway recursion.

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

Chris M. Thomasson

unread,
Apr 17, 2021, 10:05:58 PM4/17/21
to
On 4/17/2021 5:18 PM, olcott wrote:
> On 4/17/2021 9:17 AM, olcott wrote:
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>>
>> The referenced execution trace is on x86 machine language,
>> disassembled for human consumption.
>>
>
> void X(u32 P, i32 I)
> {
>  Simulate(P, I);
> }
>
> void Y(u32 P)
> {
>  X(P, P);
> }
>
> int main()
> {
>  X((u32)Y, (u32)Y);
> }
>
>
> 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.
>
>

Does your simulator handle the CMPXCHG instruction?

olcott

unread,
Apr 17, 2021, 10:12:18 PM4/17/21
to
The actual x86 emulator handles all of the x86 32-bit instructions.
If this screws up my criteria then I simply screen it out.

I may end up creating a machine much closer to a Turing machine except
that it will have 32-bit signed relative addressing at the very least.

Chris M. Thomasson

unread,
Apr 17, 2021, 10:18:45 PM4/17/21
to
Ahh, okay. So it can handle the LOCK prefix as well, right? CMPXCHG is a
32-bit instruction and, well, you know about the LOCK prefix so, thanks
for answering my question.

https://www.felixcloutier.com/x86/cmpxchg

https://www.felixcloutier.com/x86/lock

Does your simulator lock the bus, and/or the cache line in its emulation
of these instructions? Think of trying, and failing to lock the cache
line a bunch of times in a row, then finally resorting to the bus lock.
How do you do it in your simulator?


> If this screws up my criteria then I simply screen it out.

I do not know what you mean. CMPXCHG, XADD, XCHG, all of the x86 32-bit
instructions must be in your simulator right?


> I may end up creating a machine much closer to a Turing machine except
> that it will have 32-bit signed relative addressing at the very least.

Did you emulator x86 or not?

wij

unread,
Apr 18, 2021, 10:52:43 AM4/18/21
to
I can think of no easy way to detect infinite recursion in C++.

From the problem description:

Y: // no contiditonal branch
read_arg of Y
push_arg for X
call X
pop_arg for X
ret

X:
... // no return instruction
push_arg for Y
call Y
pop_arg for Y
... // no return instruction, probably unreachable

Obviously, both X() and Y() can never return. Then, what is the point?

Bonita Montero

unread,
Apr 18, 2021, 12:12:47 PM4/18/21
to
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!
STOP POSTING IN comp.lang.c/c++ !!!

olcott

unread,
Apr 18, 2021, 12:16:53 PM4/18/21
to
On 4/18/2021 11:12 AM, Bonita Montero wrote:
> STOP POSTING IN comp.lang.c/c++ !!!

Since this <is> relevant to C/C++ you can simply STFU !

Real Troll

unread,
Apr 18, 2021, 12:26:20 PM4/18/21
to
Did you use for loop to print all that crap?

olcott

unread,
Apr 18, 2021, 1:11:50 PM4/18/21
to
On 4/18/2021 9:52 AM, wij wrote:
> On Saturday, 17 April 2021 at 22:18:02 UTC+8, olcott wrote:
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>>
>> The referenced execution trace is on x86 machine language, disassembled
>> for human consumption.
>>
>> --
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
>
> I can think of no easy way to detect infinite recursion in C++.
>

The detection of the infinite recursion occurs at the machine language
level.

> From the problem description:
>
> Y: // no contiditonal branch
> read_arg of Y
> push_arg for X
> call X
> pop_arg for X
> ret
>
> X:
> ... // no return instruction
> push_arg for Y
> call Y
> pop_arg for Y
> ... // no return instruction, probably unreachable
>
> Obviously, both X() and Y() can never return. Then, what is the point?
>

The idea is to be able to define X() as a halt decider for functions
that call X() in infinite recursion.

Bonita Montero

unread,
Apr 18, 2021, 1:33:20 PM4/18/21
to
> Since this <is> relevant to C/C++ you can simply STFU !

It isn't relvant specifically to C/C++, it is relevant to any
language. So stop posting here.

olcott

unread,
Apr 18, 2021, 1:35:19 PM4/18/21
to
KNOW !

wij

unread,
Apr 18, 2021, 2:02:32 PM4/18/21
to
Then, X() "You call it a halt decider", is defined not to return.

olcott

unread,
Apr 18, 2021, 2:21:35 PM4/18/21
to
On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> If a function X() is called by function Y() twice in sequence from the
>> same machine address of Y() with the same parameters to X() and the
>> execution trace shows no conditional branch instructions in Y() or
>> function call returns in X() then the function call from Y() to X() is
>> infinitely recursive unless X() stops it.
>
> You mean like this:
>
> 0x000055555555517d <main+0>: endbr64
> 0x0000555555555181 <main+4>: push %rbp
> 0x0000555555555182 <main+5>: mov %rsp,%rbp
> 0x0000555555555185 <main+8>: callq 0x555555555129 <Y>
> 0x0000555555555129 <Y+0>: endbr64
> 0x000055555555512d <Y+4>: push %rbp
> 0x000055555555512e <Y+5>: mov %rsp,%rbp
> 0x0000555555555131 <Y+8>: mov 0x2f15(%rip),%eax
> 0x0000555555555137 <Y+14>: lea 0x1(%rax),%edx

It is this line-of-code that has the same effect as simulating a
conditional branch using a jump table:
> 0x000055555555513a <Y+17>: mov %edx,0x2f0c(%rip)
> 0x0000555555555140 <Y+23>: cltq
> 0x0000555555555142 <Y+25>: lea 0x0(,%rax,8),%rdx
> 0x000055555555514a <Y+33>: lea 0x2ecf(%rip),%rax
> 0x0000555555555151 <Y+40>: mov (%rdx,%rax,1),%rax
> 0x0000555555555155 <Y+44>: callq *%rax
> 0x000055555555515c <X+0>: endbr64
> 0x0000555555555160 <X+4>: push %rbp
> 0x0000555555555161 <X+5>: mov %rsp,%rbp
> 0x0000555555555164 <X+8>: callq 0x555555555129 <Y>

Simply restricting the model to the x86 architecture gets rid of this
problem. Since my purpose is to prove that there is at least one case
where a halt decider can correctly decide that it was called in infinite
recursion discarding an architectural model is a reasonable choice.

This is the revised infinite recursion detection criteria:

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.

When X() detects that its simulation of Y() meets the above criteria
then X() can definitely stop simulating Y() to prevent its own infinite
execution.

olcott

unread,
Apr 18, 2021, 2:24:22 PM4/18/21
to
When X() uses the following criteria to decide to stop simulating Y()
then X() has correctly decided that Y() would otherwise cause X() to
have infinite execution.

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.


>

wij

unread,
Apr 18, 2021, 2:41:23 PM4/18/21
to
Then, you restrict Y() to the type of function that X() can detect.

olcott

unread,
Apr 18, 2021, 2:54:46 PM4/18/21
to
Basically the above criteria allows a C function X() that simulates the
x86 machine language of function Y() to correctly decide that Y() is
calling X() in infinite recursion.

It turns out that this same scenario is what has been used to "prove"
that the halting problem cannot be solved.

If X is the Linz H and Y is a slightly simplified version of the Linz
H^, then H does correctly decides not halting on H^

void H^(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt = H((u32)H^, (u32)H^);
Output("Input_Would_Halt = ", Input_Would_Halt);
}

http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf

wij

unread,
Apr 18, 2021, 3:44:36 PM4/18/21
to
Y() can be written in various way to simulate X() that X() has no way to
predict. Or X() can predict the future.

E.g. Y() can split the algorithm of X() into several parts and simulate it.
How can X() know about this.

olcott

unread,
Apr 18, 2021, 3:53:37 PM4/18/21
to
You have that backwards, here it is in more detail:

#define u32 uint32_t

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

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

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

X() has an x86 emulator and the compiled C of Y() is x86.

> E.g. Y() can split the algorithm of X() into several parts and simulate it.
> How can X() know about this.
>
>> If X is the Linz H and Y is a slightly simplified version of the Linz
>> H^, then H does correctly decides not halting on H^
>>
>> void H^(u32 P)
>> {
>> u32 Input_Would_Halt = Halts(P, P);
>> if (Input_Would_Halt)
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 Input_Would_Halt = H((u32)H^, (u32)H^);
>> Output("Input_Would_Halt = ", Input_Would_Halt);
>> }
>>
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf
>> --
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein


wij

unread,
Apr 18, 2021, 4:05:31 PM4/18/21
to
I hope you can also solve the mentioned example:

olcott

unread,
Apr 18, 2021, 4:07:30 PM4/18/21
to
Y() is not at all any sort of simulator, you have this part backwards.

wij

unread,
Apr 18, 2021, 4:16:27 PM4/18/21
to
Therefore X() can only solve 'known instances', right?

olcott

unread,
Apr 18, 2021, 4:37:22 PM4/18/21
to
X() can detect a when it is called in infinite recursion by Y() which is
an x86 function generated by a C compiler.

This is sufficient to refute the conventional halting problem
undecidability proofs.


void Y(u32 P)
{
int Input_Would_Halt = X(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}

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

wij

unread,
Apr 19, 2021, 1:06:35 AM4/19/21
to
> >> Y() is not at all any sort of simulator, you have this part backwards.
> >> --
> >> Copyright 2021 Pete Olcott
> >>
> >> "Great spirits have always encountered violent opposition from mediocre
> >> minds." Einstein
> >
> > Therefore X() can only solve 'known instances', right?
> >
> X() can detect a when it is called in infinite recursion by Y() which is
> an x86 function generated by a C compiler.
>

So, the answer is yes. X() can only solve existing 'known instances' AND
it also have to be an x86 function generated by a C compiler.

> This is sufficient to refute the conventional halting problem
> undecidability proofs.
>

If you think so.
https://en.wikipedia.org/wiki/Necessity_and_sufficiency

>
> void Y(u32 P)
> {
> int Input_Would_Halt = X(P, P);
> if (Input_Would_Halt)
> HERE: goto HERE;
> }
>
> int main()
> {
> X((u32)Y, (u32)Y);
> }
>
>

I have been avoid mentioning the secondary issue that such codes are
very type dependent, suspicious to pass real tests.

olcott

unread,
Apr 19, 2021, 10:49:19 AM4/19/21
to
On 4/19/2021 12:06 AM, wij wrote:
>>>> Y() is not at all any sort of simulator, you have this part backwards.
>>>> --
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>>
>>> Therefore X() can only solve 'known instances', right?
>>>
>> X() can detect a when it is called in infinite recursion by Y() which is
>> an x86 function generated by a C compiler.
>>
>
> So, the answer is yes. X() can only solve existing 'known instances' AND
> it also have to be an x86 function generated by a C compiler.

No, X() can solve an infinite set of instances where X() simulates Y()
and can examine the execution trace of Y() in some machine language.

>> This is sufficient to refute the conventional halting problem
>> undecidability proofs.
>>
>
> If you think so.
> https://en.wikipedia.org/wiki/Necessity_and_sufficiency
>
>>
>> void Y(u32 P)
>> {
>> int Input_Would_Halt = X(P, P);
>> if (Input_Would_Halt)
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> X((u32)Y, (u32)Y);
>> }
>>
>>
>
> I have been avoid mentioning the secondary issue that such codes are
> very type dependent, suspicious to pass real tests.
>

I created that x86utm operating system and have been able to prove that
my halt decider correctly decides the above case for six months now.

wij

unread,
Apr 19, 2021, 12:13:09 PM4/19/21
to
If your, or anyone's, claim (no one can legitimately refute, in your logic) can be verified
by physical machines, you do not need people's confirmation, because the claim is
supported by physical machines, no one can refute.
Publish it in some way is enough (like astronomers spot a comet or found some
strange physic phenomena).

olcott

unread,
Apr 19, 2021, 12:51:06 PM4/19/21
to
I need to confirm that there are no gaps in my reasoning where an
execution trace meets the above criteria and is not infinitely recursive.
0 new messages