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

Groups > comp.lang.c > #174253

Re: bart again (UCX64)

Show all headers | 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