Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #79002 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-04-17 09:17 -0500 |
| Last post | 2021-04-18 13:21 -0500 |
| Articles | 20 on this page of 29 — 6 participants |
Back to article view | Back to comp.lang.c++
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 →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 09:17 -0500 |
| Subject | Infinite 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 19:18 -0500 |
| Subject | Infinite 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]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-04-18 02:02 +0000 |
| Subject | Re: 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]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-17 19:05 -0700 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-04-17 21:12 -0500 |
| Subject | Re: 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]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-17 19:18 -0700 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-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