Re: bart again (UCX64)

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c
Subject	Re: bart again (UCX64)
Date	2023-09-06 08:47 -0700
Organization	A noiseless patient Spider
Message-ID	<86o7ifnw0g.fsf@linuxsc.com> (permalink)
References	(16 earlier) <ucvuhq$gmlg$1@dont-email.me> <ud60pq$1mf0p$1@dont-email.me> <20230904234329.835@kylheku.com> <86bkegpztj.fsf@linuxsc.com> <20230905075103.116@kylheku.com>

Show all headers | View raw

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 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.

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

Thread

Re: bart again (UCX64) Richard Damon <Richard@Damon-Family.org> - 2023-09-02 09:03 -0700
  Re: bart again (UCX64) Bart <bc@freeuk.com> - 2023-09-02 19:22 +0100
    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