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


Groups > comp.theory > #39629

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

From André G. Isaak <agisaak@gm.invalid>
Newsgroups comp.theory
Subject Re: Must a partial halt decider be a pure function of its inputs?
Date 2021-09-20 16:06 -0600
Organization Christians and Atheists United Against Creeping Agnosticism
Message-ID <sib0ll$13s$1@dont-email.me> (permalink)
References (6 earlier) <A4CdnTwZ49dkRNX8nZ2dnUU7-SHNnZ2d@giganews.com> <siapa2$k39$1@dont-email.me> <somdnStr_seybtX8nZ2dnUU7-XHNnZ2d@giganews.com> <siat5v$ubi$1@dont-email.me> <aP2dnWvpR-8kn9T8nZ2dnUU7-SPNnZ2d@giganews.com>

Show all headers | View raw


On 2021-09-20 15:52, olcott wrote:
> On 9/20/2021 4:07 PM, André G. Isaak wrote:
>> On 2021-09-20 14:46, olcott wrote:
>>> On 9/20/2021 3:01 PM, André G. Isaak wrote:
>>>> On 2021-09-20 12:59, olcott wrote:
>>>>> On 9/20/2021 12:59 PM, André G. Isaak wrote:
>>>> 
>>>>>> But, as I have pointed out previously, and which you
>>>>>> ignored, you are then claiming that your *real* halt
>>>>>> decider is the combination of H, H1, Hx and your
>>>>>> 'decidability decider'.
>>>>>> 
>>>>> 
>>>>> Yes.
>>>>> 
>>>>>> In that case your P must be derived from that *combination*
>>>>>> if you want to claim that it is analogous to Linz's H_Hat.
>>>>>> 
>>>>> 
>>>>> No Olcott H1,H,Hx is superior to anything that Linz said
>>>>> because there is no input that it cannot decide.
>>>> 
>>>> So show us the actual code for this new routine. I know you are
>>>>  never going to reveal the code for your H, but you can at
>>>> least show the code for this combination routine which calls H,
>>>> H1 and Hx and returns true for halting and false for
>>>> non-halting.
>>>> 
>>>> Then show the code for the hat construction derived from this
>>>> new decider and show how this decider can correctly decide that
>>>> hat construction.
>>>> 
>>> 
>>> Before I show any code I have to have my use of static local data
>>>  validated as acceptable.
>> 
>> It won't be 'validated' because it simply isn't allowed. As Richard
>>  has pointed out the mere presence of a static variable doesn't 
>> necessarily rule out something as a computation if it is simply
>> there for efficiency's sake, but if the routine actually *depends*
>> on the use of a static variable so that difference invocations have
>> access to different information, then you're not dealing with a
>> computation.
>> 
> 
> Therefore a TM cannot possibly determine whether or not it is being 
> infinitely simulated because it is required to make sure that it
> erases the execution trace that it stored between recursive
> simulations.

And? The fact that you really want to be able to do something isn't an 
argument that that thing is actually doable.

> This weirdly enough would show that C is strictly more powerful than
> a TM, thus you and Richard are probably wrong.

No, it doesn't show this at all.

There are no computations which can be done in C which cannot also be 
done by a Turing Machine. The problem is that you are dealing with 
something that isn't a computation. We *could* convert this to a 
computation by supplying your 'execution trace' as a formal input 
parameter, but then you wouldn't be dealing with the halting problem 
since that problem defines a halt decider as taking a specific set of 
inputs which does not include an 'execution trace'.

>>>>>> The whole point of the Linz proof is that for *any* 'halt
>>>>>> decider' X, one can always construct an X_Hat which it
>>>>>> cannot decide correctly. Your combined H+H1+Hx+DD is just
>>>>>> as susceptible to this as any other putative 'halt
>>>>>> decider'.
>>>>>> 
>>>>>> André
>>>>>> 
>>>>> 
>>>>> The whole point of all these proofs is that no universal halt
>>>>>  decider exists. The Olcott combination of H1,H,Hx is such a
>>>>>  universal halt decider that is purported to not exist.
>>>>> 
>>>>> The key breakthrough is that Rice's theorem "proved" that no
>>>>>  decidability decider can possibly exist thus once we have
>>>>> such a decidability decider Rice's theorem and the halting
>>>>> theorem both fail.
>>>> 
>>>> You don't seem to understand what Rice's theorem actually
>>>> states.
>>>> 
>>>> André
>>>> 
>>> 
>>> Historically on comp.theory this has meant that it is impossible
>>> to create a TM the rejects undecidable inputs.
>> 
>> What do you mean by an 'undecidable input'? Input to what?
>> 
>> Rice's theorem says you can't create a TM X which decides some 
>> nontrivial semantic property of an arbitary Turing Machine Y (or of
>>  the language accepted by Y). Once you start talking about 'inputs'
>> you are talking about computations rather than Turing Machines.
>> 
>> André
>> 
> 
> H1 decides that H cannot correctly decide the halting status of P.

Which is neither a property of H nor of P but a statement about the 
specific computation H(P, P).

Rice's theorem is concerned with semantic properties of Turing Machines, 
not of specific computations.

André

-- 
To email remove 'invalid' & replace 'gm' with well known Google mail
service.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


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