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


Groups > comp.lang.c++ > #79002 > unrolled thread

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

Started byolcott <NoOne@NoWhere.com>
First post2021-04-17 09:17 -0500
Last post2021-04-18 13:21 -0500
Articles 20 on this page of 29 — 6 participants

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


Contents

  Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 09:17 -0500
    Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 19:18 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 02:02 +0000
      Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:05 -0700
        Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) olcott <NoOne@NoWhere.com> - 2021-04-17 21:12 -0500
          Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-17 19:18 -0700
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-17 19:49 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 07:52 -0700
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 12:11 -0500
        Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 11:02 -0700
          Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:24 -0500
            Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 11:41 -0700
              Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:54 -0500
                Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 12:44 -0700
                  Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 14:53 -0500
                    Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 13:05 -0700
                      Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 15:07 -0500
                        Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 13:16 -0700
                          Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 15:37 -0500
                            Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-18 22:06 -0700
                              Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-19 09:49 -0500
                                Re: Infinite recursion detection criteria (Please correct me if I am wrong) wij <wyniijj@gmail.com> - 2021-04-19 09:12 -0700
                                  Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-19 11:50 -0500
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) Bonita Montero <Bonita.Montero@gmail.com> - 2021-04-18 18:12 +0200
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 11:16 -0500
        Re: Infinite recursion detection criteria (Please correct me if I am wrong) Bonita Montero <Bonita.Montero@gmail.com> - 2021-04-18 19:33 +0200
          Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 12:35 -0500
      Re: Infinite recursion detection criteria (Please correct me if I am wrong) Real Troll <real.troll@trolls.com> - 2021-04-18 17:23 +0100
    Re: Infinite recursion detection criteria (Please correct me if I am wrong) olcott <NoOne@NoWhere.com> - 2021-04-18 13:21 -0500

Page 1 of 2  [1] 2  Next page →


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

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 09:17 -0500
SubjectInfinite recursion detection criteria (Please correct me if I am wrong)
Message-ID<HridnZb_Jp2ac-f9nZ2dnUU7-KdQAAAA@giganews.com>
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

[toc] | [next] | [standalone]


#79022 — Infinite recursion detection criteria (Please correct me if I am wrong)(update)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 19:18 -0500
SubjectInfinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<ZPKdnSyBUrN_5-b9nZ2dnUU7-efNnZ2d@giganews.com>
In reply to#79002
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.


-- 
Copyright 2021 Pete Olcott

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

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


#79026 — Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-04-18 02:02 +0000
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<20210417185831.149@kylheku.com>
In reply to#79022
["Followup-To:" header set to comp.theory.]
On 2021-04-18, olcott <NoOne@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

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


#79027 — Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update)

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-04-17 19:05 -0700
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<s5g45l$1vc4$1@gioia.aioe.org>
In reply to#79022
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?

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


#79028 — Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update)

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 21:12 -0500
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<tMOdnQyFAPvyCOb9nZ2dnUU7-fHNnZ2d@giganews.com>
In reply to#79027
On 4/17/2021 9:05 PM, Chris M. Thomasson wrote:
> 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?

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.

-- 
Copyright 2021 Pete Olcott

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

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


#79029 — Re: Infinite recursion detection criteria (Please correct me if I am wrong)(update)

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-04-17 19:18 -0700
SubjectRe: Infinite recursion detection criteria (Please correct me if I am wrong)(update)
Message-ID<s5g4tj$bg1$1@gioia.aioe.org>
In reply to#79028
On 4/17/2021 7:12 PM, olcott wrote:
> On 4/17/2021 9:05 PM, Chris M. Thomasson wrote:
>> 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?
> 
> The actual x86 emulator handles all of the x86 32-bit instructions.

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?

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


#79023

Fromolcott <NoOne@NoWhere.com>
Date2021-04-17 19:49 -0500
Message-ID<saCdnS6GYdexH-b9nZ2dnUU7-NnNnZ2d@giganews.com>
In reply to#79002
On 4/17/2021 7:34 PM, Ben Bacarisse wrote:
> olcott <NoOne@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.


-- 
Copyright 2021 Pete Olcott

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

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


#79030

Fromwij <wyniijj@gmail.com>
Date2021-04-18 07:52 -0700
Message-ID<a04df195-6e19-496f-842e-8006422b6977n@googlegroups.com>
In reply to#79002
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++.

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?

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


