Re: bart again (UCX64)

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: bart again (UCX64)
Date	2023-09-06 19:57 +0100
Organization	A noiseless patient Spider
Message-ID	<875y4nqgdv.fsf@bsb.me.uk> (permalink)
References	(16 earlier) <ud60pq$1mf0p$1@dont-email.me> <20230904234329.835@kylheku.com> <86bkegpztj.fsf@linuxsc.com> <20230905075103.116@kylheku.com> <86o7ifnw0g.fsf@linuxsc.com>

Show all headers | View raw

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.

>>> 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.  Most authors will
invent a notation for a configuration (often a pictorial one) to help in
explanations.

-- 
Ben.

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) Bart <bc@freeuk.com> - 2023-09-05 12:51 +0100

csiph-web