Re: bart again (UCX64)

Path	csiph.com!weretis.net!feeder8.news.weretis.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c
Subject	Re: bart again (UCX64)
Date	Wed, 06 Sep 2023 19:01:25 -0700
Organization	A noiseless patient Spider
Lines	56
Message-ID	<867cp2oi6i.fsf@linuxsc.com> (permalink)
References	<b74c088d-09e6-4842-8b6c-1921d68154c7n@googlegroups.com> <ucs9pb$3nd9i$1@dont-email.me> <ucsg9u$3ofr6$1@dont-email.me> <ucsk81$3p2kg$1@dont-email.me> <ucsm1u$3pb1c$1@dont-email.me> <871qfiknil.fsf@bsb.me.uk> <ucsu3s$3qfrk$1@dont-email.me> <87v8ctkbsj.fsf@bsb.me.uk> <uctaf3$3v98j$1@dont-email.me> <87pm31jusi.fsf@bsb.me.uk> <ucuvtc$cbnk$1@dont-email.me> <5JHIM.574995$qnnb.462524@fx11.iad> <ucvk6s$f6nb$1@dont-email.me> <r1JIM.297958$uLJb.27694@fx41.iad> <ucvuhq$gmlg$1@dont-email.me> <ud60pq$1mf0p$1@dont-email.me> <20230904234329.835@kylheku.com> <86bkegpztj.fsf@linuxsc.com> <20230905075103.116@kylheku.com> <86o7ifnw0g.fsf@linuxsc.com> <875y4nqgdv.fsf@bsb.me.uk>
MIME-Version	1.0
Content-Type	text/plain; charset=us-ascii
Injection-Info	dont-email.me; posting-host="28fb28ff8f70d848737d53d65ae3a64e"; logging-data="2991116"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX193nmXfHvNp5iG5+IgihEZ5Nn35Hufc+pQ="
User-Agent	Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock	sha1:fmm9vK6bqKOA8iDyrInQnwqG7jY= sha1:5y/DmCaiHsNtbBRiLYOGorApass=
Xref	csiph.com comp.lang.c:174253

Show key headers only | View raw

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

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>>
>>> On 2023-09-05, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>>>>
>>>>> A Turing machine is completely defined and has no run-time
>>>>> inputs;  everything is on the tape.
>>>>
>>>> This is wrong.  A Turing machine is just the machine.  The tape
>>>> is separate.
>>>
>>> Apologies for that.  A term for what I'm referring to is
>>> "Turing machine configuration" (offered in _Introduction to the
>>> Theory of Computation_, 3rd ed, Michael Sipser).
>>
>> Not a term I'm familiar with.  Seems like a poor choice
>> of phrase.
>
> It's quite widely used but not exactly as Kaz seems to be
> suggesting.  Siper uses it in the way I've seen other authors use
> it:
>
>   "As a Turing machine computes, changes occur in the current
>   state, the current tape contents, and the current head location.
>   A setting of these three items is called a configuration of the
>   Turing machine."
>
> A TM configuration represents the state of a computation.

I see.  That makes more sense.  I still think the name is a
little funny, but at least I see the point of the concept.

>>>> It would be pointless to talk about "Turing machines"
>>>> if all a given "Turing machine" could do is one computation.
>>>
>>> "Does this Turing machine configuration halt?" is a
>>> meaningful question.
>>
>> The question usually asked is "Does a given Turing machine halt
>> when started on a blank tape?".  Given a Turing machine T and
>> input tape I, it's easy to construct a Turing machine T' such
>> that T' halts when started on a blank tape if and only iff T
>> halts when started on I.  ISTM that the notion of a Turing
>> machine configuration (whether by that name or a different one)
>> isn't very useful.
>
> True, but given the way it is actually defined it is very
> useful as a way to talk about the progress of a computation.
> [...]

Yes.  Thank you for the clarification.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: bart again (UCX64) vallor <vallor@cultnix.org> - 2023-09-05 01:38 +0000
  Re: bart again (UCX64) Richard Damon <Richard@Damon-Family.org> - 2023-09-04 20:05 -0700
    Re: bart again (UCX64) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-09-06 16:45 -0700
  Re: bart again (UCX64) Kaz Kylheku <864-117-4973@kylheku.com> - 2023-09-05 06:49 +0000
    Re: bart again (UCX64) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-09-05 05:30 -0700
      Re: bart again (UCX64) Kaz Kylheku <864-117-4973@kylheku.com> - 2023-09-05 17:16 +0000
        Re: bart again (UCX64) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-09-06 08:47 -0700
          Re: bart again (UCX64) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-09-06 19:57 +0100
            Re: bart again (UCX64) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-09-06 19:01 -0700
    Re: bart again (UCX64) James Kuyper <jameskuyper@alumni.caltech.edu> - 2023-09-09 01:14 -0400
      Re: bart again (UCX64) Kaz Kylheku <864-117-4973@kylheku.com> - 2023-09-09 05:22 +0000
  Re: bart again (UCX64) Bart <bc@freeuk.com> - 2023-09-05 12:51 +0100

csiph-web