Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2586 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-02-26 13:53 -0600 |
| Last post | 2021-03-09 19:42 -0600 |
| Articles | 20 on this page of 38 — 10 participants |
Back to article view | Back to comp.software-eng
Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-26 13:53 -0600
Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 12:48 -0800
Re: Detecting infinite recursion Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-02-26 21:37 +0000
Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 15:26 -0800
Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-02-27 01:58 +0000
Re: Detecting infinite recursion Jeff Barnett <jbb@notatt.com> - 2021-02-26 21:32 -0700
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 14:20 -0600
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 14:40 -0600
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 21:30 -0600
Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-02-28 13:08 -0600
Re: Detecting infinite recursion (H_Hat is proved to be decidable) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-01 03:52 +0000
Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 21:32 -0600
Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-03 15:37 -0600
Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-02 09:29 -0600
Re: Detecting infinite recursion om@iki.fi (Otto J. Makela) - 2021-03-02 18:36 +0200
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 11:22 -0600
Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 17:46 +0000
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:00 -0600
Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:35 +0000
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:50 -0600
Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:57 +0000
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 14:20 -0600
Re: Detecting infinite recursion Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-03-02 12:57 -0800
Re: Detecting infinite recursion gazelle@shell.xmission.com (Kenny McCormack) - 2021-03-03 02:17 +0000
Re: Detecting infinite recursion (credit where it is due) olcott <NoOne@NoWhere.com> - 2021-03-02 18:45 -0600
Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 20:40 -0600
Re: Detecting infinite recursion (halt decider spec) Richard Damon <Richard@Damon-Family.org> - 2021-03-02 21:57 -0500
Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:03 -0600
Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:05 -0600
Re: Detecting infinite recursion (halt deciding criteria) olcott <NoOne@NoWhere.com> - 2021-03-03 15:50 -0600
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:52 -0600
Re: Detecting infinite recursion (rewritten) olcott <NoOne@NoWhere.com> - 2021-03-03 17:06 -0600
Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:55 -0600
Re: Detecting infinite recursion (pathological self-reference error) olcott <NoOne@NoWhere.com> - 2021-03-06 09:58 -0600
Re: Detecting infinite recursion Bonita Montero <Bonita.Montero@gmail.com> - 2021-03-07 16:38 +0100
Re: Detecting infinite recursion (halting problem) olcott <NoOne@NoWhere.com> - 2021-03-07 09:55 -0600
Refuting the halting problem proofs with fully operational code olcott <NoOne@NoWhere.com> - 2021-03-09 10:26 -0600
Re: Detecting infinite recursion (2021-03-09) olcott <NoOne@NoWhere.com> - 2021-03-09 19:42 -0600
Page 1 of 2 [1] 2 Next page →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-02-26 13:53 -0600 |
| Subject | Detecting infinite recursion |
| Message-ID | <3LadneKdoK8jzKT9nZ2dnUU78T3NnZ2d@giganews.com> |
(1) We know that every software function invoked with the same data must
have the same execution trace.
(2) When a software function invokes itself this is recursive invocation.
(3) When the second recursive invocation of a software function calls
itself with the same data as the prior invocation then it must have the
same execution trace as the prior invocation.
(4) When the second recursive invocation of a software function calls
itself with the same data has no conditional branch instructions
inbetween these two invocations then this is a case of infinite recursion.
(5) When the recursive invocation is replaced with a call to a software
system that simulates the execution of the calling function with its
same data, then this is equivalent to a recursive invocation.
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
Does everyone agree?
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [next] | [standalone]
| From | Siri Cruise <chine.bleu@yahoo.com> |
|---|---|
| Date | 2021-02-26 12:48 -0800 |
| Message-ID | <chine.bleu-8495E8.12481226022021@reader.eternal-september.org> |
| In reply to | #2586 |
In article <3LadneKdoK8jzKT9nZ2dnUU78T3NnZ2d@giganews.com>, olcott <NoOne@NoWhere.com> wrote: > Does everyone agree? P = \a.P(succ(a)) P 0 > (1) We know that every software function invoked with the same data must > have the same execution trace. When does a recursion use the same data? -- :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @ 'I desire mercy, not sacrifice.' /|\ Discordia: not just a religion but also a parody. This post / \ I am an Andrea Doria sockpuppet. insults Islam. Mohammed
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> |
|---|---|
| Date | 2021-02-26 21:37 +0000 |
| Message-ID | <tSd_H.261436$Wue5.69200@fx13.ams4> |
| In reply to | #2586 |
On 26/02/2021 19:53, olcott wrote:
> (1) We know that every software function invoked with the same data must have
> the same execution trace.
>
> (2) When a software function invokes itself this is recursive invocation.
>
> (3) When the second recursive invocation of a software function calls itself
> with the same data as the prior invocation then it must have the same execution
> trace as the prior invocation.
>
> (4) When the second recursive invocation of a software function calls itself
> with the same data has no conditional branch instructions inbetween these two
> invocations then this is a case of infinite recursion.
>
> (5) When the recursive invocation is replaced with a call to a software system
> that simulates the execution of the calling function with its same data, then
> this is equivalent to a recursive invocation.
>
> // P has address of H_Hat
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
> Does everyone agree?
No.
(-1) In general for an algorithm or program to perform useful work its functions
contain branching logic.
(0) Only pure functions may not modify mutable state.
...
(6) ???
(7) ???
(8) ???
...
(???) ???
...
/Flibble
--
😎
[toc] | [prev] | [next] | [standalone]
| From | Siri Cruise <chine.bleu@yahoo.com> |
|---|---|
| Date | 2021-02-26 15:26 -0800 |
| Message-ID | <chine.bleu-776407.15262726022021@reader.eternal-september.org> |
| In reply to | #2588 |
In article <tSd_H.261436$Wue5.69200@fx13.ams4>,
Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> wrote:
> (-1) In general for an algorithm or program to perform useful work its
> functions
> contain branching logic.
>
> (0) Only pure functions may not modify mutable state.
goldbach = \n.[
goldbachsum(n, 2, 2) -> goldbach(n+2);
true -> halt
]
goldbachsum = \n,r,s. [
r>=n -> false;
not prime(r, 2) -> goldbachsum(n, r+1, 2);
not prime(s, 2) -> goldbachsum(n, r, s+1);
r+s>n -> goldbachsum(n, r+1, 2);
r+s<n -> goldbachsum(n, r, s+1);
r+s=n -> true;
]
prime = \n,r.[
r*r>n -> true;
n mod r=0 -> false;
true -> prime(n, r+1)
]
Prove goldbach(2) halts or never halts and you win a Hero of the
Mathematics badge.
--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
Discordia: not just a religion but also a parody. This post / \
I am an Andrea Doria sockpuppet. insults Islam. Mohammed
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-02-27 01:58 +0000 |
| Message-ID | <20210226175333.826@kylheku.com> |
| In reply to | #2586 |
On 2021-02-26, olcott <NoOne@NoWhere.com> wrote:
> (1) We know that every software function invoked with the same data must
> have the same execution trace.
>
> (2) When a software function invokes itself this is recursive invocation.
>
> (3) When the second recursive invocation of a software function calls
> itself with the same data as the prior invocation then it must have the
> same execution trace as the prior invocation.
>
> (4) When the second recursive invocation of a software function calls
> itself with the same data has no conditional branch instructions
> inbetween these two invocations then this is a case of infinite recursion.
>
> (5) When the recursive invocation is replaced with a call to a software
> system that simulates the execution of the calling function with its
> same data, then this is equivalent to a recursive invocation.
>
> // P has address of H_Hat
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
> Does everyone agree?
If Simulate(P, P) replaces P(P), and the simulation is a faithful
replica of the processor, then nothing has changed.
You have previosuly written about a scheme in which Simulate
contains provisions for monitoring the execution. An outer Simulate has
instruction stream information from all inner Simulate calls and is able
to impose the rule that the simulation will only go to some fixed number
of levels, like 3. Let's call that N.
Firstly, what that does is change H_Hat: H_Hat is no longer infinitely
recursive, because Simulate detects an internal halting condition and
stops.
Secondly, the different recursion levels of H_Hat are not equivalent
to each other.
The outer-most H_Hat goes to N levels of recursion/simulation nesting.
The next lower nesting, though ostensibly executing the same logic,
only has N-1 remaining levels available to it before it will be
terminated.
The one after that N-2.
A function that terminates after U nestings is not the same function
as a similar one which terminates after V nestings, for U != V.
We must treat each H_Hat invocation at every nesting level i as a
different function H_Hat_i.
--
TXR Programming Language: http://nongnu.org/txr
Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2021-02-26 21:32 -0700 |
| Message-ID | <s1ci0a$3np$1@dont-email.me> |
| In reply to | #2586 |
On 2/26/2021 12:53 PM, olcott wrote:
> (1) We know that every software function invoked with the same data must
> have the same execution trace.
>
> (2) When a software function invokes itself this is recursive invocation.
>
> (3) When the second recursive invocation of a software function calls
> itself with the same data as the prior invocation then it must have the
> same execution trace as the prior invocation.
>
> (4) When the second recursive invocation of a software function calls
> itself with the same data has no conditional branch instructions
> inbetween these two invocations then this is a case of infinite recursion.
>
> (5) When the recursive invocation is replaced with a call to a software
> system that simulates the execution of the calling function with its
> same data, then this is equivalent to a recursive invocation.
>
> // P has address of H_Hat
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
> Does everyone agree?
You took off all of this time to come up with this. Remember when you
were pooping in the Lisp group without a clue of what you were talking
about or knowledge of any modern Lisp? Disgraceful! Consider a function
which accesses a variable bound outside its scope - there are many
variations here and this is why you should have learned some Lisp
instead of just pooping. Then the above is incorrect. Of course you have
something different in mind but are making a pig of terminology. Above
you say "software" function and that is what I'm talking about. If you
mean "mathematical" function, well do you remember the definition of a
mathematical function? In this case, you are correct but that has little
or nothing to do with software. I suggest another hiatus for you but
make it longer this time. Much longer.
--
Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-02-27 14:20 -0600 |
| Message-ID | <GcCdnUfqFrXxNKf9nZ2dnUU7-fHNnZ2d@giganews.com> |
| In reply to | #2586 |
On 2/27/2021 12:57 PM, Richard Damon wrote:
> On 2/27/21 10:26 AM, olcott wrote:
>> On 2/27/2021 9:18 AM, Richard Damon wrote:
>>> On 2/26/21 4:00 PM, olcott wrote:
>>>> On 2/26/2021 2:41 PM, Malcolm McLean wrote:
>>>>> On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
>>>>>> (1) We know that every software function invoked with the same data
>>>>>> must
>>>>>> have the same execution trace.
>>>>>>
>>>>> Yes, as long as by "data" we mean everything which the function reads,
>>>>> not
>>>>> only parameters.
>>>>>>
>>>>>> (2) When a software function invokes itself this is recursive
>>>>>> invocation.
>>>>>>
>>>>>> (3) When the second recursive invocation of a software function calls
>>>>>> itself with the same data as the prior invocation then it must have
>>>>>> the
>>>>>> same execution trace as the prior invocation.
>>>>>>
>>>>>> (4) When the second recursive invocation of a software function calls
>>>>>> itself with the same data has no conditional branch instructions
>>>>>> inbetween these two invocations then this is a case of infinite
>>>>>> recursion.
>>>>>>
>>>>> You don't need 4. If A calls itself with exactly the same data as it
>>>>> was
>>>>> originally invoked with, then it must be infitely recursive, even if
>>>>> there
>>>>> are conditional branches. It always takes the same branches. The only
>>>>> question is whether the first invocation makes the recursive call
>>>>> (depending
>>>>> how you are using the term "calls").
>>>>
>>>> This would seem to be true.
>>>>
>>>>>>
>>>>>> (5) When the recursive invocation is replaced with a call to a
>>>>>> software
>>>>>> system that simulates the execution of the calling function with its
>>>>>> same data, then this is equivalent to a recursive invocation.
>>>>>>
>>>>>> // P has address of H_Hat
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> Simulate(P, P);
>>>>>> }
>>>>>>
>>>>>> Does everyone agree?
>>>>>>
>>>>> Yes, you're right. But the caveat I would have is that this system is
>>>>> wide open
>>>>> to cheating, because it's hard to verify that Simulate() is not having
>>>>> access to
>>>>> data that varies by invocation level.
>>>>>
>>>>
>>>> If we hypothetically assume that it is a "given" that Simulate() only
>>>> simulates its input then we should be able to conclude that any
>>>> invocation meeting the above conditions specifies the equivalent of
>>>> infinite recursion.
>>>>
>>>
>>> One important point is that these conclusions assume that the function
>>> described actually exists and that (as stated) the 'software function'
>>> is actually a true model of a mathematical function (i.e., all inputs
>>> have been identified).
>>>
>>> One key point is that if the function is NOT described as an actual
>>> computation, but just as a description, then it is possible to make
>>> contradictory or wrong conclusions if the function is not actually
>>> finitely computable.
>>>
>>
>> void Simulate(u32 P, u32 I)
>> {
>> ((void(*)(int))P)(I);
>> }
>>
>>
>> // P has address of H_Hat
>> void H_Hat(u32 P)
>> {
>> Simulate(P, P);
>> }
>>
>>
>> Ignoring finite stack space then the above is infinitely recursive right?
>>
>
> Yes, because you haven't hit any of the limitations I mentioned.
>
> Simulate is fully defined and can be seen to not depend on anything not
> declared as an input.
>
If simulate was much more complex such that it simulated the execution
of the x86 machine language (shown below) then again the fact that
execution trace of H_Hat() shows that Simulate() has been invoked a
second time in sequence with the same input proves that H_Hat() is
infinitely recursive. (Assuming that Simulate() only simulates it input).
void H_Hat2(u32 P)
{
Simulate(P, P);
}
_H_Hat()
[000008a8](01) 55 push ebp
[000008a9](02) 8bec mov ebp,esp
[000008ab](03) 8b4508 mov eax,[ebp+08]
[000008ae](01) 50 push eax
[000008af](03) 8b4d08 mov ecx,[ebp+08]
[000008b2](01) 51 push ecx
[000008b3](05) e8c0fbffff call 00000478
[000008b8](03) 83c408 add esp,+08
[000008bb](01) 5d pop ebp
[000008bc](01) c3 ret
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
The two push instruction preceding the call to Simulate are the second
and first parameter respectively.
...[000008a8][00011220][0001122c](01) 55 push ebp
...[000008a9][00011220][0001122c](02) 8bec mov ebp,esp
...[000008ab][00011220][0001122c](03) 8b4508 mov eax,[ebp+08]
...[000008ae][0001121c][000008a8](01) 50 push eax ;
push second param: 8a8
...[000008af][0001121c][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][00011218][000008a8](01) 51 push ecx ;
push first param: 8a8
...[000008b3][00011214][000008b8](05) e8c0fbffff call 00000478 ;
call Simulate(0x8b8, 0x8b8)
...[000008a8][00011204][00011210](01) 55 push ebp
...[000008a9][00011204][00011210](02) 8bec mov ebp,esp
...[000008ab][00011204][00011210](03) 8b4508 mov eax,[ebp+08]
...[000008ae][00011200][000008a8](01) 50 push eax ;
push second param: 8a8
...[000008af][00011200][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][000111fc][000008a8](01) 51 push ecx ;
push first param: 8a8
...[000008b3][000111f8][000008b8](05) e8c0fbffff call 00000478 ;
call Simulate(0x8b8, 0x8b8)
Now we can see that H_Hat's call to Simulate causes H_Hat to be
infinitely recursive because its execution trace shows two invocations
of Simulate from H_Hat each with identical input.
--
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-02-27 14:40 -0600 |
| Message-ID | <B9KdnRWaiqKBM6f9nZ2dnUU7-bPNnZ2d@giganews.com> |
| In reply to | #2586 |
On 2/27/2021 12:57 PM, Richard Damon wrote:
> On 2/27/21 10:26 AM, olcott wrote:
>> On 2/27/2021 9:18 AM, Richard Damon wrote:
>>> On 2/26/21 4:00 PM, olcott wrote:
>>>> On 2/26/2021 2:41 PM, Malcolm McLean wrote:
>>>>> On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
>>>>>> (1) We know that every software function invoked with the same data
>>>>>> must
>>>>>> have the same execution trace.
>>>>>>
>>>>> Yes, as long as by "data" we mean everything which the function reads,
>>>>> not
>>>>> only parameters.
>>>>>>
>>>>>> (2) When a software function invokes itself this is recursive
>>>>>> invocation.
>>>>>>
>>>>>> (3) When the second recursive invocation of a software function calls
>>>>>> itself with the same data as the prior invocation then it must have
>>>>>> the
>>>>>> same execution trace as the prior invocation.
>>>>>>
>>>>>> (4) When the second recursive invocation of a software function calls
>>>>>> itself with the same data has no conditional branch instructions
>>>>>> inbetween these two invocations then this is a case of infinite
>>>>>> recursion.
>>>>>>
>>>>> You don't need 4. If A calls itself with exactly the same data as it
>>>>> was
>>>>> originally invoked with, then it must be infitely recursive, even if
>>>>> there
>>>>> are conditional branches. It always takes the same branches. The only
>>>>> question is whether the first invocation makes the recursive call
>>>>> (depending
>>>>> how you are using the term "calls").
>>>>
>>>> This would seem to be true.
>>>>
>>>>>>
>>>>>> (5) When the recursive invocation is replaced with a call to a
>>>>>> software
>>>>>> system that simulates the execution of the calling function with its
>>>>>> same data, then this is equivalent to a recursive invocation.
>>>>>>
>>>>>> // P has address of H_Hat
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> Simulate(P, P);
>>>>>> }
>>>>>>
>>>>>> Does everyone agree?
>>>>>>
>>>>> Yes, you're right. But the caveat I would have is that this system is
>>>>> wide open
>>>>> to cheating, because it's hard to verify that Simulate() is not having
>>>>> access to
>>>>> data that varies by invocation level.
>>>>>
>>>>
>>>> If we hypothetically assume that it is a "given" that Simulate() only
>>>> simulates its input then we should be able to conclude that any
>>>> invocation meeting the above conditions specifies the equivalent of
>>>> infinite recursion.
>>>>
>>>
>>> One important point is that these conclusions assume that the function
>>> described actually exists and that (as stated) the 'software function'
>>> is actually a true model of a mathematical function (i.e., all inputs
>>> have been identified).
>>>
>>> One key point is that if the function is NOT described as an actual
>>> computation, but just as a description, then it is possible to make
>>> contradictory or wrong conclusions if the function is not actually
>>> finitely computable.
>>>
>>
>> void Simulate(u32 P, u32 I)
>> {
>> ((void(*)(int))P)(I);
>> }
>>
>>
>> // P has address of H_Hat
>> void H_Hat(u32 P)
>> {
>> Simulate(P, P);
>> }
>>
>>
>> Ignoring finite stack space then the above is infinitely recursive right?
>>
>
> Yes, because you haven't hit any of the limitations I mentioned.
>
> Simulate is fully defined and can be seen to not depend on anything not
> declared as an input.
>
When simulate emulates the execution of the x86 machine language (shown
below) then the execution trace of H_Hat() showing that Simulate() has
been invoked a second time in sequence with the same input proves that
H_Hat() is infinitely recursive. (Assuming that Simulate() only
simulates it input).
// P has the machine address of H_Hat
void H_Hat2(u32 P)
{
Simulate(P, P);
}
_H_Hat()
[000008a8](01) 55 push ebp
[000008a9](02) 8bec mov ebp,esp
[000008ab](03) 8b4508 mov eax,[ebp+08]
[000008ae](01) 50 push eax
[000008af](03) 8b4d08 mov ecx,[ebp+08]
[000008b2](01) 51 push ecx
[000008b3](05) e8c0fbffff call 00000478
[000008b8](03) 83c408 add esp,+08
[000008bb](01) 5d pop ebp
[000008bc](01) c3 ret
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
Push instructions have pushed the value shown in their in the third
column. The two push instructions preceding the call to Simulate are its
second and first parameters respectively.
...[000008a8][00011220][0001122c](01) 55 push ebp
...[000008a9][00011220][0001122c](02) 8bec mov ebp,esp
...[000008ab][00011220][0001122c](03) 8b4508 mov eax,[ebp+08]
...[000008ae][0001121c][000008a8](01) 50 push eax
...[000008af][0001121c][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][00011218][000008a8](01) 51 push ecx
Call Simulate(000008a8, 000008a8)
...[000008b3][00011214][000008b8](05) e8c0fbffff call 00000478
...[000008a8][00011204][00011210](01) 55 push ebp
...[000008a9][00011204][00011210](02) 8bec mov ebp,esp
...[000008ab][00011204][00011210](03) 8b4508 mov eax,[ebp+08]
...[000008ae][00011200][000008a8](01) 50 push eax
...[000008af][00011200][000008a8](03) 8b4d08 mov ecx,[ebp+08]
...[000008b2][000111fc][000008a8](01) 51 push ecx
Call Simulate(000008a8, 000008a8)
...[000008b3][000111f8][000008b8](05) e8c0fbffff call 00000478
Now we can see that H_Hat's call to Simulate() causes H_Hat() to be
infinitely recursive because its execution trace shows two invocations
of Simulate() from H_Hat() each with identical input.
--
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-02-27 21:30 -0600 |
| Message-ID | <IuGdnQFwjfPUk6b9nZ2dnUU7-afNnZ2d@giganews.com> |
| In reply to | #2593 |
On 2/27/2021 9:01 PM, Richard Damon wrote:
> On 2/27/21 9:36 PM, olcott wrote:
>> On 2/27/2021 8:19 PM, Richard Damon wrote:
>>> On 2/27/21 3:40 PM, olcott wrote:
>>>> On 2/27/2021 12:57 PM, Richard Damon wrote:
>>>>> On 2/27/21 10:26 AM, olcott wrote:
>>>>>> On 2/27/2021 9:18 AM, Richard Damon wrote:
>>>>>>> On 2/26/21 4:00 PM, olcott wrote:
>>>>>>>> On 2/26/2021 2:41 PM, Malcolm McLean wrote:
>>>>>>>>> On Friday, 26 February 2021 at 19:53:37 UTC, olcott wrote:
>>>>>>>>>> (1) We know that every software function invoked with the same
>>>>>>>>>> data
>>>>>>>>>> must
>>>>>>>>>> have the same execution trace.
>>>>>>>>>>
>>>>>>>>> Yes, as long as by "data" we mean everything which the function
>>>>>>>>> reads,
>>>>>>>>> not
>>>>>>>>> only parameters.
>>>>>>>>>>
>>>>>>>>>> (2) When a software function invokes itself this is recursive
>>>>>>>>>> invocation.
>>>>>>>>>>
>>>>>>>>>> (3) When the second recursive invocation of a software function
>>>>>>>>>> calls
>>>>>>>>>> itself with the same data as the prior invocation then it must
>>>>>>>>>> have
>>>>>>>>>> the
>>>>>>>>>> same execution trace as the prior invocation.
>>>>>>>>>>
>>>>>>>>>> (4) When the second recursive invocation of a software function
>>>>>>>>>> calls
>>>>>>>>>> itself with the same data has no conditional branch instructions
>>>>>>>>>> inbetween these two invocations then this is a case of infinite
>>>>>>>>>> recursion.
>>>>>>>>>>
>>>>>>>>> You don't need 4. If A calls itself with exactly the same data
>>>>>>>>> as it
>>>>>>>>> was
>>>>>>>>> originally invoked with, then it must be infitely recursive,
>>>>>>>>> even if
>>>>>>>>> there
>>>>>>>>> are conditional branches. It always takes the same branches. The
>>>>>>>>> only
>>>>>>>>> question is whether the first invocation makes the recursive call
>>>>>>>>> (depending
>>>>>>>>> how you are using the term "calls").
>>>>>>>>
>>>>>>>> This would seem to be true.
>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> (5) When the recursive invocation is replaced with a call to a
>>>>>>>>>> software
>>>>>>>>>> system that simulates the execution of the calling function
>>>>>>>>>> with its
>>>>>>>>>> same data, then this is equivalent to a recursive invocation.
>>>>>>>>>>
>>>>>>>>>> // P has address of H_Hat
>>>>>>>>>> void H_Hat(u32 P)
>>>>>>>>>> {
>>>>>>>>>> Simulate(P, P);
>>>>>>>>>> }
>>>>>>>>>>
>>>>>>>>>> Does everyone agree?
>>>>>>>>>>
>>>>>>>>> Yes, you're right. But the caveat I would have is that this
>>>>>>>>> system is
>>>>>>>>> wide open
>>>>>>>>> to cheating, because it's hard to verify that Simulate() is not
>>>>>>>>> having
>>>>>>>>> access to
>>>>>>>>> data that varies by invocation level.
>>>>>>>>>
>>>>>>>>
>>>>>>>> If we hypothetically assume that it is a "given" that Simulate()
>>>>>>>> only
>>>>>>>> simulates its input then we should be able to conclude that any
>>>>>>>> invocation meeting the above conditions specifies the equivalent of
>>>>>>>> infinite recursion.
>>>>>>>>
>>>>>>>
>>>>>>> One important point is that these conclusions assume that the
>>>>>>> function
>>>>>>> described actually exists and that (as stated) the 'software
>>>>>>> function'
>>>>>>> is actually a true model of a mathematical function (i.e., all inputs
>>>>>>> have been identified).
>>>>>>>
>>>>>>> One key point is that if the function is NOT described as an actual
>>>>>>> computation, but just as a description, then it is possible to make
>>>>>>> contradictory or wrong conclusions if the function is not actually
>>>>>>> finitely computable.
>>>>>>>
>>>>>>
>>>>>> void Simulate(u32 P, u32 I)
>>>>>> {
>>>>>> ((void(*)(int))P)(I);
>>>>>> }
>>>>>>
>>>>>>
>>>>>> // P has address of H_Hat
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> Simulate(P, P);
>>>>>> }
>>>>>>
>>>>>>
>>>>>> Ignoring finite stack space then the above is infinitely recursive
>>>>>> right?
>>>>>>
>>>>>
>>>>> Yes, because you haven't hit any of the limitations I mentioned.
>>>>>
>>>>> Simulate is fully defined and can be seen to not depend on anything not
>>>>> declared as an input.
>>>>>
>>>>
>>>> When simulate emulates the execution of the x86 machine language (shown
>>>> below) then the execution trace of H_Hat() showing that Simulate() has
>>>> been invoked a second time in sequence with the same input proves that
>>>> H_Hat() is infinitely recursive. (Assuming that Simulate() only
>>>> simulates it input).
>>>
>>> You are now getting on thin ice, since the code to Simulate isn't
>>> provided, its obedience to the requirements isn't verifable.
>>
>> I am not asking you to verify the code. The actual code and its full
>> execution trace is many hundreds of pages.
>>
>> I am asking you whether or not code with the properties that I have
>> provided can be necessarily determined to be infinitely recursive.
>
> First, a lot of the equivocation is because you have shown yourself in
> the past to 'try to pull a fast one' by misusing quotes.
>
> If the actual virtual execution path of the program under the simulation
> function is identical to that of the first program, then of course the
> answer would be yes. The issue is that, based on past performance, you
> are apt to some point in the future break one of those conditions and
> wish to claim the answer has to be the same, but it doesn't.
Emulating an x86 machine with an x86 machine is functionally equivalent
to direct execution yet has many thousands of additional steps.
>
>>
>>>>
>>>>
>>>> // P has the machine address of H_Hat
>>>> void H_Hat2(u32 P)
>>>> {
>>>> Simulate(P, P);
>>>> }
>>>>
>>>> _H_Hat()
>>>> [000008a8](01) 55 push ebp
>>>> [000008a9](02) 8bec mov ebp,esp
>>>> [000008ab](03) 8b4508 mov eax,[ebp+08]
>>>> [000008ae](01) 50 push eax
>>>> [000008af](03) 8b4d08 mov ecx,[ebp+08]
>>>> [000008b2](01) 51 push ecx
>>>> [000008b3](05) e8c0fbffff call 00000478
>>>> [000008b8](03) 83c408 add esp,+08
>>>> [000008bb](01) 5d pop ebp
>>>> [000008bc](01) c3 ret
>>>>
>>>> Columns
>>>> (1) Machine address of instruction
>>>> (2) Machine address of top of stack
>>>> (3) Value of top of stack after instruction executed
>>>> (4) Number of bytes of machine code
>>>>
>>>> Push instructions have pushed the value shown in their in the third
>>>> column. The two push instructions preceding the call to Simulate are its
>>>> second and first parameters respectively.
>>>>
>>>> ...[000008a8][00011220][0001122c](01) 55 push ebp
>>>> ...[000008a9][00011220][0001122c](02) 8bec mov ebp,esp
>>>> ...[000008ab][00011220][0001122c](03) 8b4508 mov eax,[ebp+08]
>>>> ...[000008ae][0001121c][000008a8](01) 50 push eax
>>>> ...[000008af][0001121c][000008a8](03) 8b4d08 mov ecx,[ebp+08]
>>>> ...[000008b2][00011218][000008a8](01) 51 push ecx
>>>>
>>>> Call Simulate(000008a8, 000008a8)
>>>> ...[000008b3][00011214][000008b8](05) e8c0fbffff call 00000478
>>>>
>>>> ...[000008a8][00011204][00011210](01) 55 push ebp
>>>> ...[000008a9][00011204][00011210](02) 8bec mov ebp,esp
>>>> ...[000008ab][00011204][00011210](03) 8b4508 mov eax,[ebp+08]
>>>> ...[000008ae][00011200][000008a8](01) 50 push eax
>>>> ...[000008af][00011200][000008a8](03) 8b4d08 mov ecx,[ebp+08]
>>>> ...[000008b2][000111fc][000008a8](01) 51 push ecx
>>>>
>>>> Call Simulate(000008a8, 000008a8)
>>>> ...[000008b3][000111f8][000008b8](05) e8c0fbffff call 00000478
>>>>
>>>> Now we can see that H_Hat's call to Simulate() causes H_Hat() to be
>>>> infinitely recursive because its execution trace shows two invocations
>>>> of Simulate() from H_Hat() each with identical input.
>>>>
>>>
>>> Note here also that your trace become incomplete here, as we DON't have
>>> a complete cycle, but need to work on assumptions of benign action of
>>> the Simulate function.
>>>
>>
>> Because the simulator only simulates it is functionally equivalent to
>> the original version shown above.
>>
>> Yes. I don't care about your opinions on any of the other details. I
>> only want an objective assessment regarding whether or not the code that
>> I specified with the assumptions that I specified can be determined to
>> be necessarily infinitely recursive.
>>
>
> And as I said above, Yes, as long as your code meets the requirements
> stated, and the usage is within those parameters, yes.
>
> Note, the trace by itself is NOT sufficient, it needs to be combined
> with the description and restriction of the simulator for it to provide
> the 'proof' you are describing.
The trace combined with the assumption that the simulator only simulates
is enough within the context of this assumption. If this is not enough
for you then your understanding is insufficent.
> Note again, as you trimmed the remark, Simulate does NOT qualify as a
> UTM equivalent as it ooes not run the simulation in an isolated memory
> space, it mixing of the machine it is operationg on with the machine it
> is simulating makes it unsuitable for that purpose.
>
That is a whole other can of worms that will not be addressed for a very
long time. Unless I proceed in the smallest possible increments of my
elaboration people jump to the end based on false assumptions never even
realizing that they are making any assumptions at all.
If we proceed with a purely objective analysis with zero opinions
what-so-ever involved then and only then can be get through to the end.
So let's sum up where we are:
(1) The following code is obviously infinitely recursive:
void Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
}
// P has address of H_Hat
void H_Hat(u32 P)
{
Simulate(P, P);
}
(2) If the Simulate() function is replaced with an x86 emulator that
emulates its input then this too is obviously infinitely recursive.
--
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-02-28 13:08 -0600 |
| Subject | Re: Detecting infinite recursion (H_Hat is proved to be decidable) |
| Message-ID | <vsWdnaqGeKOtd6b9nZ2dnUU7-W3NnZ2d@giganews.com> |
| In reply to | #2593 |
On 2/28/2021 11:20 AM, Mr Flibble wrote:
> On 28/02/2021 16:34, olcott wrote:
>> On 2/28/2021 10:26 AM, Mr Flibble wrote:
>>> On 28/02/2021 14:34, olcott wrote:
>>>> On 2/28/2021 8:24 AM, Mr Flibble wrote:
>>>>> On 28/02/2021 04:10, olcott wrote:
>>>>>> By 35 years of software engineering I know that things are much
>>>>>> more easily understood at very high level abstractions and when
>>>>>> you present a myriad of details then things become utterly
>>>>>> incomprehensible.
>>>>>
>>>>> No, we want an implementation which WE can feed input (program and
>>>>> data) of OUR choosing in order to test YOUR claims. You won't do
>>>>> this because you know it doesn't work. You are selling snake oil,
>>>>> nothing more.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> As soon as it is universally agreed that I am hypothetically correct
>>>> then I will provide access to the system. If it is universally
>>>> agreed that within my assumptions H_Hat would be correctly decided
>>>> and this refutes the halting problem proofs then I will provide
>>>> access to my system.
>>>
>>> Why do we have to wait? What are you hiding? Are you hiding that you
>>> only have snake oil?
>>>
>>> /Flibble
>>>
>>
>> You have to wait primarily to provide the incentive for a thorough
>> review. Most people here have already rejected what I have said
>> out-of-hand without review. The rest rejected what I have said on the
>> basis of false assumptions that they were not ever aware were
>> assumptions.
>
> Part of the problem is what you post to these newsgroups is ambiguous
> and open to interpretation. Code is not open to interpretation and if we
> could run your implementation we could validate your claims ourselves.
> Publish now please unless of course you only have snake oil, which seems
> to be the case.
>
> /Flibble
>
This instance of H_Hat() is proved to be decidable and all the code is
provided. This H_Hat() calls Simulate() that returns true whenever its
input halts.
int Simulate(u32 P, u32 I)
{
((void(*)(int))P)(I);
return 1;
}
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Simulate(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
_Simulate()
[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](05) b801000000 mov eax,00000001
[0000048a](01) 5d pop ebp
[0000048b](01) c3 ret
_H_Hat()
[00000858](01) 55 push ebp
[00000859](02) 8bec mov ebp,esp
[0000085b](01) 51 push ecx
[0000085c](03) 8b4508 mov eax,[ebp+08]
[0000085f](01) 50 push eax
[00000860](03) 8b4d08 mov ecx,[ebp+08]
[00000863](01) 51 push ecx
[00000864](05) e80ffcffff call 00000478
[00000869](03) 83c408 add esp,+08
[0000086c](03) 8945fc mov [ebp-04],eax
[0000086f](04) 837dfc00 cmp dword [ebp-04],+00
[00000873](02) 7402 jz 00000877
[00000875](02) ebfe jmp 00000875
[00000877](02) 8be5 mov esp,ebp
[00000879](01) 5d pop ebp
[0000087a](01) c3 ret
Because the execution trace shown below shows that H_Hat() invokes
Simulate() with the same data two times in sequence we can conclude that
H_Hat() is invoked in infinite recursion.
Push instructions have already pushed the value shown in their in the
third column. The two push instructions preceding the call to Simulate()
are its second and first parameters respectively.
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text
...[00000858][000111c5][000111d1](01) 55 push ebp
...[00000859][000111c5][000111d1](02) 8bec mov ebp,esp
...[0000085b][000111c1][00000000](01) 51 push ecx
...[0000085c][000111c1][00000000](03) 8b4508 mov eax,[ebp+08]
...[0000085f][000111bd][00000858](01) 50 push eax
...[00000860][000111bd][00000858](03) 8b4d08 mov ecx,[ebp+08]
...[00000863][000111b9][00000858](01) 51 push ecx
; Call Simulate(0x858, 0x858);
...[00000864][000111b5][00000869](05) e80ffcffff call 00000478
...[00000858][000111a5][000111b1](01) 55 push ebp
...[00000859][000111a5][000111b1](02) 8bec mov ebp,esp
...[0000085b][000111a1][00000858](01) 51 push ecx
...[0000085c][000111a1][00000858](03) 8b4508 mov eax,[ebp+08]
...[0000085f][0001119d][00000858](01) 50 push eax
...[00000860][0001119d][00000858](03) 8b4d08 mov ecx,[ebp+08]
...[00000863][00011199][00000858](01) 51 push ecx
; Call Simulate(0x858, 0x858);
...[00000864][00011195][00000869](05) e80ffcffff call 00000478
--
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-03-01 03:52 +0000 |
| Subject | Re: Detecting infinite recursion (H_Hat is proved to be decidable) |
| Message-ID | <20210228194941.651@kylheku.com> |
| In reply to | #2595 |
On 2021-02-28, olcott <NoOne@NoWhere.com> wrote: > This instance of H_Hat() is proved to be decidable and all the code is > provided. This H_Hat() calls Simulate() that returns true whenever its > input halts. Your eyes keep slipping off the carrot every once in a short while. What's not decidable is universal halting, not any one specific program and its input. Any method by which you can decide a specific program and its input will also work for some other programs/inputs, but not all of them. -- TXR Programming Language: http://nongnu.org/txr Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-01 21:32 -0600 |
| Subject | Re: Detecting infinite recursion (H_Hat is proved to be decidable) |
| Message-ID | <Z9OdnSXKROxSLKD9nZ2dnUU7-bfNnZ2d@giganews.com> |
| In reply to | #2596 |
On 3/1/2021 9:05 PM, olcott wrote:
> On 3/1/2021 8:22 PM, Mike Terry wrote:
>> On 02/03/2021 01:31, olcott wrote:
>>> On 3/1/2021 7:00 PM, Mike Terry wrote:
>>>> On 01/03/2021 23:00, olcott wrote:
>>>>> On 3/1/2021 4:42 PM, Mike Terry wrote:
>>>>>> On 01/03/2021 20:22, olcott wrote:
>>>>>>> On 3/1/2021 1:39 PM, Kaz Kylheku wrote:
>>>>>>>> On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>> On 3/1/2021 12:25 PM, Kaz Kylheku wrote:
>>>>>>>>>> On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>> On 3/1/2021 10:52 AM, Kaz Kylheku wrote:
>>>>>>>>>>> I already acknowledged this. When an equivalent computation
>>>>>>>>>>> is run on a
>>>>>>>>>>> machine without resource limits (such as a TM) then this
>>>>>>>>>>> computation is
>>>>>>>>>>> infinitely recursive.
>>>>>>>>>>
>>>>>>>>>> That depends on what you mean by "equivalent". Since you have
>>>>>>>>>> tied the
>>>>>>>>>> validity your work to the x86 representation, a Turing Machine
>>>>>>>>>> version
>>>>>>>>>> of your program, to be equivalent, has to contain the x86
>>>>>>>>>> program, and
>>>>>>>>>> the simulator, faithfully reproducing the same resource
>>>>>>>>>> limitations.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> A RASP machine is known to be equivalent to a UTM.
>>>>>>>>>
>>>>>>>>> Thus the RASP is to the RAM as the Universal Turing machine is
>>>>>>>>> to the
>>>>>>>>> Turing machine. The RASP is an example of the von Neumann
>>>>>>>>> architecture.
>>>>>>>>> https://en.wikipedia.org/wiki/Random-access_stored-program_machine
>>>>>>>>>
>>>>>>>>> The x86 language is another exapmle of the von Neumann
>>>>>>>>> architecture.
>>>>>>>>> All computations implemented using the von Neumann architecture
>>>>>>>>> are
>>>>>>>>> equivalent to one another as long as they do not require more
>>>>>>>>> memory
>>>>>>>>> than is available.
>>>>>>>>>
>>>>>>>>> Thus all computations implemented using the von Neumann
>>>>>>>>> architecture are
>>>>>>>>> equivalent UTM computations as long as they do not require more
>>>>>>>>> memory
>>>>>>>>> than is available.
>>>>>>>>
>>>>>>>> That is true; but an infinite recursion does require
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>> When I say that the x86 emulator: Simulate() is functionally
>>>>>>>>>>> equivalent
>>>>>>>>>>> to this code:
>>>>>>>>>>>
>>>>>>>>>>> int Simulate(u32 P, u32 I)
>>>>>>>>>>> {
>>>>>>>>>>> ((void(*)(int))P)(I);
>>>>>>>>>>> return 1;
>>>>>>>>>>> }
>>>>>>>>>>>
>>>>>>>>>>> That is all that need be said about the capabilities of the
>>>>>>>>>>> x86 emulator.
>>>>>>>>>>
>>>>>>>>>> Yes; then clearly, the H_Hat(P, P) call (with the right casts
>>>>>>>>>> put in)
>>>>>>>>>> denotes a runaway recursive call.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> So we agree on this point?
>>>>>>>>
>>>>>>>> Why wouldn't we? It's obviously a runaway recursive call.
>>>>>>>>
>>>>>>>>> When we know that Simulate() is an x86 emulator that is
>>>>>>>>> functionally
>>>>>>>>> equivalent to direct execution of its input then from the
>>>>>>>>> execution
>>>>>>>>> trace of the execution of this input (including the inputs to
>>>>>>>>> functions
>>>>>>>>> stored on the stack) alone we can decide that H_Hat() is
>>>>>>>>> infinitely
>>>>>>>>> recursive.
>>>>>>>>
>>>>>>>> Yes.
>>>>>>>>
>>>>>>>> In a static call graph of a program, we can spot loops.
>>>>>>>>
>>>>>>>> For instance a simple infinite loop occurs when a basic block
>>>>>>>> jumps to
>>>>>>>> itself.
>>>>>>>>
>>>>>>>> A basic block has no branching instructions anywhere, except as
>>>>>>>> possibly
>>>>>>>> the last instruction. If that last instruction is an
>>>>>>>> unconditional jump
>>>>>>>> back to that block, that is an infinite loop.
>>>>>>>>
>>>>>>>> Compilers do this kind of control flow analysis to find loops,
>>>>>>>> where certain optimizations can be concentrated (e.g. giving more
>>>>>>>> registers to variables in nested loops).
>>>>>>>>
>>>>>>>> If we monitor the execution dynamically, we can likewise identify
>>>>>>>> "dynamic basic blocks" sequences of unconditionally executed
>>>>>>>> instructions with no branches, and we can detect infinite loops.
>>>>>>>> (Possibly ones that contain a stack push, if the jump is actually
>>>>>>>> a subroutine call.)
>>>>>>>>
>>>>>>>> If we simply identify the situation, but don't interfere in it,
>>>>>>>> then the
>>>>>>>> situation persists: there is runaway recursion.
>>>>>>>>
>>>>>>>
>>>>>>> When this same simulator monitors its own simulation it could
>>>>>>> figure out that the H_Hat() invocation of itself is infinitely
>>>>>>> recursive.
>>>>>>>
>>>>>>
>>>>>> I'm afraid that's "wrong-headed" thinking, because Simulate simply
>>>>>> DOES NOT monitor its own simulation, so you can't talk about when
>>>>>> it does something IT DOESN'T DO. :) The same mental confusion
>>>>>> underlies your ".. /would/ fail to terminate /if/ ABNHBD() didn't
>>>>>> abort the emulation", and other anthropomorphisms you make for TMs.
>>>>>>
>>>>>
>>>>> So in other words you cannot possibly begin to imagine that a
>>>>> software function could be adapted to add functionality.
>>>>>
>>>>>> /We/ can figure out that the above H_Hat is infinitely recursive,
>>>>>> but /we/ are not Simulate, so H_Hat is not our "We_hat", and this
>>>>>> says nothing about the Linz proof.
>>>>>>
>>>>>> The /Simulate/ as you've described it (pure emulation) /cannot/
>>>>>> "figure it out", because it fails to return and so doesn't
>>>>>> "figure" anything. Again, nothing much to say re HP proof.
>>>>>>
>>>>>> We could code a /new/ emulator routine Simulate2 (distinct from
>>>>>> H_Hat and Simulate above) which has monitoring logic, and use it
>>>>>> to examine a simulation of the H_Hat above calling Simulate(H_Hat)
>>>>>> (note: NOT calling Simulate2...), and this Simulate2 could
>>>>>> correctly decide that H_Hat(H_Hat) does not terminate.
>>>>>>
>>>>>> But H_Hat is not the "hatted" machine for Simulate2, so this also
>>>>>> is of little interest. Nobody claims that "no decider can
>>>>>> correctly decide halting for H_Hat", only that H does not
>>>>>> correctly decide halting for its own H_Hat.
>>>>>>
>>>>>> If we "update" H_Hat so that instead of calling Simulate, it calls
>>>>>> the new Simulate2, then we have a /new/ program H_Hat2, and a
>>>>>> /new/ calculation to consider. When H_Hat2 examines the
>>>>>> calculation H_Hat2(H_Hat2), with H_Hat2 calling Simulate2 etc.,
>>>>>> then H_Hat2 /*cannot*/ "figure out" that the calculation has
>>>>>> infinite recursion, BECAUSE IT DOESN'T. It can certainly /decide/
>>>>>> that H_Hat2 is infinitely recursive, but that would just be
>>>>>> Simulate2 deciding incorrectly. All in line with Linz proof.
>>>>>>
>>>>>> Remember, Simulate2 is not a "pure emulator" like Simulate, so the
>>>>>> fact that there may be two nested emulated calls to Simulate2 with
>>>>>> the same argument IS NOT PROOF OF INFINITE RECURSION.
>>>>>
>>>>> When Simulate2() is identical to Simulate() in every way except
>>>>> that it also examines the execution trace of its input to figure
>>>>> out that its input is calling Simulate2() in infinite recursion
>>>>> then by logical necessity H_Hat() is still infinitely recursive.
>>>>
>>>> ?
>>>>
>>>> H_Hat doesn't call Simulate2. Maybe you mean H_Hat2 ?
>>>>
>>>> Obviously the /H_Hat/ calculation is "still" infinitely recursive,
>>>> because that calculation has never changed - by definition it calls
>>>> Simulate (not Simulate2).
>>>>
>>>> Hmm, your phrase "figuring out" isn't a standard CS term - I've
>>>> guessed it to mean that Simulate2 returns some different rc (not 1)
>>>> when it detects the nested calls to Simulate2 with the same input
>>>> data, thus making a different decision to the rc=1 [halts] decision.
>>>> Maybe you mean something else?
>>>>
>>>>
>>>> Mike.
>>>>
>> >
>>> An x86 emulator could keep track of all of the details of the
>>> execution trace of any input. If the original Simulate() was adapted
>>> to have this feature and the names remain the same then H_Hat() would
>>> invoke this updated version of Simulate() and still be infinitely
>>> recursive.
>>
>> So was my guess right? Does "figuring out" mean that Simulate2
>> returns some different rc (not 1) when it detects the nested calls to
>> Simulate2 with the same input data, thus making a different decision
>> to the rc=1 [halts] decision? All you've done is replace "figuring
>> out" with "keep track of" which is no better.
>>
>>>
>>> When software engineers add features to existing functions they do
>>> not change the names.
>>
>> What they do is change the versions. But you are not a software
>> engineer, so maybe you don't know about version numbers.
>>
>> Software engineers use version control systems so that if required
>> they can recreate the software at whatever point in the development
>> cycle is required, so there will not be confusion over what code is
>> being used/discussed at any time.
>>
>
> This is the version number of the whole system at that point in time. I
> worked on defense projects using version control. The function almost
> always keep their original names and merely acquire additional
> functionality.
>
>> In contrast, /you/ habitually use the same name for different
>> programs, and different names for the same programs. I suspect this
>> is because in part your arguments rely on confusing different programs
>> as being the same thing, in various ways. So it seems to me that you
>> do this deliberately. This is the exact opposite to how a software
>> engineer or professional programmer would behave.
>>
>
> There are only three programs that I will be talking about:
>
> // P has the machine address of H_Hat()
> void H_Hat(u32 P)
> {
> u32 Input_Halts = Simulate(P, P);
> if (Input_Halts)
> HERE: goto HERE;
> return;
> }
>
> That calls Simulate(P, P) and as the conversation progresses will
> gradually be adapted step-by-step until it becomes Halts(P, P).
>
> There will not be any version numbers for Simulate() because Simulate()
> is merely a conversational convention used to construct complete
> understanding of Halts() in small incremental steps.
>
>
>> If it is not deliberate, I suggest you just affix versions to the end
>> of your programs e.g. "H_Hat2" when they change. That's easier than
>> full versions, e.g. "H_Hat (V2.1.0.0)" and more appropriate for
>> newsgroup discussions.
>>
>>
>> Mike.
int Simulate_1(u32 P, u32 I);
Emulates the x86 code pointed to by machine address P with data at
machine address I.
int Simulate_2(u32 P, u32 I);
Same as Simulate_1() except keeps track of the execution trace of its
input including the data passed to any function invocations.
int Simulate_3(u32 P, u32 I);
Same as Simulate_2() except examines the saved execution trace
immediately after emulating each x86 language instruction to determine
whether or not this input specifies infinite recursion.
It should be self-evident that whenever any of these versions is
substituted into the body of H_Hat() that H_Hat() remains infinitely
recursive.
It should be self-evident that Simulate_3() can easily determine the
infinite recursion of H_Hat() on the basis its execution trace.
--
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-03-03 15:37 -0600 |
| Subject | Re: Detecting infinite recursion (H_Hat is proved to be decidable) |
| Message-ID | <5N2dnX-6zfkwnN39nZ2dnUU7-K3NnZ2d@giganews.com> |
| In reply to | #2598 |
On 3/3/2021 3:13 PM, Mike Terry wrote:
> On 03/03/2021 18:41, olcott wrote:
>> On 3/3/2021 8:54 AM, Mike Terry wrote:
>>> On 02/03/2021 03:32, olcott wrote:
>>>> On 3/1/2021 9:05 PM, olcott wrote:
>>>>> On 3/1/2021 8:22 PM, Mike Terry wrote:
>>>>>> On 02/03/2021 01:31, olcott wrote:
>>>>>>> On 3/1/2021 7:00 PM, Mike Terry wrote:
>>>>>>>> On 01/03/2021 23:00, olcott wrote:
>>>>>>>>> On 3/1/2021 4:42 PM, Mike Terry wrote:
>>>>>>>>>> On 01/03/2021 20:22, olcott wrote:
>>>>>>>>>>> On 3/1/2021 1:39 PM, Kaz Kylheku wrote:
>>>>>>>>>>>> On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>> On 3/1/2021 12:25 PM, Kaz Kylheku wrote:
>>>>>>>>>>>>>> On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>>> On 3/1/2021 10:52 AM, Kaz Kylheku wrote:
>>>>>>>>>>>>>>> I already acknowledged this. When an equivalent
>>>>>>>>>>>>>>> computation is run on a
>>>>>>>>>>>>>>> machine without resource limits (such as a TM) then this
>>>>>>>>>>>>>>> computation is
>>>>>>>>>>>>>>> infinitely recursive.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> That depends on what you mean by "equivalent". Since you
>>>>>>>>>>>>>> have tied the
>>>>>>>>>>>>>> validity your work to the x86 representation, a Turing
>>>>>>>>>>>>>> Machine version
>>>>>>>>>>>>>> of your program, to be equivalent, has to contain the x86
>>>>>>>>>>>>>> program, and
>>>>>>>>>>>>>> the simulator, faithfully reproducing the same resource
>>>>>>>>>>>>>> limitations.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> A RASP machine is known to be equivalent to a UTM.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Thus the RASP is to the RAM as the Universal Turing machine
>>>>>>>>>>>>> is to the
>>>>>>>>>>>>> Turing machine. The RASP is an example of the von Neumann
>>>>>>>>>>>>> architecture.
>>>>>>>>>>>>> https://en.wikipedia.org/wiki/Random-access_stored-program_machine
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> The x86 language is another exapmle of the von Neumann
>>>>>>>>>>>>> architecture.
>>>>>>>>>>>>> All computations implemented using the von Neumann
>>>>>>>>>>>>> architecture are
>>>>>>>>>>>>> equivalent to one another as long as they do not require
>>>>>>>>>>>>> more memory
>>>>>>>>>>>>> than is available.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Thus all computations implemented using the von Neumann
>>>>>>>>>>>>> architecture are
>>>>>>>>>>>>> equivalent UTM computations as long as they do not require
>>>>>>>>>>>>> more memory
>>>>>>>>>>>>> than is available.
>>>>>>>>>>>>
>>>>>>>>>>>> That is true; but an infinite recursion does require
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>> When I say that the x86 emulator: Simulate() is
>>>>>>>>>>>>>>> functionally equivalent
>>>>>>>>>>>>>>> to this code:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> int Simulate(u32 P, u32 I)
>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>> ((void(*)(int))P)(I);
>>>>>>>>>>>>>>> return 1;
>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> That is all that need be said about the capabilities of
>>>>>>>>>>>>>>> the x86 emulator.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Yes; then clearly, the H_Hat(P, P) call (with the right
>>>>>>>>>>>>>> casts put in)
>>>>>>>>>>>>>> denotes a runaway recursive call.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> So we agree on this point?
>>>>>>>>>>>>
>>>>>>>>>>>> Why wouldn't we? It's obviously a runaway recursive call.
>>>>>>>>>>>>
>>>>>>>>>>>>> When we know that Simulate() is an x86 emulator that is
>>>>>>>>>>>>> functionally
>>>>>>>>>>>>> equivalent to direct execution of its input then from the
>>>>>>>>>>>>> execution
>>>>>>>>>>>>> trace of the execution of this input (including the inputs
>>>>>>>>>>>>> to functions
>>>>>>>>>>>>> stored on the stack) alone we can decide that H_Hat() is
>>>>>>>>>>>>> infinitely
>>>>>>>>>>>>> recursive.
>>>>>>>>>>>>
>>>>>>>>>>>> Yes.
>>>>>>>>>>>>
>>>>>>>>>>>> In a static call graph of a program, we can spot loops.
>>>>>>>>>>>>
>>>>>>>>>>>> For instance a simple infinite loop occurs when a basic
>>>>>>>>>>>> block jumps to
>>>>>>>>>>>> itself.
>>>>>>>>>>>>
>>>>>>>>>>>> A basic block has no branching instructions anywhere, except
>>>>>>>>>>>> as possibly
>>>>>>>>>>>> the last instruction. If that last instruction is an
>>>>>>>>>>>> unconditional jump
>>>>>>>>>>>> back to that block, that is an infinite loop.
>>>>>>>>>>>>
>>>>>>>>>>>> Compilers do this kind of control flow analysis to find loops,
>>>>>>>>>>>> where certain optimizations can be concentrated (e.g. giving
>>>>>>>>>>>> more
>>>>>>>>>>>> registers to variables in nested loops).
>>>>>>>>>>>>
>>>>>>>>>>>> If we monitor the execution dynamically, we can likewise
>>>>>>>>>>>> identify
>>>>>>>>>>>> "dynamic basic blocks" sequences of unconditionally executed
>>>>>>>>>>>> instructions with no branches, and we can detect infinite
>>>>>>>>>>>> loops.
>>>>>>>>>>>> (Possibly ones that contain a stack push, if the jump is
>>>>>>>>>>>> actually
>>>>>>>>>>>> a subroutine call.)
>>>>>>>>>>>>
>>>>>>>>>>>> If we simply identify the situation, but don't interfere in
>>>>>>>>>>>> it, then the
>>>>>>>>>>>> situation persists: there is runaway recursion.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> When this same simulator monitors its own simulation it could
>>>>>>>>>>> figure out that the H_Hat() invocation of itself is
>>>>>>>>>>> infinitely recursive.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I'm afraid that's "wrong-headed" thinking, because Simulate
>>>>>>>>>> simply DOES NOT monitor its own simulation, so you can't talk
>>>>>>>>>> about when it does something IT DOESN'T DO. :) The same
>>>>>>>>>> mental confusion underlies your ".. /would/ fail to terminate
>>>>>>>>>> /if/ ABNHBD() didn't abort the emulation", and other
>>>>>>>>>> anthropomorphisms you make for TMs.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> So in other words you cannot possibly begin to imagine that a
>>>>>>>>> software function could be adapted to add functionality.
>>>>>>>>>
>>>>>>>>>> /We/ can figure out that the above H_Hat is infinitely
>>>>>>>>>> recursive, but /we/ are not Simulate, so H_Hat is not our
>>>>>>>>>> "We_hat", and this says nothing about the Linz proof.
>>>>>>>>>>
>>>>>>>>>> The /Simulate/ as you've described it (pure emulation)
>>>>>>>>>> /cannot/ "figure it out", because it fails to return and so
>>>>>>>>>> doesn't "figure" anything. Again, nothing much to say re HP
>>>>>>>>>> proof.
>>>>>>>>>>
>>>>>>>>>> We could code a /new/ emulator routine Simulate2 (distinct
>>>>>>>>>> from H_Hat and Simulate above) which has monitoring logic, and
>>>>>>>>>> use it to examine a simulation of the H_Hat above calling
>>>>>>>>>> Simulate(H_Hat) (note: NOT calling Simulate2...), and this
>>>>>>>>>> Simulate2 could correctly decide that H_Hat(H_Hat) does not
>>>>>>>>>> terminate.
>>>>>>>>>>
>>>>>>>>>> But H_Hat is not the "hatted" machine for Simulate2, so this
>>>>>>>>>> also is of little interest. Nobody claims that "no decider
>>>>>>>>>> can correctly decide halting for H_Hat", only that H does not
>>>>>>>>>> correctly decide halting for its own H_Hat.
>>>>>>>>>>
>>>>>>>>>> If we "update" H_Hat so that instead of calling Simulate, it
>>>>>>>>>> calls the new Simulate2, then we have a /new/ program H_Hat2,
>>>>>>>>>> and a /new/ calculation to consider. When H_Hat2 examines the
>>>>>>>>>> calculation H_Hat2(H_Hat2), with H_Hat2 calling Simulate2
>>>>>>>>>> etc., then H_Hat2 /*cannot*/ "figure out" that the calculation
>>>>>>>>>> has infinite recursion, BECAUSE IT DOESN'T. It can certainly
>>>>>>>>>> /decide/ that H_Hat2 is infinitely recursive, but that would
>>>>>>>>>> just be Simulate2 deciding incorrectly. All in line with Linz
>>>>>>>>>> proof.
>>>>>>>>>>
>>>>>>>>>> Remember, Simulate2 is not a "pure emulator" like Simulate, so
>>>>>>>>>> the fact that there may be two nested emulated calls to
>>>>>>>>>> Simulate2 with the same argument IS NOT PROOF OF INFINITE
>>>>>>>>>> RECURSION.
>>>>>>>>>
>>>>>>>>> When Simulate2() is identical to Simulate() in every way except
>>>>>>>>> that it also examines the execution trace of its input to
>>>>>>>>> figure out that its input is calling Simulate2() in infinite
>>>>>>>>> recursion then by logical necessity H_Hat() is still infinitely
>>>>>>>>> recursive.
>>>>>>>>
>>>>>>>> ?
>>>>>>>>
>>>>>>>> H_Hat doesn't call Simulate2. Maybe you mean H_Hat2 ?
>>>>>>>>
>>>>>>>> Obviously the /H_Hat/ calculation is "still" infinitely
>>>>>>>> recursive, because that calculation has never changed - by
>>>>>>>> definition it calls Simulate (not Simulate2).
>>>>>>>>
>>>>>>>> Hmm, your phrase "figuring out" isn't a standard CS term - I've
>>>>>>>> guessed it to mean that Simulate2 returns some different rc (not
>>>>>>>> 1) when it detects the nested calls to Simulate2 with the same
>>>>>>>> input data, thus making a different decision to the rc=1 [halts]
>>>>>>>> decision. Maybe you mean something else?
>>>>>>>>
>>>>>>>>
>>>>>>>> Mike.
>>>>>>>>
>>>>>> >
>>>>>>> An x86 emulator could keep track of all of the details of the
>>>>>>> execution trace of any input. If the original Simulate() was
>>>>>>> adapted to have this feature and the names remain the same then
>>>>>>> H_Hat() would invoke this updated version of Simulate() and still
>>>>>>> be infinitely recursive.
>>>>>>
>>>>>> So was my guess right? Does "figuring out" mean that Simulate2
>>>>>> returns some different rc (not 1) when it detects the nested calls
>>>>>> to Simulate2 with the same input data, thus making a different
>>>>>> decision to the rc=1 [halts] decision? All you've done is replace
>>>>>> "figuring out" with "keep track of" which is no better.
>>>>>>
>>>>>>>
>>>>>>> When software engineers add features to existing functions they
>>>>>>> do not change the names.
>>>>>>
>>>>>> What they do is change the versions. But you are not a software
>>>>>> engineer, so maybe you don't know about version numbers.
>>>>>>
>>>>>> Software engineers use version control systems so that if required
>>>>>> they can recreate the software at whatever point in the
>>>>>> development cycle is required, so there will not be confusion over
>>>>>> what code is being used/discussed at any time.
>>>>>>
>>>>>
>>>>> This is the version number of the whole system at that point in
>>>>> time. I worked on defense projects using version control. The
>>>>> function almost always keep their original names and merely acquire
>>>>> additional functionality.
>>>>>
>>>>>> In contrast, /you/ habitually use the same name for different
>>>>>> programs, and different names for the same programs. I suspect
>>>>>> this is because in part your arguments rely on confusing different
>>>>>> programs as being the same thing, in various ways. So it seems to
>>>>>> me that you do this deliberately. This is the exact opposite to
>>>>>> how a software engineer or professional programmer would behave.
>>>>>>
>>>>>
>>>>> There are only three programs that I will be talking about:
>>>>>
>>>>> // P has the machine address of H_Hat()
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Input_Halts = Simulate(P, P);
>>>>> if (Input_Halts)
>>>>> HERE: goto HERE;
>>>>> return;
>>>>> }
>>>>>
>>>>> That calls Simulate(P, P) and as the conversation progresses will
>>>>> gradually be adapted step-by-step until it becomes Halts(P, P).
>>>>>
>>>>> There will not be any version numbers for Simulate() because
>>>>> Simulate() is merely a conversational convention used to construct
>>>>> complete understanding of Halts() in small incremental steps.
>>>>>
>>>>>
>>>>>> If it is not deliberate, I suggest you just affix versions to the
>>>>>> end of your programs e.g. "H_Hat2" when they change. That's
>>>>>> easier than full versions, e.g. "H_Hat (V2.1.0.0)" and more
>>>>>> appropriate for newsgroup discussions.
>>>>>>
>>>>>>
>>>>>> Mike.
>>>>
>>>> int Simulate_1(u32 P, u32 I);
>>>> Emulates the x86 code pointed to by machine address P with data at
>>>> machine address I.
>>>>
>>>> int Simulate_2(u32 P, u32 I);
>>>> Same as Simulate_1() except keeps track of the execution trace of
>>>> its input including the data passed to any function invocations.
>>>
>>> What does "keeps track of" mean? Does Simulate_2 "do" anything with
>>> this tracked data, or is it just (in this version at least) ignored?
I provide every single detail of exactly what keeps track of means and
you simply ignore it.
It would have probably been easier if I separated out the "keeps track
of" portion so you could see this separately. I have done that now.
This is every single detail that the simulator / halt decider keeps
track of for the computation shown below.
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
(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
(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
(20)[00000868][00011140][0001114c](01) 55 push ebp
(21)[00000869][00011140][0001114c](02) 8bec mov ebp,esp
(22)[0000086b][00011140][0001114c](03) 8b4508 mov eax,[ebp+08]
(23)[0000086e][0001113c][00000868](01) 50 push eax
(24)[0000086f][0001113c][00000868](03) 8b4d08 mov ecx,[ebp+08]
(25)[00000872][00011138][00000868](01) 51 push ecx
(26)[00000873][00011134][00000878](05) e800fcffff call 00000478
The Simulator / Halt Decider only needs to keep track of the data shown
in the above table. It decodes the machine language and thus ignores the
assembly language. I show all of the details of how it analyzes this
data below.
Minimal criteria for deciding that H_Hat() calls Simulate() in infinite
recursion.
(1) The execution trace of H_Hat() shows that it calls Simulate() from
the same machine address two times in sequence with the same data.
(2) It is assumed that Simulate() either directly invokes its input (as
shown below) or Simulate() emulates the execution of the x86 machine
language of its input (functionally equivalent to the direct execution
shown below).
Does everyone agree that the above criteria is sufficient to definitely
decide that H_Hat() is infinitely recursive?
#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()
[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
(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 0x878
Line (11) pushes first parameter to Simulate() machine address 0x878
Line (12) Calls Simulate(0x878, 0x878);
(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 0x878
Line (18) pushes first parameter to Simulate() machine address 0x878
Line (19) Calls Simulate(0x878, 0x878);
(20)[00000868][00011140][0001114c](01) 55 push ebp
(21)[00000869][00011140][0001114c](02) 8bec mov ebp,esp
(22)[0000086b][00011140][0001114c](03) 8b4508 mov eax,[ebp+08]
(23)[0000086e][0001113c][00000868](01) 50 push eax
(24)[0000086f][0001113c][00000868](03) 8b4d08 mov ecx,[ebp+08]
(25)[00000872][00011138][00000868](01) 51 push ecx
(26)[00000873][00011134][00000878](05) e800fcffff call 00000478
Line (23) pushes second parameter to Simulate() machine address 0x878
Line (25) pushes first parameter to Simulate() machine address 0x878
Line (26) Calls Simulate(0x878, 0x878);
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.
--
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-03-02 09:29 -0600 |
| Subject | Re: Detecting infinite recursion (H_Hat is proved to be decidable) |
| Message-ID | <C7mdnRfu1PFXxKP9nZ2dnUU7-dXNnZ2d@giganews.com> |
| In reply to | #2596 |
On 3/2/2021 6:02 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> There are only three programs that I will be talking about:
>>
>> // P has the machine address of H_Hat()
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = Simulate(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> return;
>> }
>
> This is not a program. It's a function with hint in a comment as to
> what program you really mean. You should either write programs, or stop
> talking about them and talk about computations instead. I've
> illustrated both approaches below.
>
>> That calls Simulate(P, P) and as the conversation progresses will
>> gradually be adapted step-by-step until it becomes Halts(P, P).
>
> This looks like a good strategy, but you make so many errors of detail
> that you will be arguing about things that don't matter every step of
> the way. It's really tedious waiting to find out what the trick is you
> are trying to pull this time around.
>
> What you need, but don't have, is a function H such that this program:
>
> #include <stdint.h>
>
> int H(intptr_t P, intptr_t I)
> {
> // Unknown code
> }
>
> void H_Hat(intptr_t P) { if (H(P, P)) while (1); }
>
> int main(void) { return H((intptr_t)H_Hat, (intptr_t)H_Hat); }
>
> correctly returns 1 or 0 indicating the halting or non-halting of this
> program:
>
> #include <stdint.h>
>
> int H(intptr_t P, intptr_t I)
> {
> // Unknown code exactly as in the previous program
> }
>
> void H_Hat(intptr_t P) { if (H(P, P)) while (1); }
>
> int main(void) { H_Hat((intptr_t)H_Hat); }
>
> Alternatively, you can have one program reflecting the two key
> computations:
>
> #include <stdint.h>
> #include <stdio.h>
>
> int H(intptr_t P, intptr_t I)
> {
> // Unknown code
> }
>
> void H_Hat(intptr_t P) { if (H(P, P)) while (1); }
>
> int main(void) {
> printf("%d\n", H((intptr_t)H_Hat, (intptr_t)H_Hat));
> H_Hat((intptr_t)H_Hat);
> }
>
> This program should either print 1 and terminate, or print 0 and fail to
> terminate. To everyone but you, this program will make it cryatal clear
> why you can't succeed without trickery.
>
> You have some combination of shared data, nested levels of simulation,
> or maybe just your old redefined criterion for "correctly" reporting
> halting that makes it look, to you, like you have something interesting.
> How long must we wait to see what sort of trickery it is this time?
>
> Most of the time you have wasted since apparently having it all sort out
> years ago, has been taking up building the smoke machines and polishing
> the mirrors. You now have yards of code and mile of traces in which you
> have buried the trick. Your original claim, stripped of the lies about
> having actual Turing machines, was simple and impossible. You've lost
> that clarity. Deliberately so, I imagine.
>
>> There will not be any version numbers for Simulate() because
>> Simulate() is merely a conversational convention used to construct
>> complete understanding of Halts() in small incremental steps.
>
> You can find your mistake simply by finding the first of those steps
> where you move from something boring to something you'd like to boast
> about. That is the step at which you introduce the trick.
>
#include <stdint.h>
#define u8 uint8_t
#define u32 uint32_t
#define u16 uint16_t
u32 Halts(u32 P, u32 I)
{
((void(*)(int))P)(I);
return 1;
}
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);
}
Because the execution trace shown below shows that H_Hat() invokes
Halts() with the same data two times in sequence we can conclude that
H_Hat() is invoked in infinite recursion entirely based on the execution
trace of H_Hat() and the assumption that Halts() does nothing besides
execute or emulate its input.
When Halts() is augmented so that it can see that H_Hat() invokes it two
times in sequence with the same data then Halts() can determine that
H_Hat() is infinitely recursive.
_Halts()
[000004af](01) 55 push ebp
[000004b0](02) 8bec mov ebp,esp
[000004b2](03) 8b450c mov eax,[ebp+0c]
[000004b5](01) 50 push eax
[000004b6](03) ff5508 call dword [ebp+08]
[000004b9](03) 83c404 add esp,+04
[000004bc](05) b801000000 mov eax,00000001
[000004c1](01) 5d pop ebp
[000004c2](01) c3 ret
_H_Hat()
[0000088f](01) 55 push ebp
[00000890](02) 8bec mov ebp,esp
[00000892](01) 51 push ecx
[00000893](03) 8b4508 mov eax,[ebp+08]
[00000896](01) 50 push eax ; 2nd Param
[00000897](03) 8b4d08 mov ecx,[ebp+08]
[0000089a](01) 51 push ecx ; 1st Param
[0000089b](05) e80ffcffff call 000004af ; Halts(P,P)
[000008a0](03) 83c408 add esp,+08
[000008a3](03) 8945fc mov [ebp-04],eax
[000008a6](04) 837dfc00 cmp dword [ebp-04],+00
[000008aa](02) 7402 jz 000008ae
[000008ac](02) ebfe jmp 000008ac
[000008ae](02) 8be5 mov esp,ebp
[000008b0](01) 5d pop ebp
[000008b1](01) c3 ret
_main()
[000008bf](01) 55 push ebp
[000008c0](02) 8bec mov ebp,esp
[000008c2](01) 51 push ecx
[000008c3](05) 688f080000 push 0000088f
[000008c8](05) 688f080000 push 0000088f
[000008cd](05) e8ddfbffff call 000004af
[000008d2](03) 83c408 add esp,+08
[000008d5](03) 8945fc mov [ebp-04],eax
[000008d8](03) 8b45fc mov eax,[ebp-04]
[000008db](01) 50 push eax
[000008dc](05) 680b030000 push 0000030b
[000008e1](05) e869faffff call 0000034f
[000008e6](03) 83c408 add esp,+08
[000008e9](02) 33c0 xor eax,eax
[000008eb](02) 8be5 mov esp,ebp
[000008ed](01) 5d pop ebp
[000008ee](01) c3 ret
Push instructions have already pushed the value shown in their in the
third column. The two push instructions preceding the call to Simulate()
are its second and first parameters respectively.
Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text
...[000008bf][00011208][00000000](01) 55 push ebp
...[000008c0][00011208][00000000](02) 8bec mov ebp,esp
...[000008c2][00011204][00000000](01) 51 push ecx
...[000008c3][00011200][0000088f](05) 688f080000 push 0000088f
...[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f
...[000008cd][000111f8][000008d2](05) e8ddfbffff call 000004af
...[0000088f][000111e8][000111f4](01) 55 push ebp
...[00000890][000111e8][000111f4](02) 8bec mov ebp,esp
...[00000892][000111e4][00000000](01) 51 push ecx
...[00000893][000111e4][00000000](03) 8b4508 mov eax,[ebp+08]
...[00000896][000111e0][0000088f](01) 50 push eax ; 2nd Param
...[00000897][000111e0][0000088f](03) 8b4d08 mov ecx,[ebp+08]
...[0000089a][000111dc][0000088f](01) 51 push ecx ; 1st Param
Call Halts(0000088f, 0000088f);
...[0000089b][000111d8][000008a0](05) e80ffcffff call 000004af
...[0000088f][000111c8][000111d4](01) 55 push ebp
...[00000890][000111c8][000111d4](02) 8bec mov ebp,esp
...[00000892][000111c4][0000088f](01) 51 push ecx
...[00000893][000111c4][0000088f](03) 8b4508 mov eax,[ebp+08]
...[00000896][000111c0][0000088f](01) 50 push eax ; 2nd Param
...[00000897][000111c0][0000088f](03) 8b4d08 mov ecx,[ebp+08]
...[0000089a][000111bc][0000088f](01) 51 push ecx ;1st Param
Call Halts(0000088f, 0000088f);
...[0000089b][000111b8][000008a0](05) e80ffcffff call 000004af
It continues to execute the same portion of H_Hat() sequence above
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | om@iki.fi (Otto J. Makela) |
|---|---|
| Date | 2021-03-02 18:36 +0200 |
| Message-ID | <87czwhfr6s.fsf@tigger.extechop.net> |
| In reply to | #2586 |
I'm a bit late to the discussion, but this sounds a lot like you're trying to overturn Turing's proof that that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. -- /* * * Otto J. Makela <om@iki.fi> * * * * * * * * * */ /* Phone: +358 40 765 5772, ICBM: N 60 10' E 24 55' */ /* Mail: Mechelininkatu 26 B 27, FI-00100 Helsinki */ /* * * Computers Rule 01001111 01001011 * * * * * * */
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-02 11:22 -0600 |
| Message-ID | <uLSdnZF1Hv7L6aP9nZ2dnUU7-e3NnZ2d@giganews.com> |
| In reply to | #2600 |
On 3/2/2021 10:36 AM, Otto J. Makela wrote:
> I'm a bit late to the discussion, but this sounds a lot like you're
> trying to overturn Turing's proof that that a general algorithm to solve
> the halting problem for all possible program-input pairs cannot exist.
>
Yes. The key brand new insight that I had about this proof is that the
actual execution trace never reaches the undecidable portion, thus
making the conventional halting problem counter-examples {Linz, Sipser,
Kozen} decidable.
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
"It looks like the original specification provided in
the Linz text may be infinitely recursive in that each
TM requires its own input."
Self Modifying Turing Machine (SMTM) Solution to the Halting Problem
(concrete example) August 2016
https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example
Infinitely Recursive input on HP Proofs (March 11, 2017)
https://groups.google.com/g/comp.theory/c/NcFS02hKs1U/m/PlBF-1LRBAAJ
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company (315-320)
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
Kozen, Dexter 1997. Automata and Computability. New York:
Springer-Verlag. (231-234).
--
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-03-02 17:46 +0000 |
| Message-ID | <20210302093944.475@kylheku.com> |
| In reply to | #2601 |
On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>> I'm a bit late to the discussion, but this sounds a lot like you're
>> trying to overturn Turing's proof that that a general algorithm to solve
>> the halting problem for all possible program-input pairs cannot exist.
>>
>
> Yes. The key brand new insight that I had about this proof is that the
> actual execution trace never reaches the undecidable portion, thus
The program has no "undecidable portion". We know perfectly well
whether it terminates or not, because it is trivial.
All that is undecidable, in the context of computability, is the problem
of determining whether any program whatsoever on any input terminates.
"Undecidable
> making the conventional halting problem counter-examples {Linz, Sipser,
> Kozen} decidable.
Each such example is individually decidable, and everybody knows this.
No example of anything even moderately hard to decide is ever presented
in the proofs.
> // P has the machine address of H_Hat()
> void H_Hat(u32 P)
> {
> u32 Input_Halts = Halts(P, P);
> if (Input_Halts)
> HERE: goto HERE;
> return;
> }
Everyone, including probably most CS undergrads by the time they reach
senior year, that if Halts decides that it's a good idea to "decide"
halting by simply running the code, runaway recursion will occur.
When I first encountered the halting problem concept, I remember that
the text I was reading mentioned this: if the decision function jus
executes the function, it precipitates into infinite regress, and
therefore does not terminate, in which case there is no decision.
You have not discovered anything.
Also, the idea of an insruction stream that has no branches corresponds
to the well-known concept of a basic block in program control flow
analysis, used in compilers. Again, something even CS undergrads know by
the time they graduate.
--
TXR Programming Language: http://nongnu.org/txr
Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-02 13:00 -0600 |
| Message-ID | <ErKdnaAPipewFqP9nZ2dnUU7-YfNnZ2d@giganews.com> |
| In reply to | #2602 |
On 3/2/2021 11:46 AM, Kaz Kylheku wrote:
> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>>> I'm a bit late to the discussion, but this sounds a lot like you're
>>> trying to overturn Turing's proof that that a general algorithm to solve
>>> the halting problem for all possible program-input pairs cannot exist.
>>>
>>
>> Yes. The key brand new insight that I had about this proof is that the
>> actual execution trace never reaches the undecidable portion, thus
>
> The program has no "undecidable portion". We know perfectly well
> whether it terminates or not, because it is trivial.
>
Daryl McCullough
https://groups.google.com/g/comp.theory/c/wgJjJR78FaU/m/_eWPqsSS8bEJ
I can finally give credit where credit is due. Daryl McCullough was the
one that originally came up with this analogy in March of 2012.
When we ask Bill: Is your answer to this question "no" ?
Bill cannot possibly provide a correct answer because both answers of
"yes" and "no" form a contradiction.
In this same way Halts() cannot possibly provide a correct return value
indicating halting / non halting to H_Hat().
// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts2(P, P);
if (Input_Halts)
HERE: goto HERE;
return;
}
The brand new insight that I documented that I came up with in 2016 was
that a halt decider that examines the simulation of its input as the
basis for its halting decision would never reach the point where it
returns any value to H_Hat().
--
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-03-02 19:35 +0000 |
| Message-ID | <20210302111744.595@kylheku.com> |
| In reply to | #2603 |
["Followup-To:" header set to comp.lang.c.] On 2021-03-02, olcott <NoOne@NoWhere.com> wrote: > On 3/2/2021 11:46 AM, Kaz Kylheku wrote: >> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote: >>> On 3/2/2021 10:36 AM, Otto J. Makela wrote: >>>> I'm a bit late to the discussion, but this sounds a lot like you're >>>> trying to overturn Turing's proof that that a general algorithm to solve >>>> the halting problem for all possible program-input pairs cannot exist. >>>> >>> >>> Yes. The key brand new insight that I had about this proof is that the >>> actual execution trace never reaches the undecidable portion, thus >> >> The program has no "undecidable portion". We know perfectly well >> whether it terminates or not, because it is trivial. >> > > Daryl McCullough > https://groups.google.com/g/comp.theory/c/wgJjJR78FaU/m/_eWPqsSS8bEJ > I can finally give credit where credit is due. Daryl McCullough was the > one that originally came up with this analogy in March of 2012. > > When we ask Bill: Is your answer to this question "no" ? > Bill cannot possibly provide a correct answer because both answers of > "yes" and "no" form a contradiction. Since we are not part of the program, there is no contradiction in our answer when we decide whether the example terminates or not. If the example terminates and gives a result, that result may have the interpretation that it is wrong; i.e. a contradiction. If the program's is taken to mean "I do not halt", than that is wrong; That has no bearing on the fact that the program has halted, and that our own answer "it has halted" is right. The decider is only shown wrong on that one example, not that it's on all inputs. The decider is not absolutely contradicted. > The brand new insight that I documented that I came up with in 2016 was > that a halt decider that examines the simulation of its input as the > basis for its halting decision would never reach the point where it > returns any value to H_Hat(). This is undergrad-level obvious that if the decider, instead of implementing some actual decision algorithm, simply executes the input, then if that input does not terminate, that "decision" will also not terminate, and that it is victim to infinite regress. The first time I learned about the halting problem, it was in a textbook which noted this obvious fact. You should be more humble in your claims that you have some brand new result. -- TXR Programming Language: http://nongnu.org/txr Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-03-02 13:50 -0600 |
| Message-ID | <POednXfS7IB4C6P9nZ2dnUU78IfNnZ2d@giganews.com> |
| In reply to | #2603 |
On 3/2/2021 1:00 PM, olcott wrote:
> On 3/2/2021 11:46 AM, Kaz Kylheku wrote:
>> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>>> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>>>> I'm a bit late to the discussion, but this sounds a lot like you're
>>>> trying to overturn Turing's proof that that a general algorithm to
>>>> solve
>>>> the halting problem for all possible program-input pairs cannot exist.
>>>>
>>>
>>> Yes. The key brand new insight that I had about this proof is that the
>>> actual execution trace never reaches the undecidable portion, thus
>>
>> The program has no "undecidable portion". We know perfectly well
>> whether it terminates or not, because it is trivial.
>>
There is a much earlier attribution to the same person:
sci.logic Daryl McCullough June 25, 2004
On Friday, June 25, 2004 at 6:30:39 PM UTC-5, Daryl McCullough wrote:
> You ask someone (we'll call him "Jack") to give a truthful
> yes/no answer to the following question:
> Will Jack's answer to this question be no?
> Jack can't possibly give a correct yes/no answer to the question.
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
Jack cannot possibly provide a correct answer because both answers of
"yes" and "no" form a contradiction.
> In this same way Halts() cannot possibly provide a correct return value
> indicating halting / non halting to H_Hat().
>
> // P has the machine address of H_Hat()
> void H_Hat(u32 P)
> {
> u32 Input_Halts = Halts2(P, P);
> if (Input_Halts)
> HERE: goto HERE;
> return;
> }
>
> The brand new insight that I documented that I came up with in 2016 was
> that a halt decider that examines the simulation of its input as the
> basis for its halting decision would never reach the point where it
> returns any value to H_Hat().
>
>
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | comp.software-eng
csiph-web