#79039

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 12:11 -0500
Message-ID<lsWdnYskA-je9eH9nZ2dnUU7-QPNnZ2d@giganews.com>
In reply to#79030
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.

-- 
Copyright 2021 Pete Olcott

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

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


#79043

Fromwij <wyniijj@gmail.com>
Date2021-04-18 11:02 -0700
Message-ID<9fc3fd91-1e6f-43f9-a0e6-a0a3137a84d9n@googlegroups.com>
In reply to#79039
On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
> 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.

Then, X() "You call it a halt decider", is defined not to return.

> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

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


#79045

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 13:24 -0500
Message-ID<RsGdncseEM7e5OH9nZ2dnUU7-YOdnZ2d@giganews.com>
In reply to#79043
On 4/18/2021 1:02 PM, wij wrote:
> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>> 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.
> 
> Then, X() "You call it a halt decider", is defined not to return.

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.


> 
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein


-- 
Copyright 2021 Pete Olcott

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

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


#79047

Fromwij <wyniijj@gmail.com>
Date2021-04-18 11:41 -0700
Message-ID<848351c4-f3ca-4ee5-b446-c18c8e4b1635n@googlegroups.com>
In reply to#79045
On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote:
> On 4/18/2021 1:02 PM, wij wrote: 
> > On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote: 
> >> 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. 
> > 
> > Then, X() "You call it a halt decider", is defined not to return.
> 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. 
> 
> 
> >
> >> -- 
> >> Copyright 2021 Pete Olcott 
> >> 
> >> "Great spirits have always encountered violent opposition from mediocre 
> >> minds." Einstein 
> 
> 
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

Then, you restrict Y() to the type of function that X() can detect.

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


#79050

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 13:54 -0500
Message-ID<OZGdne6o-bv-HeH9nZ2dnUU7-V3NnZ2d@giganews.com>
In reply to#79047
On 4/18/2021 1:41 PM, wij wrote:
> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote:
>> On 4/18/2021 1:02 PM, wij wrote:
>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>>>> 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.
>>>
>>> Then, X() "You call it a halt decider", is defined not to return.
>> 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.
>>
>>
>>>
>>>> -- 
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>
>>
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> Then, you restrict Y() to the type of function that X() can detect.
> 

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

-- 
Copyright 2021 Pete Olcott

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

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


#79051

Fromwij <wyniijj@gmail.com>
Date2021-04-18 12:44 -0700
Message-ID<c805d673-fe7b-4b28-8d7e-1fd99f037177n@googlegroups.com>
In reply to#79050
On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote:
> On 4/18/2021 1:41 PM, wij wrote: 
> > On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote: 
> >> On 4/18/2021 1:02 PM, wij wrote: 
> >>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote: 
> >>>> 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. 
> >>> 
> >>> Then, X() "You call it a halt decider", is defined not to return. 
> >> 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. 
> >> 
> >> 
> >>> 
> >>>> -- 
> >>>> Copyright 2021 Pete Olcott 
> >>>> 
> >>>> "Great spirits have always encountered violent opposition from mediocre 
> >>>> minds." Einstein 
> >> 
> >> 
> >> -- 
> >> Copyright 2021 Pete Olcott 
> >> 
> >> "Great spirits have always encountered violent opposition from mediocre 
> >> minds." Einstein 
> > 
> > Then, you restrict Y() to the type of function that X() can detect. 
> >
> 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. 
> 

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.

> 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

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


#79053

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 14:53 -0500
Message-ID<x6qdnUAduaCxE-H9nZ2dnUU7-enNnZ2d@giganews.com>
In reply to#79051
On 4/18/2021 2:44 PM, wij wrote:
> On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote:
>> On 4/18/2021 1:41 PM, wij wrote:
>>> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote:
>>>> On 4/18/2021 1:02 PM, wij wrote:
>>>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>>>>>> 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.
>>>>>
>>>>> Then, X() "You call it a halt decider", is defined not to return.
>>>> 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.
>>>>
>>>>
>>>>>
>>>>>> -- 
>>>>>> Copyright 2021 Pete Olcott
>>>>>>
>>>>>> "Great spirits have always encountered violent opposition from mediocre
>>>>>> minds." Einstein
>>>>
>>>>
>>>> -- 
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>>
>>> Then, you restrict Y() to the type of function that X() can detect.
>>>
>> 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.
>>
> 
> Y() can be written in various way to simulate X() that X() has no way to
> predict. Or X() can predict the future.
> 

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


