Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"It's when they say 2 + 2 = 5 that I begin to argue." -- Eric Pepke


devel / comp.theory / Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

SubjectAuthor
* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ keyolcott
+- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Python
+- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
 `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |+* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Malcolm McLean
    ||`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    || `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Malcolm McLean
    ||  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    ||   +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    ||   |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    ||   | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    ||   |  `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    ||   `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    | +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    | |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    | | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    | |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    | |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    | |    `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    | |     `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |    `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |     +- Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |     `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |      +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |      |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |      | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |      |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |      |   `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |      `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |       `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |   +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |   |`- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |+- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Python
    |   |        |    |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |    `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |     `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Jeff Barnett
    |   |        |    |      |`- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Jeff Barnett
    |   |        |    |      |   |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   | `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |   |  `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |   |    `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   |     `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |   |      `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   |       +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |      |   |       |`- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |      |   |       `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |      |   `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |      `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |       `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |        `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |         `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |          +- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |          `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |           `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |            +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |            |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |            | +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Dennis Bush
    |   |        |    |            | |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |            | | +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Python
    |   |        |    |            | | |`* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |            | | | +- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Python
    |   |        |    |            | | | `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |            | | `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |            | +* Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse
    |   |        |    |            | |`- Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |            | `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Richard Damon
    |   |        |    |            `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |             +- Refuting the Peter Linz Halting Problem Proof --- Version(10) [Malcolm McLean
    |   |        |    |             `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |              `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |               `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    |                `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   |        |    |                 `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        |    `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [olcott
    |   |        `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [André G. Isaak
    |   `* Refuting the Peter Linz Halting Problem Proof --- Version(10) [Andy Walker
    `- Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piecBen Bacarisse

Pages:12345678910111213141516171819202122232425262728293031323334353637383940
Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87mth1ae3z.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29366&group=comp.theory#29366

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 01:25:52 +0100
Organization: A noiseless patient Spider
Lines: 86
Message-ID: <87mth1ae3z.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18rqshZXqCoRmZ6gWJMGECNOOaGoVfBpqU="
Cancel-Lock: sha1:TpvqULNCD6Gqs5vHm9Suuc/Qnpw=
sha1:lEtz2vwVL+ag/9VUJ+MAJCfdcfs=
X-BSB-Auth: 1.203c10a97a67431c3aea.20220404012552BST.87mth1ae3z.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 00:25 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>> understanding what this means.
>>>>>>>>
>>>>>>>> OK let's give it a shot.
>>>>>>>
>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>> assumptions to be made explicit.
>>>>>>>
>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>
>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>> things to iron out first.)
>>>>>>>
>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>> Can every element of this set be enumerated in finite time?
>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>> Yes through algorithmic compression.
>>>>>
>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>
>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>> membership can't have a number as input. TMs accept or reject strings,
>>>> not numbers.
>>>>
>>>> But surely the iseven(n) function is computable, so how do you think we
>>>> should resolve this? Hint: think encoding.
>>>> Can you have a stab at specifying E now using Linz's notation?
>>>
>>> I want to very thoroughly go through all of the points completely as
>>> efficiently as possible. Because a C function could do this as a pure
>>> function of its ASCII digit sequence inputs by merely examining the
>>> last digits for: {0,2,4,8} we know that E is decidable.
>> It will take longer if you take digressions like this! C is not a
>> complete model of computation. No C function can do the job for any
>> number.
>> Let's stick to TMs. What encoding would you use for a TM decider for
>> this problem? Can you specify it using Linz's notation?
>>
>
> ASCII text digits. No.

ASCII is a red-herring here. It's just a mapping from symbols to
numbers and TM's use symbols so the numbers don't come into it.

Yes, you can use digits to encode the number, but you usually get a more
complicated TM is you use decimal digits. I'm going to ask you to write
the TM E shortly and it's easier if you use either binary or unary.

But that's just friendly advice. I leave it to you to pick what set of
symbols (and their meanings) is to be used to encode the number on the
TMs tape.

What's the hurdle with specifying it? It's going to have this pattern:

E.q0 ??? ⊦* E.qy if ???
E.q0 ??? ⊦* E.qn otherwise.

(The three ??? won't all be the same things.) Any idea how to flesh
this out?

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87ilrpae0j.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29367&group=comp.theory#29367

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 01:27:56 +0100
Organization: A noiseless patient Spider
Lines: 85
Message-ID: <87ilrpae0j.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk> <S%p2K.922$n41.730@fx35.iad>
<87czhxbuu0.fsf@bsb.me.uk>
<n72dnaG_RMvdrNf_nZ2dnUU7_81g4p2d@giganews.com>
<871qydbu46.fsf@bsb.me.uk>
<1cudneKRZsRXqNf_nZ2dnUU7_8xh4p2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+b+xO9bT94vurvVAKhuTPZ5HPj1lsTUZ0="
Cancel-Lock: sha1:iGcmUBDb4Qya3lcABfFe731iW0s=
sha1:6G/yukZTeoBd/Ho7XGRs8p45q24=
X-BSB-Auth: 1.b74030c6c9c3ee2318a1.20220404012756BST.87ilrpae0j.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 00:27 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 6:54 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/3/2022 6:39 PM, Ben Bacarisse wrote:
>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>
>>>>> On 4/3/22 6:57 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>> understanding what this means.
>>>>>>>>>>
>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>
>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>
>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>
>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>> things to iron out first.)
>>>>>>>>>
>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>> Yes through algorithmic compression.
>>>>>>>
>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>> not numbers.
>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>> should resolve this? Hint: think encoding.
>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>>
>>>>>
>>>>> And I would say YES, because they can be given a REPRESENTATION of a
>>>>> Number.
>>>> And you are welcome to say that. You won't be confused by saying it.
>>>> The trouble with a blanket yes is what representations can we use?
>>>
>>> All of this is totally extraneous.
>>> Is a memebership algorithm for E possible? YES any C program could
>>> trivially implement it.
>> You are not in "student mode" here. You are laying down the law, but
>> that's my job!
>> First, E is the name I suggested a TM, not for the set of even numbers.
>> You must use the names I suggest for the things I suggest you do or
>> there will be dozens of posts just about what E is or what X is!
>> Second, you don't yet know enough about compatibility theory to switch
>> between TMs and C. C is not suitable for lots of reasons.
>> Let's stick to TMs until that is fully wrapped up.
>
> Any encoding besides ASCII text digits is intolerable.

I've addressed this point to move the process forward in the main chain
of the thread.

This is going to turn into a mess if I have to reply to everyone as well
as you and also to your replies to them. I am going to limit my replies
to posts of yours in direct reply to mine from now on.

If you want to argue with RD or MM about all this, be my guest, but I'll
be talking to you about these exercises in the main chain of the thread.

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29368&group=comp.theory#29368

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 19:34:06 -0500
Date: Sun, 3 Apr 2022 19:33:57 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87mth1ae3z.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 100
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-i4FNUnphlWLkedkljhpn7EyZmP/DdV8KT0XYE4pNSNqBas+Oa9PG8VUNxFb4El91b0jnjKqyOEk371i!ZsTaxnqsmMBzrN2LicdyBq56BFvA7WU0H0JBI6HJsLp/OW0qPX45ZpoVAXspng9vqaQYoNVccbO+
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5924
 by: olcott - Mon, 4 Apr 2022 00:33 UTC

On 4/3/2022 7:25 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>> understanding what this means.
>>>>>>>>>
>>>>>>>>> OK let's give it a shot.
>>>>>>>>
>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>> assumptions to be made explicit.
>>>>>>>>
>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>
>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>> things to iron out first.)
>>>>>>>>
>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>> Yes through algorithmic compression.
>>>>>>
>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>
>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>> not numbers.
>>>>>
>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>> should resolve this? Hint: think encoding.
>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>
>>>> I want to very thoroughly go through all of the points completely as
>>>> efficiently as possible. Because a C function could do this as a pure
>>>> function of its ASCII digit sequence inputs by merely examining the
>>>> last digits for: {0,2,4,8} we know that E is decidable.
>>> It will take longer if you take digressions like this! C is not a
>>> complete model of computation. No C function can do the job for any
>>> number.
>>> Let's stick to TMs. What encoding would you use for a TM decider for
>>> this problem? Can you specify it using Linz's notation?
>>>
>>
>> ASCII text digits. No.
>
> ASCII is a red-herring here. It's just a mapping from symbols to
> numbers and TM's use symbols so the numbers don't come into it.
>
> Yes, you can use digits to encode the number, but you usually get a more
> complicated TM is you use decimal digits. I'm going to ask you to write
> the TM E shortly and it's easier if you use either binary or unary.
>
> But that's just friendly advice. I leave it to you to pick what set of
> symbols (and their meanings) is to be used to encode the number on the
> TMs tape.
>
> What's the hurdle with specifying it? It's going to have this pattern:
>
> E.q0 ??? ⊦* E.qy if ???
> E.q0 ??? ⊦* E.qn otherwise.
>
> (The three ??? won't all be the same things.) Any idea how to flesh
> this out?
>

The whole algorithm is merely checking the last ASCII digit for
{0,2,4,6,8}. In binary this would check the last digit for 0.
So not too bad even in TM.

Move to last digit
last_digit == 0 then YES
else NO

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<RJCdnVMp-PO-oNf_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29369&group=comp.theory#29369

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 19:34:43 -0500
Date: Sun, 3 Apr 2022 19:34:34 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<S%p2K.922$n41.730@fx35.iad> <87czhxbuu0.fsf@bsb.me.uk>
<n72dnaG_RMvdrNf_nZ2dnUU7_81g4p2d@giganews.com> <871qydbu46.fsf@bsb.me.uk>
<1cudneKRZsRXqNf_nZ2dnUU7_8xh4p2d@giganews.com> <87ilrpae0j.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87ilrpae0j.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <RJCdnVMp-PO-oNf_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 93
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-P0eHGM/HK9g4fJI6fKRJLC+kMOh3Et8hYOVfHz190JGfIqc/dbO7b1kVNaT/Qp7TmFYu1TEQSr/TDC5!sZr5LDWHHcdhKpT+nTHGUFOOOOo/apL6JKPbjkMEsbIgPmWIuMAfOo7HaQqd3hJ4U6rYuXBMLg+b
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 6011
 by: olcott - Mon, 4 Apr 2022 00:34 UTC

On 4/3/2022 7:27 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 6:54 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 4/3/2022 6:39 PM, Ben Bacarisse wrote:
>>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>>
>>>>>> On 4/3/22 6:57 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>>> understanding what this means.
>>>>>>>>>>>
>>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>>
>>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>>
>>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>>
>>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>>> things to iron out first.)
>>>>>>>>>>
>>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>>> Yes through algorithmic compression.
>>>>>>>>
>>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>>> not numbers.
>>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>>> should resolve this? Hint: think encoding.
>>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>>>
>>>>>>
>>>>>> And I would say YES, because they can be given a REPRESENTATION of a
>>>>>> Number.
>>>>> And you are welcome to say that. You won't be confused by saying it.
>>>>> The trouble with a blanket yes is what representations can we use?
>>>>
>>>> All of this is totally extraneous.
>>>> Is a memebership algorithm for E possible? YES any C program could
>>>> trivially implement it.
>>> You are not in "student mode" here. You are laying down the law, but
>>> that's my job!
>>> First, E is the name I suggested a TM, not for the set of even numbers.
>>> You must use the names I suggest for the things I suggest you do or
>>> there will be dozens of posts just about what E is or what X is!
>>> Second, you don't yet know enough about compatibility theory to switch
>>> between TMs and C. C is not suitable for lots of reasons.
>>> Let's stick to TMs until that is fully wrapped up.
>>
>> Any encoding besides ASCII text digits is intolerable.
>
> I've addressed this point to move the process forward in the main chain
> of the thread.
>
> This is going to turn into a mess if I have to reply to everyone as well
> as you and also to your replies to them. I am going to limit my replies
> to posts of yours in direct reply to mine from now on.
>
> If you want to argue with RD or MM about all this, be my guest, but I'll
> be talking to you about these exercises in the main chain of the thread.
>

Good idea.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87czhxadkg.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29370&group=comp.theory#29370

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 01:37:35 +0100
Organization: A noiseless patient Spider
Lines: 23
Message-ID: <87czhxadkg.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<0fb8f03a-6589-4fc2-81b6-4fc86667442dn@googlegroups.com>
<D6edneV9g7navtf_nZ2dnUU7_83NnZ2d@giganews.com>
<1ce913ac-a7df-49ed-928f-1570ccdd01b0n@googlegroups.com>
<n72dnaa_RMs0rdf_nZ2dnUU7_81QAAAA@giganews.com>
<87v8vpafdz.fsf@bsb.me.uk>
<1cudnR2RZsSyq9f_nZ2dnUU7_8xh4p2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18WH8ZCupbDl4CDKhN8+WdBco7s7zLgioE="
Cancel-Lock: sha1:el3bZ7JZRXHvYSsFm42SfWWmq2I=
sha1:yilhduGqnPBbypFbMl6EUCohMUU=
X-BSB-Auth: 1.3eab1512c9c89dc28790.20220404013735BST.87czhxadkg.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 00:37 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 6:58 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> I will never tolerate the tediousness of encoding TMs, my proof is
>>> sufficient.
>> Oh! I thought you were entering into this with an open mind and that
>> you were prepared to do it properly. Encoding TMs is central to the
>> halting problem.
>> Do you want to stop?
>
> I will not tolerate TMs that cannot store an ASCII digit as a single
> tape element.

You can use any symbols you like as the tape alphabet. The ASCII part
is irrelevant because TMs are defined in terms of the abstract symbols
and have no interest in what numbers are used by you and me to send
those symbols across the Internet (or, indeed, what numbers are used
for them in any context).

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<877d85adc8.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29371&group=comp.theory#29371

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 01:42:31 +0100
Organization: A noiseless patient Spider
Lines: 93
Message-ID: <877d85adc8.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
<87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/LJ9+/IE/SscsAq+6VIwHkpYue6ZKdhqo="
Cancel-Lock: sha1:GYZ/ZiB10LHPxSjBvcl1u5va+g0=
sha1:IBwsHlkqGTb3i/3aw3r8HeOXyjw=
X-BSB-Auth: 1.06b7946b2b7a70daa680.20220404014231BST.877d85adc8.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 00:42 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 7:25 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>> understanding what this means.
>>>>>>>>>>
>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>
>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>
>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>
>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>> things to iron out first.)
>>>>>>>>>
>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>> Yes through algorithmic compression.
>>>>>>>
>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>>
>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>> not numbers.
>>>>>>
>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>> should resolve this? Hint: think encoding.
>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>
>>>>> I want to very thoroughly go through all of the points completely as
>>>>> efficiently as possible. Because a C function could do this as a pure
>>>>> function of its ASCII digit sequence inputs by merely examining the
>>>>> last digits for: {0,2,4,8} we know that E is decidable.
>>>> It will take longer if you take digressions like this! C is not a
>>>> complete model of computation. No C function can do the job for any
>>>> number.
>>>> Let's stick to TMs. What encoding would you use for a TM decider for
>>>> this problem? Can you specify it using Linz's notation?
>>>>
>>>
>>> ASCII text digits. No.
>> ASCII is a red-herring here. It's just a mapping from symbols to
>> numbers and TM's use symbols so the numbers don't come into it.
>> Yes, you can use digits to encode the number, but you usually get a more
>> complicated TM is you use decimal digits. I'm going to ask you to write
>> the TM E shortly and it's easier if you use either binary or unary.
>> But that's just friendly advice. I leave it to you to pick what set of
>> symbols (and their meanings) is to be used to encode the number on the
>> TMs tape.
>> What's the hurdle with specifying it? It's going to have this pattern:
>>
>> E.q0 ??? ⊦* E.qy if ???
>> E.q0 ??? ⊦* E.qn otherwise.
>>
>> (The three ??? won't all be the same things.) Any idea how to flesh
>> this out?
>
> The whole algorithm is merely checking the last ASCII digit for
> {0,2,4,6,8}. In binary this would check the last digit for 0. So not
> too bad even in TM.

It seems you want to skip ahead (and that's fine), but please try to
specify the TM formally. Then you can write it. After all,
specification is where the main gap in understanding lies for you.

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<rYKdnZAcHKNe3Nf_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29372&group=comp.theory#29372

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 19:54:27 -0500
Date: Sun, 3 Apr 2022 19:54:18 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<0fb8f03a-6589-4fc2-81b6-4fc86667442dn@googlegroups.com>
<D6edneV9g7navtf_nZ2dnUU7_83NnZ2d@giganews.com>
<1ce913ac-a7df-49ed-928f-1570ccdd01b0n@googlegroups.com>
<n72dnaa_RMs0rdf_nZ2dnUU7_81QAAAA@giganews.com> <87v8vpafdz.fsf@bsb.me.uk>
<1cudnR2RZsSyq9f_nZ2dnUU7_8xh4p2d@giganews.com> <87czhxadkg.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87czhxadkg.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <rYKdnZAcHKNe3Nf_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 31
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-4pj6+WB+BvwY6kxtTEZaLI33pX4xjgQ9cyi6VEC550cXYOEkLYN7wr/bdA+sQxKGgiEEap/qkP9/LwV!puzhd2jVtdJC9Yj3uzsq9fW5tjEHVX/z02ShEzgbUZiTEkR+gvALX2ydO/bqxpCdX2hUWxvcjx2k
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2851
 by: olcott - Mon, 4 Apr 2022 00:54 UTC

On 4/3/2022 7:37 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 6:58 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> I will never tolerate the tediousness of encoding TMs, my proof is
>>>> sufficient.
>>> Oh! I thought you were entering into this with an open mind and that
>>> you were prepared to do it properly. Encoding TMs is central to the
>>> halting problem.
>>> Do you want to stop?
>>
>> I will not tolerate TMs that cannot store an ASCII digit as a single
>> tape element.
>
> You can use any symbols you like as the tape alphabet. The ASCII part
> is irrelevant because TMs are defined in terms of the abstract symbols
> and have no interest in what numbers are used by you and me to send
> those symbols across the Internet (or, indeed, what numbers are used
> for them in any context).
>

I just can't tolerate too many tedious steps.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29373&group=comp.theory#29373

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 19:57:59 -0500
Date: Sun, 3 Apr 2022 19:57:50 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <877d85adc8.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 103
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-oaeHbEcziPVu4jIbFoHvP8PjHhHon9v+DsFEKvjOa3WQIeJY2KX6gRVpiCElRz337V40o3EOhJAJdys!5eK/wsFkNCIwN2nYBd+XLW9Hrreo+WzP+cXLt3PjbLnix55RdpXlsKt4N0KHhDFqwe/sku5zv2OU
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 6586
 by: olcott - Mon, 4 Apr 2022 00:57 UTC

On 4/3/2022 7:42 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 7:25 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>>> understanding what this means.
>>>>>>>>>>>
>>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>>
>>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>>
>>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>>
>>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>>> things to iron out first.)
>>>>>>>>>>
>>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>>> Yes through algorithmic compression.
>>>>>>>>
>>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>>>
>>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>>> not numbers.
>>>>>>>
>>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>>> should resolve this? Hint: think encoding.
>>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>>
>>>>>> I want to very thoroughly go through all of the points completely as
>>>>>> efficiently as possible. Because a C function could do this as a pure
>>>>>> function of its ASCII digit sequence inputs by merely examining the
>>>>>> last digits for: {0,2,4,8} we know that E is decidable.
>>>>> It will take longer if you take digressions like this! C is not a
>>>>> complete model of computation. No C function can do the job for any
>>>>> number.
>>>>> Let's stick to TMs. What encoding would you use for a TM decider for
>>>>> this problem? Can you specify it using Linz's notation?
>>>>>
>>>>
>>>> ASCII text digits. No.
>>> ASCII is a red-herring here. It's just a mapping from symbols to
>>> numbers and TM's use symbols so the numbers don't come into it.
>>> Yes, you can use digits to encode the number, but you usually get a more
>>> complicated TM is you use decimal digits. I'm going to ask you to write
>>> the TM E shortly and it's easier if you use either binary or unary.
>>> But that's just friendly advice. I leave it to you to pick what set of
>>> symbols (and their meanings) is to be used to encode the number on the
>>> TMs tape.
>>> What's the hurdle with specifying it? It's going to have this pattern:
>>>
>>> E.q0 ??? ⊦* E.qy if ???
>>> E.q0 ??? ⊦* E.qn otherwise.
>>>
>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>> this out?
>>
>> The whole algorithm is merely checking the last ASCII digit for
>> {0,2,4,6,8}. In binary this would check the last digit for 0. So not
>> too bad even in TM.
>
> It seems you want to skip ahead (and that's fine), but please try to
> specify the TM formally. Then you can write it. After all,
> specification is where the main gap in understanding lies for you.
>

The TM simply skips all input tape elements without a blank until it
hits a blank backs up and tests this blank for zero. Then it
conditionally branches to its accept or reject state.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<871qydabvg.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29374&group=comp.theory#29374

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 02:14:11 +0100
Organization: A noiseless patient Spider
Lines: 118
Message-ID: <871qydabvg.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
<87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
<877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+zp6DNGgQYfmpTVp0k14s9d0ymA5zoTAI="
Cancel-Lock: sha1:NjwWvvmFfuC/o+K6zxi7yQDjH4w=
sha1:iCZ3FW2ssLHLiv9gZzUPNedMFCM=
X-BSB-Auth: 1.ed0599805658e288cfde.20220404021411BST.871qydabvg.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 01:14 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 7:42 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/3/2022 7:25 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>>>> understanding what this means.
>>>>>>>>>>>>
>>>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>>>
>>>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>>>
>>>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>>>
>>>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>>>> things to iron out first.)
>>>>>>>>>>>
>>>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>>>> Yes through algorithmic compression.
>>>>>>>>>
>>>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>>>>
>>>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>>>> not numbers.
>>>>>>>>
>>>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>>>> should resolve this? Hint: think encoding.
>>>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>>>
>>>>>>> I want to very thoroughly go through all of the points completely as
>>>>>>> efficiently as possible. Because a C function could do this as a pure
>>>>>>> function of its ASCII digit sequence inputs by merely examining the
>>>>>>> last digits for: {0,2,4,8} we know that E is decidable.
>>>>>> It will take longer if you take digressions like this! C is not a
>>>>>> complete model of computation. No C function can do the job for any
>>>>>> number.
>>>>>> Let's stick to TMs. What encoding would you use for a TM decider for
>>>>>> this problem? Can you specify it using Linz's notation?
>>>>>>
>>>>>
>>>>> ASCII text digits. No.
>>>> ASCII is a red-herring here. It's just a mapping from symbols to
>>>> numbers and TM's use symbols so the numbers don't come into it.
>>>> Yes, you can use digits to encode the number, but you usually get a more
>>>> complicated TM is you use decimal digits. I'm going to ask you to write
>>>> the TM E shortly and it's easier if you use either binary or unary.
>>>> But that's just friendly advice. I leave it to you to pick what set of
>>>> symbols (and their meanings) is to be used to encode the number on the
>>>> TMs tape.
>>>> What's the hurdle with specifying it? It's going to have this pattern:
>>>>
>>>> E.q0 ??? ⊦* E.qy if ???
>>>> E.q0 ??? ⊦* E.qn otherwise.
>>>>
>>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>>> this out?
>>>
>>> The whole algorithm is merely checking the last ASCII digit for
>>> {0,2,4,6,8}. In binary this would check the last digit for 0. So not
>>> too bad even in TM.
>>
>> It seems you want to skip ahead (and that's fine), but please try to
>> specify the TM formally. Then you can write it. After all,
>> specification is where the main gap in understanding lies for you.
>
> The TM simply skips all input tape elements without a blank until it
> hits a blank backs up and tests this blank for zero. Then it
> conditionally branches to its accept or reject state.

There's an even simpler algorithm if you choose a slightly different
encoding, but that's for later...

The question was about the specification. Maybe the problem is you
don't know that a specification should not be an algorithm? As things
get more complicated you will want to be able to say what strings should
be accepted without having to say exactly what process must be followed.

It might be time to skip ahead because the next exercise is to do the
same for P, a TM that decides if a string encodes a prime number. Can
you think of how to specify that without giving an algorithm?

P.q0 ??? ⊦* P.qy if ???
P.q0 ??? ⊦* P.qn otherwise.

(The three ??? won't all be the same things.) Any idea how to flesh
this out? If you can, you will be able to do it for E very easily too.

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87v8vp8wju.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29375&group=comp.theory#29375

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 02:30:29 +0100
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <87v8vp8wju.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
<87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
<877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>
<871qydabvg.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="26865"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Tas54lEqQC7MjoaKNSCKq/tt+SD8DVG4="
Cancel-Lock: sha1:cW/DKf6aGQIdGgJ0Srd2TrP1lGM=
sha1:9cK17piIDQ82Q/PXUWCop8IMXgs=
X-BSB-Auth: 1.99e144fcf5c4d5a17ea3.20220404023029BST.87v8vp8wju.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 01:30 UTC

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> There's an even simpler algorithm if you choose a slightly different
> encoding, but that's for later...

Aside: this may or may not be true. It depends on the exact
specification, so I am guilty of jumping ahead since E is not yet
specified.

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29376&group=comp.theory#29376

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 21:38:51 -0500
Date: Sun, 3 Apr 2022 21:38:41 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <871qydabvg.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 140
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-dEOxAIotjzg4dzxHGSUlTvSamXOOadx32X59UsilNsADBOWIzU4lkzrPuyp2GvKq0U5yLps2ytTMvYI!vxK+pW5kElfDe5mAYfuSE5rlV7RsQcD1SIjXjOKOFtGjnW4hDyzLcyorp/XZph+Ea08U6oDiVGYC
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 8438
 by: olcott - Mon, 4 Apr 2022 02:38 UTC

On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 7:42 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 4/3/2022 7:25 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 4/3/2022 6:46 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 4/3/2022 5:57 PM, Ben Bacarisse wrote:
>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 4/3/2022 5:07 PM, olcott wrote:
>>>>>>>>>>> On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
>>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The key missing piece in all of these dialogues is 100% perfectly and
>>>>>>>>>>>>>>> exactly does it mean for a halt decider to compute the mapping from
>>>>>>>>>>>>>>> its input finite strings to its own final states on the basis of the
>>>>>>>>>>>>>>> actual behavior actually specified by this finite string pair.
>>>>>>>>>>>>>> You certainly have trouble understanding this so I will repeat my offer
>>>>>>>>>>>>>> to take you through a series of student exercises that I am confident
>>>>>>>>>>>>>> (provided you approach them with an open mind) will lead you to fully
>>>>>>>>>>>>>> understanding what this means.
>>>>>>>>>>>>>
>>>>>>>>>>>>> OK let's give it a shot.
>>>>>>>>>>>>
>>>>>>>>>>>> Great!  Let's start with something that will force a lot of hidden
>>>>>>>>>>>> assumptions to be made explicit.
>>>>>>>>>>>>
>>>>>>>>>>>> Q: Is the set of even numbers decidable?  If so, specify the TM (call it
>>>>>>>>>>>>     E) using Linz's notation (extended if you like).  If not, why not?
>>>>>>>>>>>>
>>>>>>>>>>>> (This may be slow to get started, because there is a lot low-level
>>>>>>>>>>>> things to iron out first.)
>>>>>>>>>>>>
>>>>>>>>>>> That depends on how you define your terms. Any element of the set of
>>>>>>>>>>> integers can be determined to be divisible by 2 with or without a remainder.
>>>>>>>>>>> Can every element of this set be enumerated in finite time?
>>>>>>>>>>> No. Can the set of all even numbers be defined in finite space?
>>>>>>>>>>> Yes through algorithmic compression.
>>>>>>>>>>
>>>>>>>>>> I forgot decidability is merely a membership algorithm, so yes.
>>>>>>>>>
>>>>>>>>> (Didn't see you'd moved on. Ignore my last reply.)
>>>>>>>>> I would say no. And for the reason you keep giving: any TM that decides
>>>>>>>>> membership can't have a number as input. TMs accept or reject strings,
>>>>>>>>> not numbers.
>>>>>>>>>
>>>>>>>>> But surely the iseven(n) function is computable, so how do you think we
>>>>>>>>> should resolve this? Hint: think encoding.
>>>>>>>>> Can you have a stab at specifying E now using Linz's notation?
>>>>>>>>
>>>>>>>> I want to very thoroughly go through all of the points completely as
>>>>>>>> efficiently as possible. Because a C function could do this as a pure
>>>>>>>> function of its ASCII digit sequence inputs by merely examining the
>>>>>>>> last digits for: {0,2,4,8} we know that E is decidable.
>>>>>>> It will take longer if you take digressions like this! C is not a
>>>>>>> complete model of computation. No C function can do the job for any
>>>>>>> number.
>>>>>>> Let's stick to TMs. What encoding would you use for a TM decider for
>>>>>>> this problem? Can you specify it using Linz's notation?
>>>>>>>
>>>>>>
>>>>>> ASCII text digits. No.
>>>>> ASCII is a red-herring here. It's just a mapping from symbols to
>>>>> numbers and TM's use symbols so the numbers don't come into it.
>>>>> Yes, you can use digits to encode the number, but you usually get a more
>>>>> complicated TM is you use decimal digits. I'm going to ask you to write
>>>>> the TM E shortly and it's easier if you use either binary or unary.
>>>>> But that's just friendly advice. I leave it to you to pick what set of
>>>>> symbols (and their meanings) is to be used to encode the number on the
>>>>> TMs tape.
>>>>> What's the hurdle with specifying it? It's going to have this pattern:
>>>>>
>>>>> E.q0 ??? ⊦* E.qy if ???
>>>>> E.q0 ??? ⊦* E.qn otherwise.
>>>>>
>>>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>>>> this out?
>>>>
>>>> The whole algorithm is merely checking the last ASCII digit for
>>>> {0,2,4,6,8}. In binary this would check the last digit for 0. So not
>>>> too bad even in TM.
>>>
>>> It seems you want to skip ahead (and that's fine), but please try to
>>> specify the TM formally. Then you can write it. After all,
>>> specification is where the main gap in understanding lies for you.
>>
>> The TM simply skips all input tape elements without a blank until it
>> hits a blank backs up and tests this blank for zero. Then it
>> conditionally branches to its accept or reject state.
>
> There's an even simpler algorithm if you choose a slightly different
> encoding, but that's for later...
>
> The question was about the specification. Maybe the problem is you
> don't know that a specification should not be an algorithm? As things
> get more complicated you will want to be able to say what strings should
> be accepted without having to say exactly what process must be followed.
>

A specification can be a many different levels of abstraction from a
very broad goal: I want to implement a fully functional human mind in
software that can exactly duplicate every single detail of the
functional end result of human mind. All the way down to complete source
code that will compile and execute correctly.

This also includes everything inbetween. A specification is an
implementation map that guides every step. This seems best when the map
is inbetween multiple layers of abstraction of progressive layers of
detail.

> It might be time to skip ahead because the next exercise is to do the
> same for P, a TM that decides if a string encodes a prime number. Can
> you think of how to specify that without giving an algorithm?
>
> P.q0 ??? ⊦* P.qy if ???
> P.q0 ??? ⊦* P.qn otherwise.
>
> (The three ??? won't all be the same things.) Any idea how to flesh
> this out? If you can, you will be able to do it for E very easily too.
>

P.q0 S ⊦* P.qy if Is-Prime-Number(S)
P.q0 S ⊦* P.qn otherwise.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<t2dp8l$edu$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29377&group=comp.theory#29377

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Date: Sun, 3 Apr 2022 21:38:59 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 30
Message-ID: <t2dp8l$edu$1@dont-email.me>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 4 Apr 2022 03:39:01 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="f79bfa4594b7ce730cc216529e8ee278";
logging-data="14782"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/L62E2z9lREDCNoj5fJdJ2"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
Cancel-Lock: sha1:2+VwWssxKaRMO/35A0AbjEHQEnk=
In-Reply-To: <r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Mon, 4 Apr 2022 03:38 UTC

On 2022-04-03 20:38, olcott wrote:
> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:

>> It might be time to skip ahead because the next exercise is to do the
>> same for P, a TM that decides if a string encodes a prime number.  Can
>> you think of how to specify that without giving an algorithm?
>>
>>      P.q0 ??? ⊦* P.qy    if ???
>>      P.q0 ??? ⊦* P.qn    otherwise.
>>
>> (The three ??? won't all be the same things.)  Any idea how to flesh
>> this out?  If you can, you will be able to do it for E very easily too.
>>
>
> P.q0 S ⊦* P.qy    if Is-Prime-Number(S)
> P.q0 S ⊦* P.qn    otherwise.

You'll want to write out your condition without referring to some
undefined pseudofunction. The above isn't interpretable unless you also
provide some specification for Is-Prime-Number(). You may think this is
self-explanatory based on the name you've chosen, but it really is not
for reasons which will become apparent once you see the point Ben is
getting at. [I'll leave that point to Ben]

André

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

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29378&group=comp.theory#29378

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 22:57:20 -0500
Date: Sun, 3 Apr 2022 22:57:11 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <t2dp8l$edu$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t2dp8l$edu$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 46
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-KR5U3vg2uwysWvW0iWou+AocssvfPJ487dsSdrYSK32kPeSq01PaKunOHVbVrdQn4JGZ3F4gYdkovxo!Ms4qg/wqIlh6yM9aYFJWb0a9Z1pFpyG4QjRbWCv1umpxQqJKWhEU0+sW1pnhikNaGG1F6pdipmqd
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3554
 by: olcott - Mon, 4 Apr 2022 03:57 UTC

On 4/3/2022 10:38 PM, André G. Isaak wrote:
> On 2022-04-03 20:38, olcott wrote:
>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>
>>> It might be time to skip ahead because the next exercise is to do the
>>> same for P, a TM that decides if a string encodes a prime number.  Can
>>> you think of how to specify that without giving an algorithm?
>>>
>>>      P.q0 ??? ⊦* P.qy    if ???
>>>      P.q0 ??? ⊦* P.qn    otherwise.
>>>
>>> (The three ??? won't all be the same things.)  Any idea how to flesh
>>> this out?  If you can, you will be able to do it for E very easily too.
>>>
>>
>> P.q0 S ⊦* P.qy    if Is-Prime-Number(S)
>> P.q0 S ⊦* P.qn    otherwise.
>
> You'll want to write out your condition without referring to some
> undefined pseudofunction. The above isn't interpretable unless you also
> provide some specification for Is-Prime-Number(). You may think this is

On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
> It might be time to skip ahead because the next exercise is to do the
> same for P, a TM that decides if a string encodes a prime number. Can
> you think of how to specify that without giving an algorithm?

specify that without giving an algorithm?
specify that without giving an algorithm?
specify that without giving an algorithm?

> self-explanatory based on the name you've chosen, but it really is not
> for reasons which will become apparent once you see the point Ben is
> getting at. [I'll leave that point to Ben]
>
> André
>
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<t2drs1$i05$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29379&group=comp.theory#29379

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Date: Sun, 3 Apr 2022 22:23:29 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 50
Message-ID: <t2drs1$i05$1@dont-email.me>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <t2dp8l$edu$1@dont-email.me>
<Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 4 Apr 2022 04:23:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="f79bfa4594b7ce730cc216529e8ee278";
logging-data="18437"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ClWVSVnTCJWfAc/5GV67i"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
Cancel-Lock: sha1:polvhd5J9Jv1ZngZi/dDVeHJOLQ=
In-Reply-To: <Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Mon, 4 Apr 2022 04:23 UTC

On 2022-04-03 21:57, olcott wrote:
> On 4/3/2022 10:38 PM, André G. Isaak wrote:
>> On 2022-04-03 20:38, olcott wrote:
>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>
>>>> It might be time to skip ahead because the next exercise is to do the
>>>> same for P, a TM that decides if a string encodes a prime number.  Can
>>>> you think of how to specify that without giving an algorithm?
>>>>
>>>>      P.q0 ??? ⊦* P.qy    if ???
>>>>      P.q0 ??? ⊦* P.qn    otherwise.
>>>>
>>>> (The three ??? won't all be the same things.)  Any idea how to flesh
>>>> this out?  If you can, you will be able to do it for E very easily too.
>>>>
>>>
>>> P.q0 S ⊦* P.qy    if Is-Prime-Number(S)
>>> P.q0 S ⊦* P.qn    otherwise.
>>
>> You'll want to write out your condition without referring to some
>> undefined pseudofunction. The above isn't interpretable unless you
>> also provide some specification for Is-Prime-Number(). You may think
>> this is
>
> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
> > It might be time to skip ahead because the next exercise is to do the
> > same for P, a TM that decides if a string encodes a prime number.  Can
> > you think of how to specify that without giving an algorithm?
>
> specify that without giving an algorithm?
> specify that without giving an algorithm?
> specify that without giving an algorithm?
>
>> self-explanatory based on the name you've chosen, but it really is not
>> for reasons which will become apparent once you see the point Ben is
>> getting at. [I'll leave that point to Ben]

I think you are missing my point. I didn't say you needed to provide an
algorithm for Is-Prime-Number(). I said you needed to provide a
*specification* for this if you want to use it.

What I am suggesting is that you rewrite your condition in English
rather than pseudo-code.

André

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

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<KvOdnWCDJMRa69f_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29380&group=comp.theory#29380

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 03 Apr 2022 23:40:39 -0500
Date: Sun, 3 Apr 2022 23:40:29 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <t2dp8l$edu$1@dont-email.me>
<Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com> <t2drs1$i05$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t2drs1$i05$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <KvOdnWCDJMRa69f_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 63
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-4Sfe2rCUWEQ3ZAo4lSau+9dUVPqu60CXJmzbFQnt0BmGaJ/u+SE7ZdsTnHbJltc5B0B0knqEXioFkkU!BbYPVEWlBKJoPD9zuxMhGQyRLJlxvSrVfmvmS9RK88jpTnXISQrs3tTRNscXtBU0xzksH4lmBq/H
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4393
 by: olcott - Mon, 4 Apr 2022 04:40 UTC

On 4/3/2022 11:23 PM, André G. Isaak wrote:
> On 2022-04-03 21:57, olcott wrote:
>> On 4/3/2022 10:38 PM, André G. Isaak wrote:
>>> On 2022-04-03 20:38, olcott wrote:
>>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>>
>>>>> It might be time to skip ahead because the next exercise is to do the
>>>>> same for P, a TM that decides if a string encodes a prime number.  Can
>>>>> you think of how to specify that without giving an algorithm?
>>>>>
>>>>>      P.q0 ??? ⊦* P.qy    if ???
>>>>>      P.q0 ??? ⊦* P.qn    otherwise.
>>>>>
>>>>> (The three ??? won't all be the same things.)  Any idea how to flesh
>>>>> this out?  If you can, you will be able to do it for E very easily
>>>>> too.
>>>>>
>>>>
>>>> P.q0 S ⊦* P.qy    if Is-Prime-Number(S)
>>>> P.q0 S ⊦* P.qn    otherwise.
>>>
>>> You'll want to write out your condition without referring to some
>>> undefined pseudofunction. The above isn't interpretable unless you
>>> also provide some specification for Is-Prime-Number(). You may think
>>> this is
>>
>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>  > It might be time to skip ahead because the next exercise is to do the
>>  > same for P, a TM that decides if a string encodes a prime number.  Can
>>  > you think of how to specify that without giving an algorithm?
>>
>> specify that without giving an algorithm?
>> specify that without giving an algorithm?
>> specify that without giving an algorithm?
>>
>>> self-explanatory based on the name you've chosen, but it really is
>>> not for reasons which will become apparent once you see the point Ben
>>> is getting at. [I'll leave that point to Ben]
>
> I think you are missing my point. I didn't say you needed to provide an
> algorithm for Is-Prime-Number(). I said you needed to provide a
> *specification* for this if you want to use it.
>

Any greater degree of specification than the function name requires some
degree of algorithm. The function name is the most abstract way to
specify it. All of the precise coding is the most specific way and
everything inbetween has a degree of algorithm.

> What I am suggesting is that you rewrite your condition in English
> rather than pseudo-code.
>
> André

They are equivalent.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<t2duc6$gh$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29381&group=comp.theory#29381

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Date: Sun, 3 Apr 2022 23:06:13 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 79
Message-ID: <t2duc6$gh$1@dont-email.me>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <t2dp8l$edu$1@dont-email.me>
<Dq-dnY9GF9Y98df_nZ2dnUU7_8zNnZ2d@giganews.com> <t2drs1$i05$1@dont-email.me>
<KvOdnWCDJMRa69f_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 4 Apr 2022 05:06:14 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="f79bfa4594b7ce730cc216529e8ee278";
logging-data="529"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18OdnEstDlXRXB8yZB1tKcb"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
Cancel-Lock: sha1:/1/oq9HkkDLZg/i4o86CSGhVy5A=
In-Reply-To: <KvOdnWCDJMRa69f_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Mon, 4 Apr 2022 05:06 UTC

On 2022-04-03 22:40, olcott wrote:
> On 4/3/2022 11:23 PM, André G. Isaak wrote:
>> On 2022-04-03 21:57, olcott wrote:
>>> On 4/3/2022 10:38 PM, André G. Isaak wrote:
>>>> On 2022-04-03 20:38, olcott wrote:
>>>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>>>
>>>>>> It might be time to skip ahead because the next exercise is to do the
>>>>>> same for P, a TM that decides if a string encodes a prime number.
>>>>>> Can
>>>>>> you think of how to specify that without giving an algorithm?
>>>>>>
>>>>>>      P.q0 ??? ⊦* P.qy    if ???
>>>>>>      P.q0 ??? ⊦* P.qn    otherwise.
>>>>>>
>>>>>> (The three ??? won't all be the same things.)  Any idea how to flesh
>>>>>> this out?  If you can, you will be able to do it for E very easily
>>>>>> too.
>>>>>>
>>>>>
>>>>> P.q0 S ⊦* P.qy    if Is-Prime-Number(S)
>>>>> P.q0 S ⊦* P.qn    otherwise.
>>>>
>>>> You'll want to write out your condition without referring to some
>>>> undefined pseudofunction. The above isn't interpretable unless you
>>>> also provide some specification for Is-Prime-Number(). You may think
>>>> this is
>>>
>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>>  > It might be time to skip ahead because the next exercise is to do the
>>>  > same for P, a TM that decides if a string encodes a prime number.
>>> Can
>>>  > you think of how to specify that without giving an algorithm?
>>>
>>> specify that without giving an algorithm?
>>> specify that without giving an algorithm?
>>> specify that without giving an algorithm?
>>>
>>>> self-explanatory based on the name you've chosen, but it really is
>>>> not for reasons which will become apparent once you see the point
>>>> Ben is getting at. [I'll leave that point to Ben]
>>
>> I think you are missing my point. I didn't say you needed to provide
>> an algorithm for Is-Prime-Number(). I said you needed to provide a
>> *specification* for this if you want to use it.
>>
>
> Any greater degree of specification than the function name requires some
> degree of algorithm. The function name is the most abstract way to
> specify it. All of the precise coding is the most specific way and
> everything inbetween has a degree of algorithm.

Again, I think you are missing my point. I may come back and explain it
to you after Ben gets to the next step in his exercises.

>> What I am suggesting is that you rewrite your condition in English
>> rather than pseudo-code.
>>
>> André
>
> They are equivalent.

Then why not simply humor me and provide a version where the condition
is written out in English?

It will turn out they really are not equivalent, but I don't want to get
ahead of Ben by explicating this further here. The difference will
become apparent.

In general it's best to avoid pseudo-technical looking things for which
you have provided no definition since the whole point of technical terms
is that they have a very precise definition. English is always
preferable to some undefined 'formalism'.

André

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

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87ee2d88a6.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29382&group=comp.theory#29382

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 11:14:41 +0100
Organization: A noiseless patient Spider
Lines: 31
Message-ID: <87ee2d88a6.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
<87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
<877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>
<871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="19972"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+5/GetDzVq21TIoo2DQbZUkPkeogi/jgo="
Cancel-Lock: sha1:9s+H8myiIkR7Wg4u2VbEiyv3YHo=
sha1:ImcPiDZq3cJ5p27sHRQ1QKtks+w=
X-BSB-Auth: 1.9825944f162d62a031d2.20220404111441BST.87ee2d88a6.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 10:14 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:

>> It might be time to skip ahead because the next exercise is to do the
>> same for P, a TM that decides if a string encodes a prime number. Can
>> you think of how to specify that without giving an algorithm?
>> P.q0 ??? ⊦* P.qy if ???
>> P.q0 ??? ⊦* P.qn otherwise.
>> (The three ??? won't all be the same things.) Any idea how to flesh
>> this out? If you can, you will be able to do it for E very easily too.
>
> P.q0 S ⊦* P.qy if Is-Prime-Number(S)
> P.q0 S ⊦* P.qn otherwise.

That's getting close. We know, from how the notation works, that S is a
string of symbols in the TM's alphabet. But writing Is-Prime-Number(S)
suggests that is not natural language. That's a very hard route to go
down. I'd have to ask you for the definition of Is-Prime-Number.
Defining it symbolically is messy and if the definition is /not/ formal,
dressing the definition up with a formal-looking name is just
superficial.

I only wanted a clear and unambiguous statement of what must be the case
for P to accept S.

(I see there is already a side thread. I won't get involved but you can
count on André not to lead you astray.)

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<t2eghp$5n3$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29383&group=comp.theory#29383

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!wvONfgmCjpyJD8XieLz90w.user.46.165.242.75.POSTED!not-for-mail
From: anw...@cuboid.co.uk (Andy Walker)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Date: Mon, 4 Apr 2022 11:16:23 +0100
Organization: Not very much
Message-ID: <t2eghp$5n3$1@gioia.aioe.org>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="5859"; posting-host="wvONfgmCjpyJD8XieLz90w.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
X-Notice: Filtered by postfilter v. 0.9.2
Content-Language: en-GB
 by: Andy Walker - Mon, 4 Apr 2022 10:16 UTC

On 04/04/2022 00:46, Ben Bacarisse wrote:
> [...] C is not a
> complete model of computation. No C function can do the job for any
> number.

I think this is a little [OK, quite a lottle] unfair, for two
reasons:

-- Although C's arithmetic is limited by things like the size of an
"int", it is easy to imagine an extended C in which, if you like
as an abstraction, arbitrarily-large [and extensible] integer
types are available, in which arbitrarily much storage can be
used, and so on. There is nothing "interesting" to separate a
TM from such an abstracted C, and very little to separate an
abstract C from an actual C.

-- As I have pointed out occasionally here and elsewhere when people
have wittered on about a TM having an infinite tape, what we really
need is an arbitrarily-extensible tape. That can be achieved by a
stack of USB sticks with instructions such as "load next/previous
stick", as long as you are prepared from time to time to go to the
shop and buy some more, and as long as the entire universe doesn't
run out. IRL, "infinity" is never that large! It's often less
than ten. [In theory C programs can't match brackets; in practice
they can.]

The reasons why it's not possible to write a halt decider show
up perfectly well if you try to do so in K&R C for a PDP 11 [64K bytes
code, same for date, 2.4M discs, ...]. They're not things that can
only be done with supercomputers with hundreds of processors, etc.
These interminable threads get hung up on the behaviour of programs of
less than a page of code.

If I thought there was likely ever to be real progress, I
personally would be as happy to see it in the form of a C program as
in the formal description of some TM. Whether something is or isn't
a Real Computation [TM] is just a diversion.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Dussek

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<597901c3-9c40-4bc6-9d23-eb110458bc62n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29384&group=comp.theory#29384

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a0c:f649:0:b0:443:da6c:4297 with SMTP id s9-20020a0cf649000000b00443da6c4297mr2383625qvm.71.1649069372594;
Mon, 04 Apr 2022 03:49:32 -0700 (PDT)
X-Received: by 2002:a81:a10b:0:b0:2eb:736b:6fb4 with SMTP id
y11-20020a81a10b000000b002eb736b6fb4mr2243969ywg.161.1649069372439; Mon, 04
Apr 2022 03:49:32 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 4 Apr 2022 03:49:32 -0700 (PDT)
In-Reply-To: <t2eghp$5n3$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:ace5:144c:9716:be60;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:ace5:144c:9716:be60
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk> <t2eghp$5n3$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <597901c3-9c40-4bc6-9d23-eb110458bc62n@googlegroups.com>
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Mon, 04 Apr 2022 10:49:32 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 47
 by: Malcolm McLean - Mon, 4 Apr 2022 10:49 UTC

On Monday, 4 April 2022 at 11:16:27 UTC+1, Andy Walker wrote:
> On 04/04/2022 00:46, Ben Bacarisse wrote:
> > [...] C is not a
> > complete model of computation. No C function can do the job for any
> > number.
> I think this is a little [OK, quite a lottle] unfair, for two
> reasons:
>
> -- Although C's arithmetic is limited by things like the size of an
> "int", it is easy to imagine an extended C in which, if you like
> as an abstraction, arbitrarily-large [and extensible] integer
> types are available, in which arbitrarily much storage can be
> used, and so on. There is nothing "interesting" to separate a
> TM from such an abstracted C, and very little to separate an
> abstract C from an actual C.
>
> -- As I have pointed out occasionally here and elsewhere when people
> have wittered on about a TM having an infinite tape, what we really
> need is an arbitrarily-extensible tape. That can be achieved by a
> stack of USB sticks with instructions such as "load next/previous
> stick", as long as you are prepared from time to time to go to the
> shop and buy some more, and as long as the entire universe doesn't
> run out. IRL, "infinity" is never that large! It's often less
> than ten. [In theory C programs can't match brackets; in practice
> they can.]
>
> The reasons why it's not possible to write a halt decider show
> up perfectly well if you try to do so in K&R C for a PDP 11 [64K bytes
> code, same for date, 2.4M discs, ...]. They're not things that can
> only be done with supercomputers with hundreds of processors, etc.
> These interminable threads get hung up on the behaviour of programs of
> less than a page of code.
>
> If I thought there was likely ever to be real progress, I
> personally would be as happy to see it in the form of a C program as
> in the formal description of some TM. Whether something is or isn't
> a Real Computation [TM] is just a diversion.
>
The task is to write a Turing machine which decides the ininite set of
natural numbers, separating them into even and odd.
To write a C function which does the job for numbers up to those
that can be represented by the widest integer type is trivial. Even to
extend to numbers that will fit into the computer's memory is quite
simple.
To support numbers up to any size, you have to have a system of
swapping in and out smart drives. So essentially you're writing a
Turing machine in C. It's far easier just to write the Turing machine in
some accepted notation. And that's the job.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<t2elc9$gsl$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29385&group=comp.theory#29385

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!wvONfgmCjpyJD8XieLz90w.user.46.165.242.75.POSTED!not-for-mail
From: anw...@cuboid.co.uk (Andy Walker)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Date: Mon, 4 Apr 2022 12:38:49 +0100
Organization: Not very much
Message-ID: <t2elc9$gsl$1@gioia.aioe.org>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<t2eghp$5n3$1@gioia.aioe.org>
<597901c3-9c40-4bc6-9d23-eb110458bc62n@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="17301"; posting-host="wvONfgmCjpyJD8XieLz90w.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Content-Language: en-GB
X-Notice: Filtered by postfilter v. 0.9.2
 by: Andy Walker - Mon, 4 Apr 2022 11:38 UTC

On 04/04/2022 11:49, Malcolm McLean wrote:
> The task is to write a Turing machine which decides the ininite set of
> natural numbers, separating them into even and odd.
> To write a C function which does the job for numbers up to those
> that can be represented by the widest integer type is trivial. Even to
> extend to numbers that will fit into the computer's memory is quite
> simple.

Yes; for trivial tasks, it matters little whether you write in
TM language or C or any other language; and yes, you can boast that
"your" program can cope with numbers up to [humungous] without change
but "his" program can't. For the theory, that may be important.

> To support numbers up to any size, you have to have a system of
> swapping in and out smart drives. So essentially you're writing a
> Turing machine in C. It's far easier just to write the Turing machine in
> some accepted notation. And that's the job.

Once you have a C compiler available, then writing procedures
to "load next/previous drive" is something to do once and then invoke
as needed. It's writing the C compiler that is a lot of work. But
work that's already been done. If you actually want to run your TM
program, then someone has to write a TM compiler; that too has been
done. After that, writing a very simple TM program to test whether
the input has an odd or an even number of 1's before you hit a blank
is much the same difficulty as writing a C program to do the same.
That rapidly changes as tasks get more complex. No-one writes [eg]
payroll programs as TM state transitions. No-one any longer writes
them in assembler either. There are reasons for that!

I understand that this is a theory group and there are reasons
why CS theory is often framed in terms of what TMs can/cannot do. I
also understand that Ben is engaged in the [IMO hopeless] task of
trying to educate PO, and that "odd/even" is a simple task suited to
TMs. It was the side-line of "C isn't suitable" that I took [limited]
exception to.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Dussek

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<8735it7zaj.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29386&group=comp.theory#29386

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 14:28:52 +0100
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <8735it7zaj.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk> <t2eghp$5n3$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="10573"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX189SiCMz2Pthc+1aHs5+VQWAJuq//vAPPQ="
Cancel-Lock: sha1:plTC7vjnduvtfj16Zjdlp07sWXQ=
sha1:+kL4G/p+DFNx9pOrLMe/x0dxYJM=
X-BSB-Auth: 1.4fa800edfe599ffca14e.20220404142852BST.8735it7zaj.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 13:28 UTC

Andy Walker <anw@cuboid.co.uk> writes:

> On 04/04/2022 00:46, Ben Bacarisse wrote:
>> [...] C is not a
>> complete model of computation. No C function can do the job for any
>> number.
>
> I think this is a little [OK, quite a lottle] unfair, for two
> reasons:
>
> -- Although C's arithmetic is limited by things like the size of an
> "int", it is easy to imagine an extended C in which, if you like
> as an abstraction, arbitrarily-large [and extensible] integer
> types are available, in which arbitrarily much storage can be
> used, and so on. There is nothing "interesting" to separate a
> TM from such an abstracted C, and very little to separate an
> abstract C from an actual C.

I agree, but that sort of broad-brush abstract reasoning is dangerous in
PO's case.

In fact I suggested this way back in ... don't know ... but he insisted
on talking about real C.

The other problem with using C is that the representation issue can get
messy. That's why the Lisp family of languages is so good for this --
see Chaitin.

> -- As I have pointed out occasionally here and elsewhere when people
> have wittered on about a TM having an infinite tape, what we really
> need is an arbitrarily-extensible tape.

My preferred term is "unbounded".

> That can be achieved by a
> stack of USB sticks with instructions such as "load next/previous
> stick", as long as you are prepared from time to time to go to the
> shop and buy some more, and as long as the entire universe doesn't
> run out. IRL, "infinity" is never that large! It's often less
> than ten. [In theory C programs can't match brackets; in practice
> they can.]

Again, perfectly reasonable when broad-brush generalisations won't cause
an intellectual melt-down, but C can't do IO to specific devices so to
make this concrete, you have to have an OS as well.

> The reasons why it's not possible to write a halt decider show
> up perfectly well if you try to do so in K&R C for a PDP 11 [64K bytes
> code, same for date, 2.4M discs, ...]. They're not things that can
> only be done with supercomputers with hundreds of processors, etc.
> These interminable threads get hung up on the behaviour of programs of
> less than a page of code.

Now here there is technical wrinkle. One can, probably, prove that
halting of bounded-resource computations can't be solved by certain
similarly bounded-resource machines. But who'd want to do the maths to
prove that? And if the decider has unbounded resources, then halting of
bounded-resource computations /is/ decidable -- trivially so.

> If I thought there was likely ever to be real progress, I
> personally would be as happy to see it in the form of a C program as
> in the formal description of some TM. Whether something is or isn't
> a Real Computation [TM] is just a diversion.

When trying to get PO to see how to specify a computation, I don't want
to deal with all the distractions that using some abstract C with no
pointer limitations will throw up.

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<w_WdndouypjXZtf_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29387&group=comp.theory#29387

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 04 Apr 2022 09:06:02 -0500
Date: Mon, 4 Apr 2022 09:05:52 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <87ee2d88a6.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87ee2d88a6.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <w_WdndouypjXZtf_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 44
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-OODLTKzMablvlqtJaLbHUPc2IJjIkhHpijd64VhCS4OpzGiTJ23LLdQSBO2RZKDXi1dX1QOyxKQFuMP!7am+yoyvDe5bbXgWpWx4UrXaxQRoafU75Hzeboqd2bkGJRwFlDlY3+O+PuNjH+GiXCfvtOCxdgN6
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3546
 by: olcott - Mon, 4 Apr 2022 14:05 UTC

On 4/4/2022 5:14 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>
>>> It might be time to skip ahead because the next exercise is to do the
>>> same for P, a TM that decides if a string encodes a prime number. Can
>>> you think of how to specify that without giving an algorithm?
>>> P.q0 ??? ⊦* P.qy if ???
>>> P.q0 ??? ⊦* P.qn otherwise.
>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>> this out? If you can, you will be able to do it for E very easily too.
>>
>> P.q0 S ⊦* P.qy if Is-Prime-Number(S)
>> P.q0 S ⊦* P.qn otherwise.
>
> That's getting close. We know, from how the notation works, that S is a
> string of symbols in the TM's alphabet. But writing Is-Prime-Number(S)
> suggests that is not natural language. That's a very hard route to go
> down. I'd have to ask you for the definition of Is-Prime-Number.
> Defining it symbolically is messy and if the definition is /not/ formal,
> dressing the definition up with a formal-looking name is just
> superficial.
>

It goes through some tedious steps to see if it is a prime number:

A prime number is a natural number greater than 1 that is not a product
of two smaller natural numbers.

> I only wanted a clear and unambiguous statement of what must be the case
> for P to accept S.
>
> (I see there is already a side thread. I won't get involved but you can
> count on André not to lead you astray.)
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<Me2dnYzz6q0YYdf_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29388&group=comp.theory#29388

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 04 Apr 2022 09:11:17 -0500
Date: Mon, 4 Apr 2022 09:11:07 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<t2eghp$5n3$1@gioia.aioe.org>
<597901c3-9c40-4bc6-9d23-eb110458bc62n@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <597901c3-9c40-4bc6-9d23-eb110458bc62n@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <Me2dnYzz6q0YYdf_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 61
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-DqSkK4gqwBFMP+H47GY9O4Y33oTh8vSvopDFOXk5JZF2qlIK39eiDOzy+5vj4tU4mXHFQsxxpk2KUv5!ix+72YAVEQ4vrsO1BVEKhWTTBriy8K6m8OPTh3DHPbKVN0PuT7QP7yCZ3r3iHq4zEbG2gtyKDCCa
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4615
 by: olcott - Mon, 4 Apr 2022 14:11 UTC

On 4/4/2022 5:49 AM, Malcolm McLean wrote:
> On Monday, 4 April 2022 at 11:16:27 UTC+1, Andy Walker wrote:
>> On 04/04/2022 00:46, Ben Bacarisse wrote:
>>> [...] C is not a
>>> complete model of computation. No C function can do the job for any
>>> number.
>> I think this is a little [OK, quite a lottle] unfair, for two
>> reasons:
>>
>> -- Although C's arithmetic is limited by things like the size of an
>> "int", it is easy to imagine an extended C in which, if you like
>> as an abstraction, arbitrarily-large [and extensible] integer
>> types are available, in which arbitrarily much storage can be
>> used, and so on. There is nothing "interesting" to separate a
>> TM from such an abstracted C, and very little to separate an
>> abstract C from an actual C.
>>
>> -- As I have pointed out occasionally here and elsewhere when people
>> have wittered on about a TM having an infinite tape, what we really
>> need is an arbitrarily-extensible tape. That can be achieved by a
>> stack of USB sticks with instructions such as "load next/previous
>> stick", as long as you are prepared from time to time to go to the
>> shop and buy some more, and as long as the entire universe doesn't
>> run out. IRL, "infinity" is never that large! It's often less
>> than ten. [In theory C programs can't match brackets; in practice
>> they can.]
>>
>> The reasons why it's not possible to write a halt decider show
>> up perfectly well if you try to do so in K&R C for a PDP 11 [64K bytes
>> code, same for date, 2.4M discs, ...]. They're not things that can
>> only be done with supercomputers with hundreds of processors, etc.
>> These interminable threads get hung up on the behaviour of programs of
>> less than a page of code.
>>
>> If I thought there was likely ever to be real progress, I
>> personally would be as happy to see it in the form of a C program as
>> in the formal description of some TM. Whether something is or isn't
>> a Real Computation [TM] is just a diversion.
>>
> The task is to write a Turing machine which decides the ininite set of
> natural numbers, separating them into even and odd.
> To write a C function which does the job for numbers up to those
> that can be represented by the widest integer type is trivial. Even to
> extend to numbers that will fit into the computer's memory is quite
> simple.
> To support numbers up to any size, you have to have a system of
> swapping in and out smart drives. So essentially you're writing a
> Turing machine in C. It's far easier just to write the Turing machine in
> some accepted notation. And that's the job.

None of this crap ever gets into computability thus is mere a
distraction. If it is computable then the lack of unlimited size almost
never changes this.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<87tub87tkd.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29391&group=comp.theory#29391

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]
Date: Mon, 04 Apr 2022 16:32:34 +0100
Organization: A noiseless patient Spider
Lines: 49
Message-ID: <87tub87tkd.fsf@bsb.me.uk>
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk>
<VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk>
<w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com>
<87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com>
<877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com>
<87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com>
<877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com>
<871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com>
<87ee2d88a6.fsf@bsb.me.uk>
<w_WdndouypjXZtf_nZ2dnUU7_8zNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="5af9218b468646d7ac639d07a487e562";
logging-data="11536"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18km417w5EPI4SGuO1lY3yP1qAaHpaFNFw="
Cancel-Lock: sha1:SY+gAB7ug3nvp3UmEGSCYfChlRE=
sha1:EHUPLppgrKSklG1TSK5nKl/ttkU=
X-BSB-Auth: 1.6953d82d17294655cf63.20220404163234BST.87tub87tkd.fsf@bsb.me.uk
 by: Ben Bacarisse - Mon, 4 Apr 2022 15:32 UTC

olcott <NoOne@NoWhere.com> writes:

> On 4/4/2022 5:14 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>
>>>> It might be time to skip ahead because the next exercise is to do the
>>>> same for P, a TM that decides if a string encodes a prime number. Can
>>>> you think of how to specify that without giving an algorithm?
>>>> P.q0 ??? ⊦* P.qy if ???
>>>> P.q0 ??? ⊦* P.qn otherwise.
>>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>>> this out? If you can, you will be able to do it for E very easily too.
>>>
>>> P.q0 S ⊦* P.qy if Is-Prime-Number(S)
>>> P.q0 S ⊦* P.qn otherwise.
>> That's getting close. We know, from how the notation works, that S is a
>> string of symbols in the TM's alphabet. But writing Is-Prime-Number(S)
>> suggests that is not natural language. That's a very hard route to go
>> down. I'd have to ask you for the definition of Is-Prime-Number.
>> Defining it symbolically is messy and if the definition is /not/ formal,
>> dressing the definition up with a formal-looking name is just
>> superficial.
>
> It goes through some tedious steps to see if it is a prime number:
>
> A prime number is a natural number greater than 1 that is not a
> product of two smaller natural numbers.

We've hit a bit of a road-block rather sooner that I had expected.
First off, there's no need to define what a prime number is. If at some
point it turns out that your readers do not know, go ahead and define
it, but it's too widely understood by comp.theory readers to bother
about.

But writing (as I think you are suggesting)

P.q0 S ⊦* P.qy it goes through some tedious steps to see if it is a
prime number

is not really adequate. There are two 'it'. To what do they refer?
and nothing in P.q0 S ⊦* P.qy is a number so there is nothing there to
be a prime number.

Can you see how you (a) make it shorter, (b) make it clearer?

--
Ben.

Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [ key missing piece in dialogue ]

<lMednU9oMbfWidb_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=29392&group=comp.theory#29392

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 04 Apr 2022 10:52:43 -0500
Date: Mon, 4 Apr 2022 10:52:33 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Subject: Re: Refuting the Peter Linz Halting Problem Proof --- Version(10) [
key missing piece in dialogue ]
Content-Language: en-US
Newsgroups: comp.theory
References: <v6idnaCJifSVTtT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87sfquc7ns.fsf@bsb.me.uk> <VMSdneUyrJVin9f_nZ2dnUU7_83NnZ2d@giganews.com>
<871qydde5e.fsf@bsb.me.uk> <w-edndUxIuQ1h9f_nZ2dnUU7_83NnZ2d@giganews.com>
<w-edndQxIuTUhtf_nZ2dnUU7_81g4p2d@giganews.com> <87ilrpbwrt.fsf@bsb.me.uk>
<n72dnae_RMuWrdf_nZ2dnUU7_83NnZ2d@giganews.com> <877d85buic.fsf@bsb.me.uk>
<1cudneORZsT2qNf_nZ2dnUU7_8zNnZ2d@giganews.com> <87mth1ae3z.fsf@bsb.me.uk>
<RJCdnVAp-PNjodf_nZ2dnUU7_8zNnZ2d@giganews.com> <877d85adc8.fsf@bsb.me.uk>
<uLKdnSnsBawK39f_nZ2dnUU7_8zNnZ2d@giganews.com> <871qydabvg.fsf@bsb.me.uk>
<r9ydndF_Xuemx9f_nZ2dnUU7_8zNnZ2d@giganews.com> <87ee2d88a6.fsf@bsb.me.uk>
<w_WdndouypjXZtf_nZ2dnUU7_8zNnZ2d@giganews.com> <87tub87tkd.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87tub87tkd.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <lMednU9oMbfWidb_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 63
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-BeBSvEkLuAAsuckY94yQg53tbHKyHc0I4xrGDYoce5smRrEFPoQV6dqa41ddkTlW1iqLUIvdAmmc86q!abKQhQl+epl8ghn0QyBCfaUMyzgWQer9FFYdSXzNJlTDdWvFMWWxW64GF2pF4vi6cqigdHdR5kjs
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4485
 by: olcott - Mon, 4 Apr 2022 15:52 UTC

On 4/4/2022 10:32 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 4/4/2022 5:14 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 4/3/2022 8:14 PM, Ben Bacarisse wrote:
>>>
>>>>> It might be time to skip ahead because the next exercise is to do the
>>>>> same for P, a TM that decides if a string encodes a prime number. Can
>>>>> you think of how to specify that without giving an algorithm?
>>>>> P.q0 ??? ⊦* P.qy if ???
>>>>> P.q0 ??? ⊦* P.qn otherwise.
>>>>> (The three ??? won't all be the same things.) Any idea how to flesh
>>>>> this out? If you can, you will be able to do it for E very easily too.
>>>>
>>>> P.q0 S ⊦* P.qy if Is-Prime-Number(S)
>>>> P.q0 S ⊦* P.qn otherwise.
>>> That's getting close. We know, from how the notation works, that S is a
>>> string of symbols in the TM's alphabet. But writing Is-Prime-Number(S)
>>> suggests that is not natural language. That's a very hard route to go
>>> down. I'd have to ask you for the definition of Is-Prime-Number.
>>> Defining it symbolically is messy and if the definition is /not/ formal,
>>> dressing the definition up with a formal-looking name is just
>>> superficial.
>>
>> It goes through some tedious steps to see if it is a prime number:
>>
>> A prime number is a natural number greater than 1 that is not a
>> product of two smaller natural numbers.
>
> We've hit a bit of a road-block rather sooner that I had expected.
> First off, there's no need to define what a prime number is. If at some
> point it turns out that your readers do not know, go ahead and define
> it, but it's too widely understood by comp.theory readers to bother
> about.
>
> But writing (as I think you are suggesting)
>
> P.q0 S ⊦* P.qy it goes through some tedious steps to see if it is a
> prime number
>
> is not really adequate. There are two 'it'. To what do they refer?

You told me to make sure that I do not provide an algorithm.

This is somewhat algorithmic:
The TM examines its tape to determine of the sequence of adjacent tape
elements corresponds to a representation of a prime number.

> and nothing in P.q0 S ⊦* P.qy is a number so there is nothing there to
> be a prime number.
>
> Can you see how you (a) make it shorter, (b) make it clearer?
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Pages:12345678910111213141516171819202122232425262728293031323334353637383940
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor