Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Richard Damon <news.x.richarddamon@xoxy.net> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Must a partial halt decider be a pure function of its inputs? (addendum) |
| Date | 2021-09-19 14:51 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <si80rd$mmo$1@dont-email.me> (permalink) |
| References | <O9-dnbixA9Y0LNv8nZ2dnUU7-VvNnZ2d@giganews.com> <EfSdnT66Affd_tr8nZ2dnUU7-N_NnZ2d@giganews.com> <rZK1J.17245$dI3.3336@fx10.iad> <9v2dncLT_fQ24tr8nZ2dnUU7-X_NnZ2d@giganews.com> |
On 9/19/21 2:21 PM, olcott wrote:
> On 9/19/2021 1:05 PM, Richard Damon wrote:
>> On 9/19/21 12:20 PM, olcott 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.
>>>
>>
>>
>> Right, those items, do not BY THEMSELVES, make the code not a
>> computation. They do make it much easier for it to end up being not a
>> computation.
>>
>> Note, The rules for Computaiton theory are different than in 'Normal'
>> Computer Science, which tend to define a Pure Function on a more
>> mechanical rather than behavioral definition.
>>
>> Enforcing the mechanical rules makes sure you meet the behavioral rules,
>> but are not absolutely required.
>>
>> If you do any of that list, it can be very hard to show that you code
>> is, in fact, a computation.
>>
>
> Surprisingly it seems that you have the best understanding of this of
> all of the reviewers that have responded to this.
>
>
>
> void P(u32 x)
> {
> H(x, x);
> }
>
> int main()
> {
> Output("Input_Halts = ", H((u32)P, (u32)P));
> }
>
> Does this still meet the Halting Problem requirement that the function
> must be a pure function of its inputs:
>
> The concern is that H is called three times and only terminates its
> input after it has seen enough of the execution trace to determine that
> it specifies infinitely recursive simulation. The initial invocation of
> H(P,P) always eventually returns 0. The intermediate simulations of
> H(P,P) never return.
>
> Can we construe this whole thing as a single computation such that the
> eventual return value of the execution H(P,P) is a pure function of its
> inputs?
>
>
The problem is that whatever you are going to call your decider that
needs to be this pure function MUST be allowed to be used in various
contexts and must stay consistent.
For instance, lets look at your H.
We have the call to H inside the top level instance of P. P(P) calls
H(P,P) and this returns Non-Halting as aggreed (I think) by everyone.
We then have the call H as a top level function, like in your main
above, and there again, we have the call to H(P,P) and it returns
non-halting.
This is consistent to the previous instance, but would seem to be the
wrong answer (since P(P) Halted), but your claim is that it is right
because the SIMULATED P(P) never halted. But for the simulted P(P) to
not halt, then we see the simulated P calls a Simulated H(P,P) and for P
to never halt, the H(P,P) must not return.
This means that either this simulation itself is defective (which puts
your whole proof into shambles) or it demonstrates that H(P,P) doesn't
always behave the same way, and thus H is not a computation. This also
makes your whole proof irrelevant, as if H isn't actually a computation,
then it isn't possibly a decider.
You CAN'T just try to define that everything is a single computation, as
the problem physically has at least two computations in view: P(I) and
H(P,I) and for the H^ case, P(I) envokes the same computation at H(P,I)
and these must agree, AND the answer given by H(P,I) must agrees with
the behavior of P(I). Your whole proof seems to be trying to justify the
answer from H(P,I) not matching the behavior of P(I) but that whole
arguement seems to rest on the copy of H inside the simulated P not
doing exactly the same thing as the outer H.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web