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


Groups > comp.theory > #33741

Re: Infinitely Recursive input on HP Proofs

From André G. Isaak <agisaak@gm.invalid>
Newsgroups comp.theory
Subject Re: Infinitely Recursive input on HP Proofs
Date 2021-05-16 19:15 -0600
Organization Christians and Atheists United Against Creeping Agnosticism
Message-ID <s7sg34$94t$1@dont-email.me> (permalink)
References (3 earlier) <0sCdnWsgz4JPGjz9nZ2dnUU7-RvNnZ2d@giganews.com> <R%foI.542844$nn2.335922@fx48.iad> <-rednavQTY_BDTz9nZ2dnUU7-SXNnZ2d@giganews.com> <_yhoI.542847$nn2.449398@fx48.iad> <EsCdnduL051HNTz9nZ2dnUU7-d_NnZ2d@giganews.com>

Show all headers | View raw


On 2021-05-16 17:21, olcott wrote:
> On 5/16/2021 6:05 PM, Richard Damon wrote:
>> On 5/16/21 5:37 PM, olcott wrote:
>>> On 5/16/2021 4:19 PM, Richard Damon wrote:
>>>> On 5/16/21 5:00 PM, olcott wrote:
>>>>> On 5/16/2021 3:21 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Any genius knowing the theory of computation quite well can easily
>>>>>>> confirm that Ĥ(Ĥ) specifies the non halting behavior pattern of
>>>>>>> [infinitely_nested_simulation] to every simulating halt decider.
>>>>>>> This equally applies to all of the halting problem instances.
>>>>>>>
>>>>>>> Ĥ(Ĥ) is short-hand for:
>>>>>>> Now Ĥ is a Turing machine, so that it will have some description in
>>>>>>> Σ*,
>>>>>>> say ŵ. This string, in addition to being the description of Ĥ can
>>>>>>> also be used
>>>>>>> as input string. We can therefore legitimately ask what would happen
>>>>>>> if Ĥ is
>>>>>>> applied to ŵ. (Linz:1990:320)
>>>>>>>
>>>>>>> Linz, Peter 1990. An Introduction to Formal Languages and
>>>>>>> Automata. Lexington/Toronto: D. C. Heath and Company. (315-320)
>>>>>>
>>>>>> Nonsense.  H is the name given in Linz to a non-existent Turing
>>>>>> machine.  H^, derived from it, also does not exit.  Anyone who has 
>>>>>> read
>>>>>> that book should know that H^([H^]) specifies no behaviour at all.
>>>>>>
>>>>>> You have constructed a poor-man's partial decider that gets the "hat"
>>>>>> case wrong, but you can't justify the wrong answer by appeal Linz.
>>>>>>
>>>>>> Your "infinitely nested simulation" explanation for your decider 
>>>>>> giving
>>>>>> the wrong answer can be put on a more formal basis, but you can't 
>>>>>> do by
>>>>>> re-using the names of nonexistent TM's from Linz.
>>>>>>
>>>>>
>>>>> Well I won't say that you are not a genius or that you don't know the
>>>>> theory of computation very well.
>>>>>
>>>>> The actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to every
>>>>> simulating halt decider. This [infinitely_nested_simulation] is more
>>>>> complex than the one that Halts recognizes.
>>>>>
>>>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
>>>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
>>>>>
>>>>> The above is adapted from (Linz:1990:319).
>>>>> It shows that Turing machine Ĥ copies its input at (q0) and begins
>>>>> executing an embedded copy of the original halt decider with this 
>>>>> input
>>>>> at (qx).
>>>>>
>>>>> The (qy) state indicates that the halt decider decides that its input
>>>>> would halt. The ((qn)) state indicates the input would not halt. The
>>>>> appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt
>>>>> decider decides that its input would halt.
>>>>>
>>>>> It can be understood from the above specification that when the 
>>>>> embedded
>>>>> halt decider @Ĥ.qx bases its halting decision on simulating its input,
>>>>> and it has (Ĥ,  Ĥ) as its input that:
>>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
>>>>> this copy then
>>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
>>>>> this copy then
>>>>> Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
>>>>> this copy...
>>>>> unless and until the halt decider @Ĥ.qx stops simulating its input.
>>>>
>>>> BUT, since H is required to be finite in execution, the copy of H 
>>>> within
>>>> H^ must have some alteration from a simple simulator to break the loop.
>>>>
>>>> If it does, then it WILL break the loop, and be finite in execution.
>>>>
>>>> If it doesn't then H(H^,H^) won't break the loop, and thus will not
>>>> answer in finite time and thus fail to give an answer and not be a
>>>> decider.
>>>>
>>>
>>> That is why we need this truism to dislodge the pathological
>>> self-reference:
>>>
>>> On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> Truism:
>>>>> Every simulation that would never stop unless Halts() stops
>>>>> it at some point specifies infinite execution.
>>>>
>>>> Any algorithm that implements this truism is, of course, a halting
>>>> decider.
>>>
>>> Whether a computation is finite is more nuanced than it simply stops
>>> running otherwise an infinite loop that had its simulation aborted
>>> because its behavior matched the [infinite_loop] non-halting behavior
>>> pattern would have to be classified as a halting computation.
>>>
>>> Unless the simulating halt decider stops simulating Ĥ(Ĥ) at some point
>>> its simulation would be infinite ∴ meets the non-halting truism.
>>>
>>
>> But you can't use a 'Falsism' to change the facts about the definition.
>>
>> And, as I have said, there IS no pathological self-reference in the 
>> problem.
>>
>> YOU create the self-reference by not implementing the required copy
>> operation. In actuality the Linz proof has no real self-reference, just
>> two copies of what just happens to be the same thing.
>>
> 
> I am referring to the complete Peter Linz version where a copy <is> made.
> 
> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
> 
> The above is adapted from (Linz:1990:319).
> It shows that Turing machine Ĥ copies its input at (q0) and begins 
> executing an embedded copy of the original halt decider with this input 
> at (qx).
> 
> The (qy) state indicates that the halt decider decides that its input 
> would halt. The ((qn)) state indicates the input would not halt. The 
> appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt 
> decider decides that its input would halt.
> 
> It can be understood from the above specification that when the embedded 
> halt decider @Ĥ.qx bases its halting decision on simulating its input, 
> and it has (Ĥ,  Ĥ) as its input that:

