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


Groups > comp.theory > #33820

Re: Infinitely Recursive input on HP Proofs (Full Linz text)

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinitely Recursive input on HP Proofs (Full Linz text)
Date 2021-05-18 01:57 +0100
Organization A noiseless patient Spider
Message-ID <87r1i4270b.fsf@bsb.me.uk> (permalink)
References (1 earlier) <a4ydnWkMIKhS8Dz9nZ2dnUU7-L3NnZ2d@giganews.com> <87im3i5t12.fsf@bsb.me.uk> <0sCdnWsgz4JPGjz9nZ2dnUU7-RvNnZ2d@giganews.com> <87bl9a40nr.fsf@bsb.me.uk> <KKidnYZUNMQlUTz9nZ2dnUU7-f_NnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 5/16/2021 8:19 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> 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.
>>
>> No.  H and H^ specify no behaviour.  These lines:
>>
>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
>>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
>>
>> (with the text below) specify the behaviour of no Turing machine.
>>
>>> 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.
>>
>> The above is Linz (except for the altered specification).  But this is
>> all yours:
>>
>>> 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.
>
> In other words...

Generally not a good start.  You almost always don't understand what I'm
saying (or you misrepresent it).

> you are saying that the following Linz text would not specify the
> above behavior to a simulating halt decider H?

No, I am not saying that.  But you've cut what I said about the above.
If you want to try to understand what I said about the above, go find it
and ask a few questions about it.

<cut bits from Linz>
-- 
Ben.
  "the fact that a computation halts does not entail that it is a halting
  computation"  Peter Olcott, May 2021.

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