-- 
Copyright 2021 Pete Olcott

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

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


#79054

Fromwij <wyniijj@gmail.com>
Date2021-04-18 13:05 -0700
Message-ID<0cec0e7f-6dfb-44e2-b7f4-7cb31a1ffb59n@googlegroups.com>
In reply to#79053
On Monday, 19 April 2021 at 03:53:37 UTC+8, olcott wrote:
> On 4/18/2021 2:44 PM, wij wrote: 
> > On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote: 
> >> On 4/18/2021 1:41 PM, wij wrote: 
> >>> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote: 
> >>>> On 4/18/2021 1:02 PM, wij wrote: 
> >>>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote: 
> >>>>>> 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. 
> >>>>> 
> >>>>> Then, X() "You call it a halt decider", is defined not to return. 
> >>>> 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. 
> >>>> 
> >>>> 
> >>>>> 
> >>>>>> -- 
> >>>>>> Copyright 2021 Pete Olcott 
> >>>>>> 
> >>>>>> "Great spirits have always encountered violent opposition from mediocre 
> >>>>>> minds." Einstein 
> >>>> 
> >>>> 
> >>>> -- 
> >>>> Copyright 2021 Pete Olcott 
> >>>> 
> >>>> "Great spirits have always encountered violent opposition from mediocre 
> >>>> minds." Einstein 
> >>> 
> >>> Then, you restrict Y() to the type of function that X() can detect. 
> >>> 
> >> 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. 
> >> 
> > 
> > Y() can be written in various way to simulate X() that X() has no way to 
> > predict. Or X() can predict the future. 
> >
> 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
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

I hope you can also solve the mentioned example:

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

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


#79055

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 15:07 -0500
Message-ID<1rSdne4i4_HyDOH9nZ2dnUU7-RudnZ2d@giganews.com>
In reply to#79054
On 4/18/2021 3:05 PM, wij wrote:
> On Monday, 19 April 2021 at 03:53:37 UTC+8, olcott wrote:
>> On 4/18/2021 2:44 PM, wij wrote:
>>> On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote:
>>>> On 4/18/2021 1:41 PM, wij wrote:
>>>>> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote:
>>>>>> On 4/18/2021 1:02 PM, wij wrote:
>>>>>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>>>>>>>> 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.
>>>>>>>
>>>>>>> Then, X() "You call it a halt decider", is defined not to return.
>>>>>> 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.
>>>>>>
>>>>>>
>>>>>>>
>>>>>>>> -- 
>>>>>>>> Copyright 2021 Pete Olcott
>>>>>>>>
>>>>>>>> "Great spirits have always encountered violent opposition from mediocre
>>>>>>>> minds." Einstein
>>>>>>
>>>>>>
>>>>>> -- 
>>>>>> Copyright 2021 Pete Olcott
>>>>>>
>>>>>> "Great spirits have always encountered violent opposition from mediocre
>>>>>> minds." Einstein
>>>>>
>>>>> Then, you restrict Y() to the type of function that X() can detect.
>>>>>
>>>> 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.
>>>>
>>>
>>> Y() can be written in various way to simulate X() that X() has no way to
>>> predict. Or X() can predict the future.
>>>
>> 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
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> I hope you can also solve the mentioned example:
> 
>   E.g. Y() can split the algorithm of X() into several parts and simulate it.
>   How can X() know about this.
> 

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

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


#79056