But Linz's specification doesn't make any mention of simulating the 
input, so there isn't anything intrinsincally recursive about Linz's 
specification. It's only *your* decision to employ simulation which 
leads to potentially infinite recursion.

The actual specification involves no self-reference or recursion.

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

Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 14:09 -0500
  Re: Infinitely Recursive input on HP Proofs Jeff Barnett <jbb@notatt.com> - 2021-05-16 13:46 -0600
  Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 19:05 -0400
    Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 18:21 -0500
      Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:11 -0400
        Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 21:01 -0500
          Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 23:18 -0400
            Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 22:23 -0500
              Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:11 -0400
              Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:26 -0400
                Re: Infinitely Recursive input on HP Proofs Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-05-17 05:45 -0700
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 10:23 -0500
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:41 -0400
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 20:27 +0100
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 14:31 -0500
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:38 +0100
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 19:54 -0500
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 21:21 -0400
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-20 12:57 +0100
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:43 -0400
      Re: Infinitely Recursive input on HP Proofs André G. Isaak <agisaak@gm.invalid> - 2021-05-16 19:15 -0600
        Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 20:34 -0500
          Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:55 -0400
  Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 15:56 -0400
  Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-16 21:21 +0100
    Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 17:19 -0400
      Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:37 -0500
    Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:00 -0500
      Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 02:19 +0100
        Re: Infinitely Recursive input on HP Proofs (Full Linz text) olcott <NoOne@NoWhere.com> - 2021-05-16 20:54 -0500
          Re: Infinitely Recursive input on HP Proofs (Full Linz text) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:57 +0100
            Re: Infinitely Recursive input on HP Proofs (eternally on this point) olcott <NoOne@NoWhere.com> - 2021-05-17 20:34 -0500

csiph-web