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


Groups > comp.theory > #39507 > unrolled thread

Must a partial halt decider be a pure function of its inputs?

Started byolcott <NoOne@NoWhere.com>
First post2021-09-18 22:42 -0500
Last post2021-09-20 19:35 -0400
Articles 20 on this page of 62 — 8 participants

Back to article view | Back to comp.theory


Contents

  Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-18 22:42 -0500
    Re: Must a partial halt decider be a pure function of its inputs? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-19 02:30 -0700
      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-19 06:09 -0500
        Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-19 08:15 -0400
          Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ] olcott <NoOne@NoWhere.com> - 2021-09-19 10:03 -0500
            Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ] Richard Damon <Richard@Damon-Family.org> - 2021-09-19 13:47 -0400
            Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-19 23:42 +0100
    Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-19 06:39 -0400
      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-19 06:25 -0500
        Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-19 08:12 -0400
          Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-19 09:48 -0500
            Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-19 13:58 -0400
    Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 11:20 -0500
      Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 19:05 +0100
        Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 13:16 -0500
          Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 19:29 +0100
            Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 13:40 -0500
              Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 19:44 +0100
                Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 14:04 -0500
                  Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 20:13 +0100
                    Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 14:27 -0500
                      Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 20:29 +0100
                        Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 15:08 -0500
                          Re: Must a partial halt decider be a pure function of its inputs? (addendum) Mr Flibble <flibble@reddwarf.jmc> - 2021-09-19 21:32 +0100
                  Re: Must a partial halt decider be a pure function of its inputs? (addendum) Richard Damon <Richard@Damon-Family.org> - 2021-09-19 19:16 -0400
      Re: Must a partial halt decider be a pure function of its inputs? (addendum) Richard Damon <Richard@Damon-Family.org> - 2021-09-19 14:05 -0400
        Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 13:21 -0500
          Re: Must a partial halt decider be a pure function of its inputs? (addendum) Richard Damon <news.x.richarddamon@xoxy.net> - 2021-09-19 14:51 -0400
            Re: Must a partial halt decider be a pure function of its inputs? (addendum) olcott <NoOne@NoWhere.com> - 2021-09-19 14:14 -0500
              Re: Must a partial halt decider be a pure function of its inputs? (addendum) André G. Isaak <agisaak@gm.invalid> - 2021-09-19 13:41 -0600
    Re: Must a partial halt decider be a pure function of its inputs? Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 09:15 -0700
      Re: Must a partial halt decider be a pure function of its inputs? Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 09:34 -0700
        Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 11:46 -0500
      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 11:44 -0500
        Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 11:17 -0600
          Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 12:42 -0500
            Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 11:59 -0600
              Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 13:59 -0500
                Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 14:01 -0600
                  Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 15:46 -0500
                    Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 15:07 -0600
                      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 16:52 -0500
                        Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 16:06 -0600
                          Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 17:29 -0500
                            Re: Must a partial halt decider be a pure function of its inputs? André G. Isaak <agisaak@gm.invalid> - 2021-09-20 16:52 -0600
                              Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 18:17 -0500
            Re: Must a partial halt decider be a pure function of its inputs? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-20 23:06 +0100
              Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 17:37 -0500
                Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-20 19:31 -0400
                  Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 18:48 -0500
                    Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-20 22:38 -0400
                      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 21:45 -0500
                        Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-20 23:27 -0400
                        Re: Must a partial halt decider be a pure function of its inputs? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-20 23:14 -0700
                          Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-21 09:39 -0500
                            Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-21 19:16 -0400
                Re: Must a partial halt decider be a pure function of its inputs? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-21 01:45 +0100
                  Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 19:53 -0500
                    Re: Must a partial halt decider be a pure function of its inputs? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-21 02:39 +0100
                      Re: Must a partial halt decider be a pure function of its inputs? olcott <NoOne@NoWhere.com> - 2021-09-20 20:44 -0500
                        Re: Must a partial halt decider be a pure function of its inputs? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-21 03:33 +0100
            Re: Must a partial halt decider be a pure function of its inputs? Richard Damon <Richard@Damon-Family.org> - 2021-09-20 19:35 -0400

Page 1 of 4  [1] 2 3 4  Next page →


#39507 — Must a partial halt decider be a pure function of its inputs?

Fromolcott <NoOne@NoWhere.com>
Date2021-09-18 22:42 -0500
SubjectMust a partial halt decider be a pure function of its inputs?
Message-ID<O9-dnbixA9Y0LNv8nZ2dnUU7-VvNnZ2d@giganews.com>
This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal 
parameters to a function and a single output such as return value of 
{1,0} (indicating true or false) from this function, then whatever 
occurs in-between does not make any difference.

This would mean that my use of static local variables has no detrimental 
effect on the applicability of my partial halt decider to the halting 
problem.

u32 H(u32 P, u32 I)
{
   static u32 Aborted;
   static u32* execution_trace;



-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]


