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


Groups > comp.software-eng > #2586 > unrolled thread

Detecting infinite recursion

Started byolcott <NoOne@NoWhere.com>
First post2021-02-26 13:53 -0600
Last post2021-03-09 19:42 -0600
Articles 20 on this page of 38 — 10 participants

Back to article view | Back to comp.software-eng


Contents

  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 →


#2586 — Detecting infinite recursion

Fromolcott <NoOne@NoWhere.com>
Date2021-02-26 13:53 -0600
SubjectDetecting 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]


#2587

FromSiri Cruise <chine.bleu@yahoo.com>
Date2021-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]


#2588

FromMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
Date2021-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]


#2589

FromSiri Cruise <chine.bleu@yahoo.com>
Date2021-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]


#2590

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-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]


#2591

FromJeff Barnett <jbb@notatt.com>
Date2021-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]


#2592

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#2593

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#2594

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#2595 — Re: Detecting infinite recursion (H_Hat is proved to be decidable)

Fromolcott <NoOne@NoWhere.com>
Date2021-02-28 13:08 -0600
SubjectRe: 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]


#2596 — Re: Detecting infinite recursion (H_Hat is proved to be decidable)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-03-01 03:52 +0000
SubjectRe: 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]


#2598 — Re: Detecting infinite recursion (H_Hat is proved to be decidable)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-01 21:32 -0600
SubjectRe: 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]


#2619 — Re: Detecting infinite recursion (H_Hat is proved to be decidable)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-03 15:37 -0600
SubjectRe: 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]


#2599 — Re: Detecting infinite recursion (H_Hat is proved to be decidable)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 09:29 -0600
SubjectRe: 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]


#2600

Fromom@iki.fi (Otto J. Makela)
Date2021-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]


#2601

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#2602

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-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]


#2603

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#2604

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-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]


#2605

Fromolcott <NoOne@NoWhere.com>
Date2021-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