Fromwij <wyniijj@gmail.com>
Date2021-04-18 13:16 -0700
Message-ID<bac43495-95a0-4a51-a242-6d9e2a2d0e36n@googlegroups.com>
In reply to#79055
On Monday, 19 April 2021 at 04:07:30 UTC+8, olcott wrote:
> On 4/18/2021 3:05 PM, wij wrote: 
> > On Monday, 19 April 2021 at 03:53:37 UTC+8, olcott wrote: 
> >> On 4/18/2021 2:44 PM, wij wrote: 
> >>> On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote: 
> >>>> On 4/18/2021 1:41 PM, wij wrote: 
> >>>>> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote: 
> >>>>>> On 4/18/2021 1:02 PM, wij wrote: 
> >>>>>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote: 
> >>>>>>>> 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. 
> >>>>>>> 
> >>>>>>> Then, X() "You call it a halt decider", is defined not to return. 
> >>>>>> 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. 
> >>>>>> 
> >>>>>> 
> >>>>>>> 
> >>>>>>>> -- 
> >>>>>>>> Copyright 2021 Pete Olcott 
> >>>>>>>> 
> >>>>>>>> "Great spirits have always encountered violent opposition from mediocre 
> >>>>>>>> minds." Einstein 
> >>>>>> 
> >>>>>> 
> >>>>>> -- 
> >>>>>> Copyright 2021 Pete Olcott 
> >>>>>> 
> >>>>>> "Great spirits have always encountered violent opposition from mediocre 
> >>>>>> minds." Einstein 
> >>>>> 
> >>>>> Then, you restrict Y() to the type of function that X() can detect. 
> >>>>> 
> >>>> 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. 
> >>>> 
> >>> 
> >>> Y() can be written in various way to simulate X() that X() has no way to 
> >>> predict. Or X() can predict the future. 
> >>> 
> >> 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 
> >> -- 
> >> Copyright 2021 Pete Olcott 
> >> 
> >> "Great spirits have always encountered violent opposition from mediocre 
> >> minds." Einstein 
> > 
> > I hope you can also solve the mentioned example: 
> > 
> > E.g. Y() can split the algorithm of X() into several parts and simulate it. 
> > How can X() know about this. 
> >
> 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?

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


#79057

Fromolcott <NoOne@NoWhere.com>
Date2021-04-18 15:37 -0500
Message-ID<v7SdnThEGqfyBeH9nZ2dnUU7-TXNnZ2d@giganews.com>
In reply to#79056
On 4/18/2021 3:16 PM, wij wrote:
> On Monday, 19 April 2021 at 04:07:30 UTC+8, olcott wrote:
>> On 4/18/2021 3:05 PM, wij wrote:
>>> On Monday, 19 April 2021 at 03:53:37 UTC+8, olcott wrote:
>>>> On 4/18/2021 2:44 PM, wij wrote:
>>>>> On Monday, 19 April 2021 at 02:54:46 UTC+8, olcott wrote:
>>>>>> On 4/18/2021 1:41 PM, wij wrote:
>>>>>>> On Monday, 19 April 2021 at 02:24:22 UTC+8, olcott wrote:
>>>>>>>> On 4/18/2021 1:02 PM, wij wrote:
>>>>>>>>> On Monday, 19 April 2021 at 01:11:50 UTC+8, olcott wrote:
>>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>> Then, X() "You call it a halt decider", is defined not to return.
>>>>>>>> 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.
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>>> -- 
>>>>>>>>>> Copyright 2021 Pete Olcott
>>>>>>>>>>
>>>>>>>>>> "Great spirits have always encountered violent opposition from mediocre
>>>>>>>>>> minds." Einstein
>>>>>>>>
>>>>>>>>
>>>>>>>> -- 
>>>>>>>> Copyright 2021 Pete Olcott
>>>>>>>>
>>>>>>>> "Great spirits have always encountered violent opposition from mediocre
>>>>>>>> minds." Einstein
>>>>>>>
>>>>>>> Then, you restrict Y() to the type of function that X() can detect.
>>>>>>>
>>>>>> 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.
>>>>>>
>>>>>
>>>>> Y() can be written in various way to simulate X() that X() has no way to
>>>>> predict. Or X() can predict the future.
>>>>>
>>>> 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
>>>> -- 
>>>> Copyright 2021 Pete Olcott
>>>>
>>>> "Great spirits have always encountered violent opposition from mediocre
>>>> minds." Einstein
>>>
>>> I hope you can also solve the mentioned example:
>>>
>>> E.g. Y() can split the algorithm of X() into several parts and simulate it.
>>> How can X() know about this.
>>>
>> 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.

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


-- 
Copyright 2021 Pete Olcott

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

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


#79071

Fromwij <wyniijj@gmail.com>
Date2021-04-18 22:06 -0700
Message-ID<46dac6d4-22e6-460c-897d-075f0f5172b9n@googlegroups.com>
In reply to#79057
> >> 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.

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


Page 1 of 2  [1] 2  Next page →

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


csiph-web