Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Detecting infinite recursion (V2)
5 views
Skip to first unread message
olcott
Mar 4, 2021, 9:52:05 AM3/4/21
to
If a software function:
(1) Simulates the execution of the machine language of another function.
(2) Maintains an execution trace list of each machine state change
occurring as a result of the simulation of each machine instruction.
(3) Examines this list after the execution of each machine instruction
for the purpose of detecting whether or not the Simulate() function is
being called in infinite recursion.
(4) Stops simulating the program under test as soon as it detects that
Simulate is being called in infinite recursion.
void H_Hat(u32 P)
{
Simulate(P, P);
}
int main()
{
Simulate((u32)H_Hat, (u32)H_Hat);
}
Can this Simulate() function correctly decide not halting on its input
on the basis that it did correctly detect that it was being called in
infinite recursion?
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
(1) Simulates the execution of the machine language of another function.
(2) Maintains an execution trace list of each machine state change
occurring as a result of the simulation of each machine instruction.
(3) Examines this list after the execution of each machine instruction
for the purpose of detecting whether or not the Simulate() function is
being called in infinite recursion.
(4) Stops simulating the program under test as soon as it detects that
Simulate is being called in infinite recursion.
void H_Hat(u32 P)
{
Simulate(P, P);
}
int main()
{
Simulate((u32)H_Hat, (u32)H_Hat);
}
Can this Simulate() function correctly decide not halting on its input
on the basis that it did correctly detect that it was being called in
infinite recursion?
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Bonita Montero
Mar 4, 2021, 10:19:24 AM3/4/21
to
Can you pleas stop posting things not related to C/C++-language
issues to comp.lang.c++/c ?
olcott
Mar 4, 2021, 10:26:15 AM3/4/21
to
On 3/4/2021 9:19 AM, Bonita Montero wrote:
>
> Can you pleas stop posting things not related to C/C++-language
> issues to comp.lang.c++/c ?
I meant to put a followup-To comp.theory on the, sorry.
>
> Can you pleas stop posting things not related to C/C++-language
> issues to comp.lang.c++/c ?
Richard Damon
Mar 4, 2021, 10:55:45 AM3/4/21
to
On 3/4/21 9:51 AM, olcott wrote:
> If a software function:
> (1) Simulates the execution of the machine language of another function.
>
> (2) Maintains an execution trace list of each machine state change
> occurring as a result of the simulation of each machine instruction.
>
> (3) Examines this list after the execution of each machine instruction
> for the purpose of detecting whether or not the Simulate() function is
> being called in infinite recursion.
>
> (4) Stops simulating the program under test as soon as it detects that
> Simulate is being called in infinite recursion.
>
>
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
>
> int main()
> {
> Simulate((u32)H_Hat, (u32)H_Hat);
> }
>
> Can this Simulate() function correctly decide not halting on its input
> on the basis that it did correctly detect that it was being called in
> infinite recursion?
>
>
A SIMULATOR, which never stops until the program it is running stops,
> If a software function:
> (1) Simulates the execution of the machine language of another function.
>
> (2) Maintains an execution trace list of each machine state change
> occurring as a result of the simulation of each machine instruction.
>
> (3) Examines this list after the execution of each machine instruction
> for the purpose of detecting whether or not the Simulate() function is
> being called in infinite recursion.
>
> (4) Stops simulating the program under test as soon as it detects that
> Simulate is being called in infinite recursion.
>
>
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
>
> int main()
> {
> Simulate((u32)H_Hat, (u32)H_Hat);
> }
>
> Can this Simulate() function correctly decide not halting on its input
> on the basis that it did correctly detect that it was being called in
> infinite recursion?
>
>
can detect infinte execution this way.
Once you hit step 4, and the simulator changes its computation based on
this behavior, then the simulator need to understand the behivor when it
is invoked recursively and handles it.
That is the crux of the flaw in your system. Step for introduces a
conditional into the loop that is capable of breaking the otherwise
infinite recursion, and once that conditional become part of the
computation it is analyzing, it needs to take that conditional into
account which breaks most of the rules that you can use to detect the
infinite execution.
David Brown
Mar 4, 2021, 10:59:55 AM3/4/21
to
On 04/03/2021 15:51, olcott wrote:
> If a software function:
> (1) Simulates the execution of the machine language of another function.
>
> (2) Maintains an execution trace list of each machine state change
> occurring as a result of the simulation of each machine instruction.
>
> (3) Examines this list after the execution of each machine instruction
> for the purpose of detecting whether or not the Simulate() function is
> being called in infinite recursion.
>
> (4) Stops simulating the program under test as soon as it detects that
> Simulate is being called in infinite recursion.
>
You can't detect if a program has infinite recursion or not. (I.e., you
> If a software function:
> (1) Simulates the execution of the machine language of another function.
>
> (2) Maintains an execution trace list of each machine state change
> occurring as a result of the simulation of each machine instruction.
>
> (3) Examines this list after the execution of each machine instruction
> for the purpose of detecting whether or not the Simulate() function is
> being called in infinite recursion.
>
> (4) Stops simulating the program under test as soon as it detects that
> Simulate is being called in infinite recursion.
>
can't detect if it will halt or not - the "infinite recursion" is just a
distraction, as the problem is equivalent.)
In any finite number of steps, you can only be sure that the function
has stopped within that number of steps, or has not yet stopped. You
can't (in general) know if it will continue.
I suspect that your ideas about simulation - in particular, simulating
x86 assembly - have given you a warped view of the whole problem. You
are restricting everything to a limited finite size. Ultimately this
gives you a limit that does not exist in general.
If you are dealing only with programs written in x86 machine code that
fit within 2 ^ 32 bytes of combined program and data space (as indicated
by your "u32" type), then there will be a limit to the number of cycles
that a program can run if it is ever going to halt (for a given input).
And the potential range of inputs is known and finite (since the
machine is limited) - so you can just take the maximum over all possible
programs and all possible inputs. Call that number N. Run your
simulator for at most N steps. If the simulated program has stopped,
you know it halts. If it has not, you know it can never halt.
(The size of N here is absurdly huge, of course.)
But the "halting problem" is about general programs - not a limited
subset of programs. There are no limits to the sizes involved.
The proof that you can't solve the halting problem is really quite simple.
Suppose you have made a function (or program - the terms are equivalent)
"halts" that returns "true" if a program halts, and "false" if it does
not. Then you can write the function:
function bad() :
if halts(bad) then loop forever()
If "bad" halts, then "halts(bad)" is true and "bad" loops forever - so
"bad" does not halt.
If "bad" does not halt, then "halts(bad)" returns false and bad()
finishes - it does not halt.
It is /that/ simple.
You can put more effort into it to formalise a proof - or just look up a
proof on the net. But that's a rough sketch, and is enough to show you
that the halting problem is not computable.
olcott
Mar 4, 2021, 11:04:25 AM3/4/21
to
On 3/4/2021 9:55 AM, Richard Damon wrote:
> On 3/4/21 9:51 AM, olcott wrote:
>> If a software function:
>> (1) Simulates the execution of the machine language of another function.
>>
>> (2) Maintains an execution trace list of each machine state change
>> occurring as a result of the simulation of each machine instruction.
>>
>> (3) Examines this list after the execution of each machine instruction
>> for the purpose of detecting whether or not the Simulate() function is
>> being called in infinite recursion.
>>
>> (4) Stops simulating the program under test as soon as it detects that
>> Simulate is being called in infinite recursion.
>>
>>
>> void H_Hat(u32 P)
>> {
>> Simulate(P, P);
>> }
>>
>>
>> int main()
>> {
>> Simulate((u32)H_Hat, (u32)H_Hat);
>> }
>>
>> Can this Simulate() function correctly decide not halting on its input
>> on the basis that it did correctly detect that it was being called in
>> infinite recursion?
>>
>>
>
> A SIMULATOR, which never stops until the program it is running stops,
> can detect infinte execution this way.
>
No it cannot because it never makes any decision in all of eternity.
> On 3/4/21 9:51 AM, olcott wrote:
>> If a software function:
>> (1) Simulates the execution of the machine language of another function.
>>
>> (2) Maintains an execution trace list of each machine state change
>> occurring as a result of the simulation of each machine instruction.
>>
>> (3) Examines this list after the execution of each machine instruction
>> for the purpose of detecting whether or not the Simulate() function is
>> being called in infinite recursion.
>>
>> (4) Stops simulating the program under test as soon as it detects that
>> Simulate is being called in infinite recursion.
>>
>>
>> void H_Hat(u32 P)
>> {
>> Simulate(P, P);
>> }
>>
>>
>> int main()
>> {
>> Simulate((u32)H_Hat, (u32)H_Hat);
>> }
>>
>> Can this Simulate() function correctly decide not halting on its input
>> on the basis that it did correctly detect that it was being called in
>> infinite recursion?
>>
>>
>
> A SIMULATOR, which never stops until the program it is running stops,
> can detect infinte execution this way.
>
> Once you hit step 4, and the simulator changes its computation based on
> this behavior, then the simulator need to understand the behivor when it
> is invoked recursively and handles it.
>
> That is the crux of the flaw in your system. Step for introduces a
> conditional into the loop that is capable of breaking the otherwise
> infinite recursion, and once that conditional become part of the
> computation it is analyzing, it needs to take that conditional into
> account which breaks most of the rules that you can use to detect the
> infinite execution.
>
Does the input program halt? Then "no" is the wrong answer.
If the halt decider is answering the question:
Does the simulation of the input program have to be terminated to
prevent its otherwise infinite execution?
Then "yes" is the correct answer.
olcott
Mar 4, 2021, 11:09:02 AM3/4/21
to
On 3/4/2021 9:59 AM, David Brown wrote:
> On 04/03/2021 15:51, olcott wrote:
>> If a software function:
>> (1) Simulates the execution of the machine language of another function.
>>
>> (2) Maintains an execution trace list of each machine state change
>> occurring as a result of the simulation of each machine instruction.
>>
>> (3) Examines this list after the execution of each machine instruction
>> for the purpose of detecting whether or not the Simulate() function is
>> being called in infinite recursion.
>>
>> (4) Stops simulating the program under test as soon as it detects that
>> Simulate is being called in infinite recursion.
>>
>
> You can't detect if a program has infinite recursion or not. (I.e., you
> can't detect if it will halt or not - the "infinite recursion" is just a
> distraction, as the problem is equivalent.)
Sure you can here is a concrete example:
> On 04/03/2021 15:51, olcott wrote:
>> If a software function:
>> (1) Simulates the execution of the machine language of another function.
>>
>> (2) Maintains an execution trace list of each machine state change
>> occurring as a result of the simulation of each machine instruction.
>>
>> (3) Examines this list after the execution of each machine instruction
>> for the purpose of detecting whether or not the Simulate() function is
>> being called in infinite recursion.
>>
>> (4) Stops simulating the program under test as soon as it detects that
>> Simulate is being called in infinite recursion.
>>
>
> You can't detect if a program has infinite recursion or not. (I.e., you
> can't detect if it will halt or not - the "infinite recursion" is just a
> distraction, as the problem is equivalent.)
#include <stdint.h>
#define u32 uint32_t
int Simulate(u32 P, u32 I)
{
((void(*)(u32))P)(I);
}
void H_Hat(u32 P)
{
Simulate(P, P);
}
int main()
{
Simulate((u32)H_Hat, (u32)H_Hat);
}
_Simulate()
void H_Hat(u32 P)
{
Simulate(P, P);
}
int main()
{
Simulate((u32)H_Hat, (u32)H_Hat);
}
[00000478](01) 55 push ebp
[00000479](02) 8bec mov ebp,esp
[0000047b](03) 8b450c mov eax,[ebp+0c]
[0000047e](01) 50 push eax
[0000047f](03) ff5508 call dword [ebp+08]
[00000482](03) 83c404 add esp,+04
[00000485](01) 5d pop ebp
[00000486](01) c3 ret
_H_Hat()
[00000868](01) 55 push ebp
[00000869](02) 8bec mov ebp,esp
[0000086b](03) 8b4508 mov eax,[ebp+08]
[0000086e](01) 50 push eax
[0000086f](03) 8b4d08 mov ecx,[ebp+08]
[00000872](01) 51 push ecx
[00000873](05) e800fcffff call 00000478
[00000878](03) 83c408 add esp,+08
[0000087b](01) 5d pop ebp
[0000087c](01) c3 ret
_main()
[00000888](01) 55 push ebp
[00000889](02) 8bec mov ebp,esp
[0000088b](05) 6868080000 push 00000868
[00000890](05) 6868080000 push 00000868
[00000895](05) e8defbffff call 00000478
[0000089a](03) 83c408 add esp,+08
[0000089d](02) 33c0 xor eax,eax
[0000089f](01) 5d pop ebp
[000008a0](01) c3 ret
Columns
(1) Sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
(01)[00000888][00011194][00000000](01) 55 push ebp
(02)[00000889][00011194][00000000](02) 8bec mov ebp,esp
(03)[0000088b][00011190][00000868](05) 6868080000 push 00000868
(04)[00000890][0001118c][00000868](05) 6868080000 push 00000868
(05)[00000895][00011188][0000089a](05) e8defbffff call 00000478
Line (03) pushes second parameter to Simulate() machine address 0x868
Line (04) pushes first parameter to Simulate() machine address 0x868
Line (05) Calls Simulate(0x868, 0x868);
(06)[00000868][00011178][00011184](01) 55 push ebp
(07)[00000869][00011178][00011184](02) 8bec mov ebp,esp
(08)[0000086b][00011178][00011184](03) 8b4508 mov eax,[ebp+08]
(09)[0000086e][00011174][00000868](01) 50 push eax
(10)[0000086f][00011174][00000868](03) 8b4d08 mov ecx,[ebp+08]
(11)[00000872][00011170][00000868](01) 51 push ecx
(12)[00000873][0001116c][00000878](05) e800fcffff call 00000478
Line (09) pushes second parameter to Simulate() machine address 0x868
Line (11) pushes first parameter to Simulate() machine address 0x868
Line (12) Calls Simulate(0x868, 0x868);
(13)[00000868][0001115c][00011168](01) 55 push ebp
(14)[00000869][0001115c][00011168](02) 8bec mov ebp,esp
(15)[0000086b][0001115c][00011168](03) 8b4508 mov eax,[ebp+08]
(16)[0000086e][00011158][00000868](01) 50 push eax
(17)[0000086f][00011158][00000868](03) 8b4d08 mov ecx,[ebp+08]
(18)[00000872][00011154][00000868](01) 51 push ecx
(19)[00000873][00011150][00000878](05) e800fcffff call 00000478
Line (16) pushes second parameter to Simulate() machine address 0x868
Line (18) pushes first parameter to Simulate() machine address 0x868
Line (19) Calls Simulate(0x868, 0x868);
Now we have seen that Simulate() is invoked two times from the same
machine address of H_Hat() with the same data. We also know that
Simulate() either executes or emulates the machine language of its input
and nothing more. This seems to provide a sufficient basis for deciding
that H_Hat() is infinitely recursive, thus non-halting.
olcott
Mar 4, 2021, 11:29:49 AM3/4/21
to
On 3/4/2021 10:17 AM, Richard Damon wrote:
> Ok, if you want to work on a DIFFERENT question, you can do so, but that
> means that you CAN NOT claim that any of your results are applicable to
> classical computation theory, like the halting problem proofs. (At least
> until you can rigorously make a proof that they do)
>
> So, if you are willing to publicly announce that you admit that your
> work is not related to the classic halting problem, the no problem with
> your claims.
>
> But, since you seem to keep making the claims that they do, we will keep
> pointing out that you are wrong.
>
I have reframed the halting problem** such that a universal halt decider
can no longer be shown to be impossible.
**Removing its pathological self-reference(Olcott 2004)
By doing this the conventional halting problem proof counter-examples
become halting decidable.
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
> means that you CAN NOT claim that any of your results are applicable to
> classical computation theory, like the halting problem proofs. (At least
> until you can rigorously make a proof that they do)
>
> So, if you are willing to publicly announce that you admit that your
> work is not related to the classic halting problem, the no problem with
> your claims.
>
> But, since you seem to keep making the claims that they do, we will keep
> pointing out that you are wrong.
>
I have reframed the halting problem** such that a universal halt decider
can no longer be shown to be impossible.
**Removing its pathological self-reference(Olcott 2004)
By doing this the conventional halting problem proof counter-examples
become halting decidable.
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
olcott
Mar 4, 2021, 12:13:11 PM3/4/21
to
On 3/4/2021 10:44 AM, Richard Damon wrote:
> I guess you are taking the extream option and not even staying in the
> field of logical proof.
>
> You can NOT just 'reframe' a problem and change its core definitions and
> now say that you have solved the problem.
>
> Yes, maybe you can say that with your new Olcott Infinite Recursion
> problem, the proofs like Linz do not apply. That doesn't say you have
> come up with a counter in the domain of the Conventional Halting Problem.
>
The reason that I can do this is that my revision to the halting problem
criteria provides the means for a universal halt decider to exist.
The only reason that the original halting problem is undecidable is
because it was asking an incorrect question.
sci.lang Jan 31, 2015, 7:58:34 PM
Is the concept of [incorrect question] new?
https://groups.google.com/g/sci.lang/c/lSdYexJ0ozo/m/aDN9-TYLHwIJ
Feb 20, 2015, 11:38:48 AM
The logical law of polar questions
https://groups.google.com/g/sci.lang/c/AO5Vlupeelo/m/nxJy7N2vULwJ
The revised question:
Does the simulation of the input program have to be stopped to prevent
its infinite execution?
Eliminates the pathological self-reference(Olcott 2004) error of the
halting problem question.
> field of logical proof.
>
> You can NOT just 'reframe' a problem and change its core definitions and
> now say that you have solved the problem.
>
> Yes, maybe you can say that with your new Olcott Infinite Recursion
> problem, the proofs like Linz do not apply. That doesn't say you have
> come up with a counter in the domain of the Conventional Halting Problem.
>
The reason that I can do this is that my revision to the halting problem
criteria provides the means for a universal halt decider to exist.
The only reason that the original halting problem is undecidable is
because it was asking an incorrect question.
sci.lang Jan 31, 2015, 7:58:34 PM
Is the concept of [incorrect question] new?
https://groups.google.com/g/sci.lang/c/lSdYexJ0ozo/m/aDN9-TYLHwIJ
Feb 20, 2015, 11:38:48 AM
The logical law of polar questions
https://groups.google.com/g/sci.lang/c/AO5Vlupeelo/m/nxJy7N2vULwJ
The revised question:
Does the simulation of the input program have to be stopped to prevent
its infinite execution?
Eliminates the pathological self-reference(Olcott 2004) error of the
halting problem question.
0 new messages