#39512

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2021-09-19 02:30 -0700
Message-ID<0e051f10-a810-4a4b-a865-c9130b12e8edn@googlegroups.com>
In reply to#39507
On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
> This is my paraphrase of the requirement a partial 
> halt decider must be a pure function of its inputs: 
> 
> As long as there is one set of inputs such as such as the formal 
> parameters to a function and a single output such as return value of 
> {1,0} (indicating true or false) from this function, then whatever 
> occurs in-between does not make any difference. 
> 
> This would mean that my use of static local variables has no detrimental 
> effect on the applicability of my partial halt decider to the halting 
> problem. 
> 
> u32 H(u32 P, u32 I) 
> { 
> static u32 Aborted; 
> static u32* execution_trace; 
> 
To qualify as a decider, the halt decider must calculate a (mathematical) function.
That is, for each possible input, there must be one and only one output, that
is always the same for each input.

How a piece of computer code achieves that is not important, and details vary
from language to language. In some primitive languages (or high-level scripting 
languages) it may not be possible to declare local variables, for instance. 

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


#39516

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 06:09 -0500
Message-ID<A_ydnUPNnJYah9r8nZ2dnUU7-UXNnZ2d@giganews.com>
In reply to#39512
On 9/19/2021 4:30 AM, Malcolm McLean wrote:
> On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
>> This is my paraphrase of the requirement a partial
>> halt decider must be a pure function of its inputs:
>>
>> As long as there is one set of inputs such as such as the formal
>> parameters to a function and a single output such as return value of
>> {1,0} (indicating true or false) from this function, then whatever
>> occurs in-between does not make any difference.
>>
>> This would mean that my use of static local variables has no detrimental
>> effect on the applicability of my partial halt decider to the halting
>> problem.
>>
>> u32 H(u32 P, u32 I)
>> {
>> static u32 Aborted;
>> static u32* execution_trace;
>>
> To qualify as a decider, the halt decider must calculate a (mathematical) function.
> That is, for each possible input, there must be one and only one output, that
> is always the same for each input.
> 
> How a piece of computer code achieves that is not important, and details vary
> from language to language. In some primitive languages (or high-level scripting
> languages) it may not be possible to declare local variables, for instance.
> 

That is great. If this truly is the case then this completes the essence 
of my system.

This enables a decidability decider that refutes Rice's theorem:

u32 PSR_Olcott_2004(u32 P)
{
   return H1(P,P) != H(P,P);
}

int main()
{
   Output("Pathological Self-Reference(Olcott 2004) = ",
           PSR_Olcott_2004((u32) P));
}

-- 
Copyright 2021 Pete Olcott

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

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


#39520

FromRichard Damon <Richard@Damon-Family.org>
Date2021-09-19 08:15 -0400
Message-ID<KRF1J.110582$lC6.92289@fx41.iad>
In reply to#39516
On 9/19/21 7:09 AM, olcott wrote:
> On 9/19/2021 4:30 AM, Malcolm McLean wrote:
>> On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
>>> This is my paraphrase of the requirement a partial
>>> halt decider must be a pure function of its inputs:
>>>
>>> As long as there is one set of inputs such as such as the formal
>>> parameters to a function and a single output such as return value of
>>> {1,0} (indicating true or false) from this function, then whatever
>>> occurs in-between does not make any difference.
>>>
>>> This would mean that my use of static local variables has no detrimental
>>> effect on the applicability of my partial halt decider to the halting
>>> problem.
>>>
>>> u32 H(u32 P, u32 I)
>>> {
>>> static u32 Aborted;
>>> static u32* execution_trace;
>>>
>> To qualify as a decider, the halt decider must calculate a
>> (mathematical) function.
>> That is, for each possible input, there must be one and only one
>> output, that
>> is always the same for each input.
>>
>> How a piece of computer code achieves that is not important, and
>> details vary
>> from language to language. In some primitive languages (or high-level
>> scripting
>> languages) it may not be possible to declare local variables, for
>> instance.
>>
> 
> That is great. If this truly is the case then this completes the essence
> of my system.
> 
> This enables a decidability decider that refutes Rice's theorem:
> 
> u32 PSR_Olcott_2004(u32 P)
> {
>   return H1(P,P) != H(P,P);
> }
> 
> int main()
> {
>   Output("Pathological Self-Reference(Olcott 2004) = ",
>           PSR_Olcott_2004((u32) P));
> }
> 

And what is the Semantic Property of P that this is deciding?


What about my counter example of P = H2_Hat, which this seems to say
isn't Pathological but is the exact same 'code' (to use your term) as
H_Hat (Which you have called P) and H1_Hat?

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


#39524 — Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 10:03 -0500
SubjectRe: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]
Message-ID<p_mdncahKOr8zNr8nZ2dnUU7-RvNnZ2d@giganews.com>
In reply to#39520
On 9/19/2021 7:15 AM, Richard Damon wrote:
> On 9/19/21 7:09 AM, olcott wrote:
>> On 9/19/2021 4:30 AM, Malcolm McLean wrote:
>>> On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
>>>> This is my paraphrase of the requirement a partial
>>>> halt decider must be a pure function of its inputs:
>>>>
>>>> As long as there is one set of inputs such as such as the formal
>>>> parameters to a function and a single output such as return value of
>>>> {1,0} (indicating true or false) from this function, then whatever
>>>> occurs in-between does not make any difference.
>>>>
>>>> This would mean that my use of static local variables has no detrimental
>>>> effect on the applicability of my partial halt decider to the halting
>>>> problem.
>>>>
>>>> u32 H(u32 P, u32 I)
>>>> {
>>>> static u32 Aborted;
>>>> static u32* execution_trace;
>>>>
>>> To qualify as a decider, the halt decider must calculate a
>>> (mathematical) function.
>>> That is, for each possible input, there must be one and only one
>>> output, that
>>> is always the same for each input.
>>>
>>> How a piece of computer code achieves that is not important, and
>>> details vary
>>> from language to language. In some primitive languages (or high-level
>>> scripting
>>> languages) it may not be possible to declare local variables, for
>>> instance.
>>>
>>
>> That is great. If this truly is the case then this completes the essence
>> of my system.
>>
>> This enables a decidability decider that refutes Rice's theorem:
>>
>> u32 PSR_Olcott_2004(u32 P)
>> {
>>    return H1(P,P) != H(P,P);
>> }
>>
>> int main()
>> {
>>    Output("Pathological Self-Reference(Olcott 2004) = ",
>>            PSR_Olcott_2004((u32) P));
>> }
>>
> 
> And what is the Semantic Property of P that this is deciding?
> 

As  André aptly reminded me (that I said before)

On 9/9/2021 10:25 AM, olcott wrote:
 > It is the case that this inconsistency
 > defines a decidability decider that correctly
 > rejects P on the basis that P has the
 > pathological self-reference(Olcott 2004) error.

u32 PSR_Olcott_2004(u32 P) is a decidability decider.

> 
> What about my counter example of P = H2_Hat, which this seems to say
> isn't Pathological but is the exact same 'code' (to use your term) as
> H_Hat (Which you have called P) and H1_Hat?
> 

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

u32 PSR_Olcott_2004(u32 P)
{
   return H1(P,P) != H(P,P);
}

H1(P,P) correctly decides that its input halts because H1(P,P) does not 
have the pathological self-reference error (Olcott 2004)
Whereas H(P,P) does have this error.

int main()
{
   Output("Input_Halts = ", H1((u32)P, (u32)P));
}

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ halts, and

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt

H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly transitions to H.qy
Because H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does not have the pathological 
self-reference error (Olcott 2004)

Whereas Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does have this error.

H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
is a decidability decider rejecting ⟨Ĥ⟩ ⟨Ĥ⟩ as undecidable for Ĥ.qx

-- 
Copyright 2021 Pete Olcott

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

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


#39535 — Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-09-19 13:47 -0400
SubjectRe: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]
Message-ID<5JK1J.169845$T_8.91887@fx48.iad>
In reply to#39524
On 9/19/21 11:03 AM, olcott wrote:
> On 9/19/2021 7:15 AM, Richard Damon wrote:
>> On 9/19/21 7:09 AM, olcott wrote:
>>> On 9/19/2021 4:30 AM, Malcolm McLean wrote:
>>>> On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:
>>>>> This is my paraphrase of the requirement a partial
>>>>> halt decider must be a pure function of its inputs:
>>>>>
>>>>> As long as there is one set of inputs such as such as the formal
>>>>> parameters to a function and a single output such as return value of
>>>>> {1,0} (indicating true or false) from this function, then whatever
>>>>> occurs in-between does not make any difference.
>>>>>
>>>>> This would mean that my use of static local variables has no
>>>>> detrimental
>>>>> effect on the applicability of my partial halt decider to the halting
>>>>> problem.
>>>>>
>>>>> u32 H(u32 P, u32 I)
>>>>> {
>>>>> static u32 Aborted;
>>>>> static u32* execution_trace;
>>>>>
>>>> To qualify as a decider, the halt decider must calculate a
>>>> (mathematical) function.
>>>> That is, for each possible input, there must be one and only one
>>>> output, that
>>>> is always the same for each input.
>>>>
>>>> How a piece of computer code achieves that is not important, and
>>>> details vary
>>>> from language to language. In some primitive languages (or high-level
>>>> scripting
>>>> languages) it may not be possible to declare local variables, for
>>>> instance.
>>>>
>>>
>>> That is great. If this truly is the case then this completes the essence
>>> of my system.
>>>
>>> This enables a decidability decider that refutes Rice's theorem:
>>>
>>> u32 PSR_Olcott_2004(u32 P)
>>> {
>>>    return H1(P,P) != H(P,P);
>>> }
>>>
>>> int main()
>>> {
>>>    Output("Pathological Self-Reference(Olcott 2004) = ",
>>>            PSR_Olcott_2004((u32) P));
>>> }
>>>
>>
>> And what is the Semantic Property of P that this is deciding?
>>
> 
> As  André aptly reminded me (that I said before)
> 
> On 9/9/2021 10:25 AM, olcott wrote:
>> It is the case that this inconsistency
>> defines a decidability decider that correctly
>> rejects P on the basis that P has the
>> pathological self-reference(Olcott 2004) error.
> 
> u32 PSR_Olcott_2004(u32 P) is a decidability decider.

Please DEFINE what you mean by a decidability decider.

Every machine that has an accept state and a reject state as its output
is a possible decider. It IS a decider if it will halt in one of those
two states for ALL inputs. It might not answer the question you WANT,
but it has decided.

> 
>>
>> What about my counter example of P = H2_Hat, which this seems to say
>> isn't Pathological but is the exact same 'code' (to use your term) as
>> H_Hat (Which you have called P) and H1_Hat?
>>
> 
> void P(u32 x)
> {
>   if (H(x, x))
>     HERE: goto HERE;
> }
> 
> u32 PSR_Olcott_2004(u32 P)
> {
>   return H1(P,P) != H(P,P);
> }
> 
> H1(P,P) correctly decides that its input halts because H1(P,P) does not
> have the pathological self-reference error (Olcott 2004)
> Whereas H(P,P) does have this error.
> 
> int main()
> {
>   Output("Input_Halts = ", H1((u32)P, (u32)P));
> }
> 
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
> if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ halts, and
> 
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt
> 
> H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly transitions to H.qy
> Because H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does not have the pathological
> self-reference error (Olcott 2004)
> 
> Whereas Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does have this error.
> 
> H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
> is a decidability decider rejecting ⟨Ĥ⟩ ⟨Ĥ⟩ as undecidable for Ĥ.qx
> 

And what does that have to do with my H2_Hat?

I will call the dishonest dodge here.

H2_Hat built by the same formula as P but from H2.

H2(H2_Hat, H2_Hat) will run into this 'Pathological' case, but

PSR_Olcott_2004(H2_Hat, H2_Hat) will say it does not have the Olcott
Pathological Self Reference issue.

Ergo, something is wrong.

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


#39577 — Re: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-19 23:42 +0100
SubjectRe: Must a partial halt decider be a pure function of its inputs? [ decidability decider ]
Message-ID<87czp489wi.fsf@bsb.me.uk>
In reply to#39524
olcott <NoOne@NoWhere.com> writes:

> H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly transitions to H.qy

Yesterday you said I was fibbing to say such a thing, and you said:

  "I have repeated H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ transitions to H.qn many times"

Up until now, only one of H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy and Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
could be right, but now you've gone completely off the rails because
only one of H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy and H.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn can be right.
Which one is the lie?

You've lost the plot.

(I've just a had great fun weekend at a dog training instructors'
course.  Not a Turing machine in sight.  Please go and do something that
brings joy to your life to the lives of others.  This can't be fun for
you.)

-- 
Ben.

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


#39515

FromRichard Damon <Richard@Damon-Family.org>
Date2021-09-19 06:39 -0400
Message-ID<0sE1J.50360$tG6.13803@fx39.iad>
In reply to#39507
On 9/18/21 11:42 PM, olcott wrote:
> This is my paraphrase of the requirement a partial
> halt decider must be a pure function of its inputs:
> 
> As long as there is one set of inputs such as such as the formal
> parameters to a function and a single output such as return value of
> {1,0} (indicating true or false) from this function, then whatever
> occurs in-between does not make any difference.
> 
> This would mean that my use of static local variables has no detrimental
> effect on the applicability of my partial halt decider to the halting
> problem.
> 
> u32 H(u32 P, u32 I)
> {
>   static u32 Aborted;
>   static u32* execution_trace;
>

As I have said, the key part that you seem to miss is that the
requirement of being a Computation means that the H that is part of H^
(you call P) must return the same answer as the H that is deciding
H(H^,H^) even though that embedded machine might be a 'slave' decider.

Thus any logic that tries to 'prove' what would happen in the simulated
machine past the point the simulation is stopped must be consistent with
the behavior of the simulating Halt Decider.

This breaks your 'doesn't not affect the behavior before' logic, because
what the decider does after aborting the simulation does sort of have an
affect on the machine being simulated because it has a copy of the exact
same computation and thus will behave the same.

It isn't that the simulator 'causes' the behavior, but that is shown to
be what is built into the algorithm (so we can't argue 'causality' as
all is caused by the design which did happen before).

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


#39517

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 06:25 -0500
Message-ID<8s2dnbwCN4--g9r8nZ2dnUU7-X3NnZ2d@giganews.com>
In reply to#39515
On 9/19/2021 5:39 AM, Richard Damon wrote:
> On 9/18/21 11:42 PM, olcott wrote:
>> This is my paraphrase of the requirement a partial
>> halt decider must be a pure function of its inputs:
>>
>> As long as there is one set of inputs such as such as the formal
>> parameters to a function and a single output such as return value of
>> {1,0} (indicating true or false) from this function, then whatever
>> occurs in-between does not make any difference.
>>
>> This would mean that my use of static local variables has no detrimental
>> effect on the applicability of my partial halt decider to the halting
>> problem.
>>
>> u32 H(u32 P, u32 I)
>> {
>>    static u32 Aborted;
>>    static u32* execution_trace;
>>
> 
> As I have said, the key part that you seem to miss is that the
> requirement of being a Computation means that the H that is part of H^
> (you call P) must return the same answer as the H that is deciding
> H(H^,H^) even though that embedded machine might be a 'slave' decider.
> 

The actual computation is merely the first invocation and the final 
output. The simulated function calls are not actual function calls, 
merely an aspect of the larger computation.

As long as every unique input always maps to the same output then we are 
good.

> Thus any logic that tries to 'prove' what would happen in the simulated
> machine past the point the simulation is stopped must be consistent with
> the behavior of the simulating Halt Decider.
>

Yes. After the halt decider has made its decision it need not examine 
any code.

> This breaks your 'doesn't not affect the behavior before' logic, because

It is moot at this is point.

> what the decider does after aborting the simulation does sort of have an
> affect on the machine being simulated because it has a copy of the exact
> same computation and thus will behave the same.
> 

None-the-less the actual halt status decision is unbiased by the 
behavior of the halt decider.

> It isn't that the simulator 'causes' the behavior, but that is shown to
> be what is built into the algorithm (so we can't argue 'causality' as
> all is caused by the design which did happen before).
> 


-- 
Copyright 2021 Pete Olcott

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

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


#39519

FromRichard Damon <Richard@Damon-Family.org>
Date2021-09-19 08:12 -0400
Message-ID<UOF1J.89170$rl3.21905@fx45.iad>
In reply to#39517
On 9/19/21 7:25 AM, olcott wrote:
> On 9/19/2021 5:39 AM, Richard Damon wrote:
>> On 9/18/21 11:42 PM, olcott wrote:
>>> This is my paraphrase of the requirement a partial
>>> halt decider must be a pure function of its inputs:
>>>
>>> As long as there is one set of inputs such as such as the formal
>>> parameters to a function and a single output such as return value of
>>> {1,0} (indicating true or false) from this function, then whatever
>>> occurs in-between does not make any difference.
>>>
>>> This would mean that my use of static local variables has no detrimental
>>> effect on the applicability of my partial halt decider to the halting
>>> problem.
>>>
>>> u32 H(u32 P, u32 I)
>>> {
>>>    static u32 Aborted;
>>>    static u32* execution_trace;
>>>
>>
>> As I have said, the key part that you seem to miss is that the
>> requirement of being a Computation means that the H that is part of H^
>> (you call P) must return the same answer as the H that is deciding
>> H(H^,H^) even though that embedded machine might be a 'slave' decider.
>>
> 
> The actual computation is merely the first invocation and the final
> output. The simulated function calls are not actual function calls,
> merely an aspect of the larger computation.

No, but they ARE supposed to be accurate recreation of a machine that IS
a computation on their own.

> 
> As long as every unique input always maps to the same output then we are
> good.

EVERY TIME. That means if H(H^,H^) is return non-halting in one place,
it is so in ALL places, including embedded copies.

> 
>> Thus any logic that tries to 'prove' what would happen in the simulated
>> machine past the point the simulation is stopped must be consistent with
>> the behavior of the simulating Halt Decider.
>>
> 
> Yes. After the halt decider has made its decision it need not examine
> any code.

But it does need to take account of what WILL happen in the machines it
was simulating after it stops.

> 
>> This breaks your 'doesn't not affect the behavior before' logic, because
> 
> It is moot at this is point.

So, you aren't going to make that argument to claim that H can ignore
what the embedded copy of H will do?

> 
>> what the decider does after aborting the simulation does sort of have an
>> affect on the machine being simulated because it has a copy of the exact
>> same computation and thus will behave the same.
>>
> 
> None-the-less the actual halt status decision is unbiased by the
> behavior of the halt decider.

Only in the sense that the behavior of the simulator instance doesn't
affect that actual behavior of the simulated machine instance, but the
behavior of the copy of the simulator in the simulated program will
affect the behavior of the simulated program.

Thus, H can't ignore the affect of copies of it, as they WILL affect the
behavior of the simulated machine, and copy the behavior of the simulator.
> 
>> It isn't that the simulator 'causes' the behavior, but that is shown to
>> be what is built into the algorithm (so we can't argue 'causality' as
>> all is caused by the design which did happen before).
>>
> 
> 

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


#39523

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 09:48 -0500
Message-ID<OoidnT6PlZMx0Nr8nZ2dnUU7-efNnZ2d@giganews.com>
In reply to#39519
On 9/19/2021 7:12 AM, Richard Damon wrote:
> On 9/19/21 7:25 AM, olcott wrote:
>> On 9/19/2021 5:39 AM, Richard Damon wrote:
>>> On 9/18/21 11:42 PM, olcott wrote:
>>>> This is my paraphrase of the requirement a partial
>>>> halt decider must be a pure function of its inputs:
>>>>
>>>> As long as there is one set of inputs such as such as the formal
>>>> parameters to a function and a single output such as return value of
>>>> {1,0} (indicating true or false) from this function, then whatever
>>>> occurs in-between does not make any difference.
>>>>
>>>> This would mean that my use of static local variables has no detrimental
>>>> effect on the applicability of my partial halt decider to the halting
>>>> problem.
>>>>
>>>> u32 H(u32 P, u32 I)
>>>> {
>>>>     static u32 Aborted;
>>>>     static u32* execution_trace;
>>>>
>>>
>>> As I have said, the key part that you seem to miss is that the
>>> requirement of being a Computation means that the H that is part of H^
>>> (you call P) must return the same answer as the H that is deciding
>>> H(H^,H^) even though that embedded machine might be a 'slave' decider.
>>>
>>
>> The actual computation is merely the first invocation and the final
>> output. The simulated function calls are not actual function calls,
>> merely an aspect of the larger computation.
> 
> No, but they ARE supposed to be accurate recreation of a machine that IS
> a computation on their own.
> 
>>
>> As long as every unique input always maps to the same output then we are
>> good.
> 
> EVERY TIME. That means if H(H^,H^) is return non-halting in one place,
> it is so in ALL places, including embedded copies.
> 
>>
>>> Thus any logic that tries to 'prove' what would happen in the simulated
>>> machine past the point the simulation is stopped must be consistent with
>>> the behavior of the simulating Halt Decider.
>>>
>>
>> Yes. After the halt decider has made its decision it need not examine
>> any code.
> 
> But it does need to take account of what WILL happen in the machines it
> was simulating after it stops.
> 
>>
>>> This breaks your 'doesn't not affect the behavior before' logic, because
>>
>> It is moot at this is point.
> 
> So, you aren't going to make that argument to claim that H can ignore
> what the embedded copy of H will do?
> 
>>
>>> what the decider does after aborting the simulation does sort of have an
>>> affect on the machine being simulated because it has a copy of the exact
>>> same computation and thus will behave the same.
>>>
>>
>> None-the-less the actual halt status decision is unbiased by the
>> behavior of the halt decider.
> 
> Only in the sense that the behavior of the simulator instance doesn't
> affect that actual behavior of the simulated machine instance, but the
> behavior of the copy of the simulator in the simulated program will
> affect the behavior of the simulated program.
> 
> Thus, H can't ignore the affect of copies of it, as they WILL affect the
> behavior of the simulated machine, and copy the behavior of the simulator.
>>
>>> It isn't that the simulator 'causes' the behavior, but that is shown to
>>> be what is built into the algorithm (so we can't argue 'causality' as
>>> all is caused by the design which did happen before).
>>>
>>
>>
> 


The return value of the execution of H(P,P) is a pure function
of the input to H(P,P). As long as the execution of H(P,P) always
derives the same return value of 0 then H(P,P) is a pure function
of its input no matter what occurs inbetween.

Only this part matters to a [pure function of its inputs]
The function return values are identical for identical arguments (no 
variation with local static variables, non-local variables, mutable 
reference arguments or input streams).
https://en.wikipedia.org/wiki/Pure_function

It doesn't say that local static variables, non-local variables, mutable 
reference arguments cannot be used, merely that their use cannot ever 
cause the same input to derive a different output.

All of the simulation between the execution of H(P,P) and the return 
value from H(P,P) is an aspect of the internal computation of H(P,P) and 
is derived on the basis of the input to H(P,P).

-- 
Copyright 2021 Pete Olcott

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

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


#39537

FromRichard Damon <Richard@Damon-Family.org>
Date2021-09-19 13:58 -0400
Message-ID<VSK1J.133838$o45.62789@fx46.iad>
In reply to#39523
On 9/19/21 10:48 AM, olcott wrote:
> On 9/19/2021 7:12 AM, Richard Damon wrote:
>> On 9/19/21 7:25 AM, olcott wrote:
>>> On 9/19/2021 5:39 AM, Richard Damon wrote:
>>>> On 9/18/21 11:42 PM, olcott wrote:
>>>>> This is my paraphrase of the requirement a partial
>>>>> halt decider must be a pure function of its inputs:
>>>>>
>>>>> As long as there is one set of inputs such as such as the formal
>>>>> parameters to a function and a single output such as return value of
>>>>> {1,0} (indicating true or false) from this function, then whatever
>>>>> occurs in-between does not make any difference.
>>>>>
>>>>> This would mean that my use of static local variables has no
>>>>> detrimental
>>>>> effect on the applicability of my partial halt decider to the halting
>>>>> problem.
>>>>>
>>>>> u32 H(u32 P, u32 I)
>>>>> {
>>>>>     static u32 Aborted;
>>>>>     static u32* execution_trace;
>>>>>
>>>>
>>>> As I have said, the key part that you seem to miss is that the
>>>> requirement of being a Computation means that the H that is part of H^
>>>> (you call P) must return the same answer as the H that is deciding
>>>> H(H^,H^) even though that embedded machine might be a 'slave' decider.
>>>>
>>>
>>> The actual computation is merely the first invocation and the final
>>> output. The simulated function calls are not actual function calls,
>>> merely an aspect of the larger computation.
>>
>> No, but they ARE supposed to be accurate recreation of a machine that IS
>> a computation on their own.
>>
>>>
>>> As long as every unique input always maps to the same output then we are
>>> good.
>>
>> EVERY TIME. That means if H(H^,H^) is return non-halting in one place,
>> it is so in ALL places, including embedded copies.
>>
>>>
>>>> Thus any logic that tries to 'prove' what would happen in the simulated
>>>> machine past the point the simulation is stopped must be consistent
>>>> with
>>>> the behavior of the simulating Halt Decider.
>>>>
>>>
>>> Yes. After the halt decider has made its decision it need not examine
>>> any code.
>>
>> But it does need to take account of what WILL happen in the machines it
>> was simulating after it stops.
>>
>>>
>>>> This breaks your 'doesn't not affect the behavior before' logic,
>>>> because
>>>
>>> It is moot at this is point.
>>
>> So, you aren't going to make that argument to claim that H can ignore
>> what the embedded copy of H will do?
>>
>>>
>>>> what the decider does after aborting the simulation does sort of
>>>> have an
>>>> affect on the machine being simulated because it has a copy of the
>>>> exact
>>>> same computation and thus will behave the same.
>>>>
>>>
>>> None-the-less the actual halt status decision is unbiased by the
>>> behavior of the halt decider.
>>
>> Only in the sense that the behavior of the simulator instance doesn't
>> affect that actual behavior of the simulated machine instance, but the
>> behavior of the copy of the simulator in the simulated program will
>> affect the behavior of the simulated program.
>>
>> Thus, H can't ignore the affect of copies of it, as they WILL affect the
>> behavior of the simulated machine, and copy the behavior of the
>> simulator.
>>>
>>>> It isn't that the simulator 'causes' the behavior, but that is shown to
>>>> be what is built into the algorithm (so we can't argue 'causality' as
>>>> all is caused by the design which did happen before).
>>>>
>>>
>>>
>>
> 
> 
> The return value of the execution of H(P,P) is a pure function
> of the input to H(P,P). As long as the execution of H(P,P) always
> derives the same return value of 0 then H(P,P) is a pure function
> of its input no matter what occurs inbetween.
> 
> Only this part matters to a [pure function of its inputs]
> The function return values are identical for identical arguments (no
> variation with local static variables, non-local variables, mutable
> reference arguments or input streams).
> https://en.wikipedia.org/wiki/Pure_function
> 
> It doesn't say that local static variables, non-local variables, mutable
> reference arguments cannot be used, merely that their use cannot ever
> cause the same input to derive a different output.
> 
> All of the simulation between the execution of H(P,P) and the return
> value from H(P,P) is an aspect of the internal computation of H(P,P) and
> is derived on the basis of the input to H(P,P).
> 

Right, BUT to say it simulated the machine CORRECTLY, the computation
that it simulated must behave exactly as if it was an independent
machine. Otherwise it is a BROKEN simulation.

That means that when H simulates P calling H, the result of that
simulation must be consistent with that simulated call to H acting
exactly like the outer call to H.

Thus, since the simulating H WILL after a finite amount of time stop it
simulation and return the non-halting answer to its caller, whatever
simulation you get to needs to be compatible with that.

In particular, we KNOW that this simulated H will only run for that
exact same finite amount of steps and then return to its caller.

PERIOD.

H makes a ERROR in applying ANY logic that contradicts that, like
assuming that the H will simulate its input forever.

PERIOD.

P(<P>) is a Halting Computation.

H(<P>, <P>) says that <P> <P> represents a non-halting computation, but
from above we know it is a Halting Computation.

In addition we know that a PROPER simulation of <P> <P> will see P
calling H <P> <P> which we KNOW will return a non-halting value in a
specific number of steps (from our running of P(<P>) and thus we know
that this simulation MUST agree with that path, or H is not properly
simulating its input.

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


#39528 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 11:20 -0500
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<EfSdnT66Affd_tr8nZ2dnUU7-N_NnZ2d@giganews.com>
In reply to#39507
On 9/18/2021 10:42 PM, olcott wrote:
> This is my paraphrase of the requirement a partial
> halt decider must be a pure function of its inputs:
> 
> As long as there is one set of inputs such as such as the formal 
> parameters to a function and a single output such as return value of 
> {1,0} (indicating true or false) from this function, then whatever 
> occurs in-between does not make any difference.
> 
> This would mean that my use of static local variables has no detrimental 
> effect on the applicability of my partial halt decider to the halting 
> problem.
> 
> u32 H(u32 P, u32 I)
> {
>    static u32 Aborted;
>    static u32* execution_trace;

Although a "pure function" would seem to require both elements on the 
link provided below, a "pure function of its inputs" seems to only 
require this first element.

(1) The function return values are identical for identical arguments
(no variation with local static variables, non-local variables, mutable 
reference arguments or input streams). 
https://en.wikipedia.org/wiki/Pure_function

This seems to be saying as long as the final return value of a function 
is consistently the same for any specific initial arguments it does not 
matter that:
(a) local static variables
(b) non-local variables
(c) mutable reference arguments
(d) input streams

are used to achieve this consistent return value.







-- 
Copyright 2021 Pete Olcott

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

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


#39538 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-09-19 19:05 +0100
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<20210919190500.00003629@reddwarf.jmc>
In reply to#39528
On Sun, 19 Sep 2021 11:20:15 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 9/18/2021 10:42 PM, olcott wrote:
> > This is my paraphrase of the requirement a partial
> > halt decider must be a pure function of its inputs:
> > 
> > As long as there is one set of inputs such as such as the formal 
> > parameters to a function and a single output such as return value
> > of {1,0} (indicating true or false) from this function, then
> > whatever occurs in-between does not make any difference.
> > 
> > This would mean that my use of static local variables has no
> > detrimental effect on the applicability of my partial halt decider
> > to the halting problem.
> > 
> > u32 H(u32 P, u32 I)
> > {
> >    static u32 Aborted;
> >    static u32* execution_trace;  
> 
> Although a "pure function" would seem to require both elements on the 
> link provided below, a "pure function of its inputs" seems to only 
> require this first element.
> 
> (1) The function return values are identical for identical arguments
> (no variation with local static variables, non-local variables,
> mutable reference arguments or input streams). 
> https://en.wikipedia.org/wiki/Pure_function
> 
> This seems to be saying as long as the final return value of a
> function is consistently the same for any specific initial arguments
> it does not matter that:
> (a) local static variables
> (b) non-local variables
> (c) mutable reference arguments
> (d) input streams
> 
> are used to achieve this consistent return value.

No, a pure function cannot have any side effects: changing static
variables is a side effect.

/Flibble

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


#39540 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 13:16 -0500
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<j5SdnQ0eGsDk49r8nZ2dnUU7-bnNnZ2d@giganews.com>
In reply to#39538
On 9/19/2021 1:05 PM, Mr Flibble wrote:
> On Sun, 19 Sep 2021 11:20:15 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 9/18/2021 10:42 PM, olcott wrote:
>>> This is my paraphrase of the requirement a partial
>>> halt decider must be a pure function of its inputs:
>>>
>>> As long as there is one set of inputs such as such as the formal
>>> parameters to a function and a single output such as return value
>>> of {1,0} (indicating true or false) from this function, then
>>> whatever occurs in-between does not make any difference.
>>>
>>> This would mean that my use of static local variables has no
>>> detrimental effect on the applicability of my partial halt decider
>>> to the halting problem.
>>>
>>> u32 H(u32 P, u32 I)
>>> {
>>>     static u32 Aborted;
>>>     static u32* execution_trace;
>>
>> Although a "pure function" would seem to require both elements on the
>> link provided below, a "pure function of its inputs" seems to only
>> require this first element.
>>
>> (1) The function return values are identical for identical arguments
>> (no variation with local static variables, non-local variables,
>> mutable reference arguments or input streams).
>> https://en.wikipedia.org/wiki/Pure_function
>>
>> This seems to be saying as long as the final return value of a
>> function is consistently the same for any specific initial arguments
>> it does not matter that:
>> (a) local static variables
>> (b) non-local variables
>> (c) mutable reference arguments
>> (d) input streams
>>
>> are used to achieve this consistent return value.
> 
> No, a pure function cannot have any side effects: changing static
> variables is a side effect.
> 
> /Flibble
> 

It does not have to be an actual pure function, it only has to be a pure 
function of its inputs.

If it has to be a pure function then it is impossible for any software 
function to be able to ever determine that it has been called in 
infinite recursion because on each recursive invocation all of its 
memory of prior invocations is erased.

-- 
Copyright 2021 Pete Olcott

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

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


#39544 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-09-19 19:29 +0100
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<20210919192912.0000074c@reddwarf.jmc>
In reply to#39540
On Sun, 19 Sep 2021 13:16:24 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 9/19/2021 1:05 PM, Mr Flibble wrote:
> > On Sun, 19 Sep 2021 11:20:15 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 9/18/2021 10:42 PM, olcott wrote:  
> >>> This is my paraphrase of the requirement a partial
> >>> halt decider must be a pure function of its inputs:
> >>>
> >>> As long as there is one set of inputs such as such as the formal
> >>> parameters to a function and a single output such as return value
> >>> of {1,0} (indicating true or false) from this function, then
> >>> whatever occurs in-between does not make any difference.
> >>>
> >>> This would mean that my use of static local variables has no
> >>> detrimental effect on the applicability of my partial halt decider
> >>> to the halting problem.
> >>>
> >>> u32 H(u32 P, u32 I)
> >>> {
> >>>     static u32 Aborted;
> >>>     static u32* execution_trace;  
> >>
> >> Although a "pure function" would seem to require both elements on
> >> the link provided below, a "pure function of its inputs" seems to
> >> only require this first element.
> >>
> >> (1) The function return values are identical for identical
> >> arguments (no variation with local static variables, non-local
> >> variables, mutable reference arguments or input streams).
> >> https://en.wikipedia.org/wiki/Pure_function
> >>
> >> This seems to be saying as long as the final return value of a
> >> function is consistently the same for any specific initial
> >> arguments it does not matter that:
> >> (a) local static variables
> >> (b) non-local variables
> >> (c) mutable reference arguments
> >> (d) input streams
> >>
> >> are used to achieve this consistent return value.  
> > 
> > No, a pure function cannot have any side effects: changing static
> > variables is a side effect.
> > 
> > /Flibble
> >   
> 
> It does not have to be an actual pure function, it only has to be a
> pure function of its inputs.

"a pure function of its inputs" makes no sense: a function is either
pure (no side effects at all) or it is impure. Impure functions are
normally called "procedures" rather than functions if we define our
terms taking the intersection of mathematics and computer science as a
guide.

> 
> If it has to be a pure function then it is impossible for any
> software function to be able to ever determine that it has been
> called in infinite recursion because on each recursive invocation all
> of its memory of prior invocations is erased.
 
Then add an extra parameter to the function that is "stack depth" or
some such but note that if we do that then obviously the function is no
longer being called with the same arguments as it recurses.

/Flibble

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


#39546 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 13:40 -0500
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<hMmdnceVtcK4Gdr8nZ2dnUU7-LHNnZ2d@giganews.com>
In reply to#39544
On 9/19/2021 1:29 PM, Mr Flibble wrote:
> On Sun, 19 Sep 2021 13:16:24 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 9/19/2021 1:05 PM, Mr Flibble wrote:
>>> On Sun, 19 Sep 2021 11:20:15 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>    
>>>> On 9/18/2021 10:42 PM, olcott wrote:
>>>>> This is my paraphrase of the requirement a partial
>>>>> halt decider must be a pure function of its inputs:
>>>>>
>>>>> As long as there is one set of inputs such as such as the formal
>>>>> parameters to a function and a single output such as return value
>>>>> of {1,0} (indicating true or false) from this function, then
>>>>> whatever occurs in-between does not make any difference.
>>>>>
>>>>> This would mean that my use of static local variables has no
>>>>> detrimental effect on the applicability of my partial halt decider
>>>>> to the halting problem.
>>>>>
>>>>> u32 H(u32 P, u32 I)
>>>>> {
>>>>>      static u32 Aborted;
>>>>>      static u32* execution_trace;
>>>>
>>>> Although a "pure function" would seem to require both elements on
>>>> the link provided below, a "pure function of its inputs" seems to
>>>> only require this first element.
>>>>
>>>> (1) The function return values are identical for identical
>>>> arguments (no variation with local static variables, non-local
>>>> variables, mutable reference arguments or input streams).
>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>
>>>> This seems to be saying as long as the final return value of a
>>>> function is consistently the same for any specific initial
>>>> arguments it does not matter that:
>>>> (a) local static variables
>>>> (b) non-local variables
>>>> (c) mutable reference arguments
>>>> (d) input streams
>>>>
>>>> are used to achieve this consistent return value.
>>>
>>> No, a pure function cannot have any side effects: changing static
>>> variables is a side effect.
>>>
>>> /Flibble
>>>    
>>
>> It does not have to be an actual pure function, it only has to be a
>> pure function of its inputs.
> 
> "a pure function of its inputs" makes no sense:

It is merely the first element of the linked "pure function" requirements.

>  a function is either
> pure (no side effects at all) or it is impure. Impure functions are
> normally called "procedures" rather than functions if we define our
> terms taking the intersection of mathematics and computer science as a
> guide.
> 
>>
>> If it has to be a pure function then it is impossible for any
>> software function to be able to ever determine that it has been
>> called in infinite recursion because on each recursive invocation all
>> of its memory of prior invocations is erased.
>   
> Then add an extra parameter to the function that is "stack depth" or

// Stack_Depth is incremented in H

void P(u32 x, Stack_Depth)
{
   H(x, x, 0);
}

int main()
{
   Output("Input_Halts = ", H((u32)P, (u32)P, 0));
}

P can break the Stack_Depth value if it has access to Stack_Depth variable.

> some such but note that if we do that then obviously the function is no
> longer being called with the same arguments as it recurses.
> 
> /Flibble
> 


-- 
Copyright 2021 Pete Olcott

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

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


#39547 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-09-19 19:44 +0100
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<20210919194430.00002cdd@reddwarf.jmc>
In reply to#39546
On Sun, 19 Sep 2021 13:40:36 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 9/19/2021 1:29 PM, Mr Flibble wrote:
> > On Sun, 19 Sep 2021 13:16:24 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 9/19/2021 1:05 PM, Mr Flibble wrote:  
> >>> On Sun, 19 Sep 2021 11:20:15 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>      
> >>>> On 9/18/2021 10:42 PM, olcott wrote:  
> >>>>> This is my paraphrase of the requirement a partial
> >>>>> halt decider must be a pure function of its inputs:
> >>>>>
> >>>>> As long as there is one set of inputs such as such as the formal
> >>>>> parameters to a function and a single output such as return
> >>>>> value of {1,0} (indicating true or false) from this function,
> >>>>> then whatever occurs in-between does not make any difference.
> >>>>>
> >>>>> This would mean that my use of static local variables has no
> >>>>> detrimental effect on the applicability of my partial halt
> >>>>> decider to the halting problem.
> >>>>>
> >>>>> u32 H(u32 P, u32 I)
> >>>>> {
> >>>>>      static u32 Aborted;
> >>>>>      static u32* execution_trace;  
> >>>>
> >>>> Although a "pure function" would seem to require both elements on
> >>>> the link provided below, a "pure function of its inputs" seems to
> >>>> only require this first element.
> >>>>
> >>>> (1) The function return values are identical for identical
> >>>> arguments (no variation with local static variables, non-local
> >>>> variables, mutable reference arguments or input streams).
> >>>> https://en.wikipedia.org/wiki/Pure_function
> >>>>
> >>>> This seems to be saying as long as the final return value of a
> >>>> function is consistently the same for any specific initial
> >>>> arguments it does not matter that:
> >>>> (a) local static variables
> >>>> (b) non-local variables
> >>>> (c) mutable reference arguments
> >>>> (d) input streams
> >>>>
> >>>> are used to achieve this consistent return value.  
> >>>
> >>> No, a pure function cannot have any side effects: changing static
> >>> variables is a side effect.
> >>>
> >>> /Flibble
> >>>      
> >>
> >> It does not have to be an actual pure function, it only has to be a
> >> pure function of its inputs.  
> > 
> > "a pure function of its inputs" makes no sense:  
> 
> It is merely the first element of the linked "pure function"
> requirements.

It is merely something that makes no sense. Pure functions CANNOT have
any side effects.

/Flibble

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


#39549 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

Fromolcott <NoOne@NoWhere.com>
Date2021-09-19 14:04 -0500
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<4qydncQrKblXFNr8nZ2dnUU7-QmdnZ2d@giganews.com>
In reply to#39547
On 9/19/2021 1:44 PM, Mr Flibble wrote:
> On Sun, 19 Sep 2021 13:40:36 -0500
> olcott <NoOne@NoWhere.com> wrote:
> 
>> On 9/19/2021 1:29 PM, Mr Flibble wrote:
>>> On Sun, 19 Sep 2021 13:16:24 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>    
>>>> On 9/19/2021 1:05 PM, Mr Flibble wrote:
>>>>> On Sun, 19 Sep 2021 11:20:15 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>       
>>>>>> On 9/18/2021 10:42 PM, olcott wrote:
>>>>>>> This is my paraphrase of the requirement a partial
>>>>>>> halt decider must be a pure function of its inputs:
>>>>>>>
>>>>>>> As long as there is one set of inputs such as such as the formal
>>>>>>> parameters to a function and a single output such as return
>>>>>>> value of {1,0} (indicating true or false) from this function,
>>>>>>> then whatever occurs in-between does not make any difference.
>>>>>>>
>>>>>>> This would mean that my use of static local variables has no
>>>>>>> detrimental effect on the applicability of my partial halt
>>>>>>> decider to the halting problem.
>>>>>>>
>>>>>>> u32 H(u32 P, u32 I)
>>>>>>> {
>>>>>>>       static u32 Aborted;
>>>>>>>       static u32* execution_trace;
>>>>>>
>>>>>> Although a "pure function" would seem to require both elements on
>>>>>> the link provided below, a "pure function of its inputs" seems to
>>>>>> only require this first element.
>>>>>>
>>>>>> (1) The function return values are identical for identical
>>>>>> arguments (no variation with local static variables, non-local
>>>>>> variables, mutable reference arguments or input streams).
>>>>>> https://en.wikipedia.org/wiki/Pure_function
>>>>>>
>>>>>> This seems to be saying as long as the final return value of a
>>>>>> function is consistently the same for any specific initial
>>>>>> arguments it does not matter that:
>>>>>> (a) local static variables
>>>>>> (b) non-local variables
>>>>>> (c) mutable reference arguments
>>>>>> (d) input streams
>>>>>>
>>>>>> are used to achieve this consistent return value.
>>>>>
>>>>> No, a pure function cannot have any side effects: changing static
>>>>> variables is a side effect.
>>>>>
>>>>> /Flibble
>>>>>       
>>>>
>>>> It does not have to be an actual pure function, it only has to be a
>>>> pure function of its inputs.
>>>
>>> "a pure function of its inputs" makes no sense:
>>
>> It is merely the first element of the linked "pure function"
>> requirements.
> 
> It is merely something that makes no sense. Pure functions CANNOT have
> any side effects.
> 
> /Flibble
> 

Then a function that can always know when it has been called in infinite 
recursion is simply not allowed. That makes no sense.

-- 
Copyright 2021 Pete Olcott

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

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


#39551 — Re: Must a partial halt decider be a pure function of its inputs? (addendum)

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-09-19 20:13 +0100
SubjectRe: Must a partial halt decider be a pure function of its inputs? (addendum)
Message-ID<20210919201305.0000555f@reddwarf.jmc>
In reply to#39549
On Sun, 19 Sep 2021 14:04:41 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 9/19/2021 1:44 PM, Mr Flibble wrote:
> > On Sun, 19 Sep 2021 13:40:36 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >   
> >> On 9/19/2021 1:29 PM, Mr Flibble wrote:  
> >>> On Sun, 19 Sep 2021 13:16:24 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>      
> >>>> On 9/19/2021 1:05 PM, Mr Flibble wrote:  
> >>>>> On Sun, 19 Sep 2021 11:20:15 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>         
> >>>>>> On 9/18/2021 10:42 PM, olcott wrote:  
> >>>>>>> This is my paraphrase of the requirement a partial
> >>>>>>> halt decider must be a pure function of its inputs:
> >>>>>>>
> >>>>>>> As long as there is one set of inputs such as such as the
> >>>>>>> formal parameters to a function and a single output such as
> >>>>>>> return value of {1,0} (indicating true or false) from this
> >>>>>>> function, then whatever occurs in-between does not make any
> >>>>>>> difference.
> >>>>>>>
> >>>>>>> This would mean that my use of static local variables has no
> >>>>>>> detrimental effect on the applicability of my partial halt
> >>>>>>> decider to the halting problem.
> >>>>>>>
> >>>>>>> u32 H(u32 P, u32 I)
> >>>>>>> {
> >>>>>>>       static u32 Aborted;
> >>>>>>>       static u32* execution_trace;  
> >>>>>>
> >>>>>> Although a "pure function" would seem to require both elements
> >>>>>> on the link provided below, a "pure function of its inputs"
> >>>>>> seems to only require this first element.
> >>>>>>
> >>>>>> (1) The function return values are identical for identical
> >>>>>> arguments (no variation with local static variables, non-local
> >>>>>> variables, mutable reference arguments or input streams).
> >>>>>> https://en.wikipedia.org/wiki/Pure_function
> >>>>>>
> >>>>>> This seems to be saying as long as the final return value of a
> >>>>>> function is consistently the same for any specific initial
> >>>>>> arguments it does not matter that:
> >>>>>> (a) local static variables
> >>>>>> (b) non-local variables
> >>>>>> (c) mutable reference arguments
> >>>>>> (d) input streams
> >>>>>>
> >>>>>> are used to achieve this consistent return value.  
> >>>>>
> >>>>> No, a pure function cannot have any side effects: changing
> >>>>> static variables is a side effect.
> >>>>>
> >>>>> /Flibble
> >>>>>         
> >>>>
> >>>> It does not have to be an actual pure function, it only has to
> >>>> be a pure function of its inputs.  
> >>>
> >>> "a pure function of its inputs" makes no sense:  
> >>
> >> It is merely the first element of the linked "pure function"
> >> requirements.  
> > 
> > It is merely something that makes no sense. Pure functions CANNOT
> > have any side effects.
> > 
> > /Flibble
> >   
> 
> Then a function that can always know when it has been called in
> infinite recursion is simply not allowed. That makes no sense.
 
Your conclusion makes no sense. What isn't allowed here is
your use of the term "pure function" to describe something that isn't a
pure function.

/Flibble

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


Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.theory


csiph-web