Groups > comp.theory > #119135

Re: How to write a self-referencial TM?

From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: How to write a self-referencial TM?
Date	2025-05-15 00:55 +0100
Organization	A noiseless patient Spider
Message-ID	<87frh6lpbv.fsf@bsb.me.uk> (permalink)
References	(4 earlier) <3b177909de383fcf209cfb9ff81fe2f118640578.camel@gmail.com> <1002l44$2k04b$3@dont-email.me> <8c7a8437e78a5b798cc23d77a8e1b6080e59ab0e.camel@gmail.com> <1002nvo$2k04b$5@dont-email.me> <87plgb9d4i.fsf@nosuchdomain.example.com>

Show all headers | View raw

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> Richard Heathfield <rjh@cpax.org.uk> writes:
> [...]
>> See <https://plato.stanford.edu/entries/turing-machine/>
>>
>> where you can read this:
>>
>> "A Turing machine then, or a computing machine as Turing called it, in
>> Turing’s original definition is a machine capable of a finite set of
>> configurations q1,…,qn (the states of the machine, called
>> m-configurations by Turing). It is supplied with a one-way infinite
>> and one-dimensional tape divided into squares each capable of carrying
>> exactly one symbol. At any moment, the machine is scanning the content
>> of one square r which is either blank (symbolized by S0) or contains a
>> symbol S1,…,Sm with S1=0 and S2=1."
>>
>> There's more to TMs than tapes.
> [...]
>
> Interesting.  The phrase "one-way infinite" implies that the tape
> is infinite in only one direction, so the cells can be indexed by
> non-negative integers.  Elsewhere on that web page, it acknowledges
> that there are variations in Turing machines, including one-way
> vs. two-way infinite tapes.  It's implied that Turings original
> concept had a one-way infinite tape.  I wasn't able to confirm or
> deny that in a very quick look through Turings original paper.

I don't think it's explicit, but the paper does refer to input being "on
the beginning" of the tape.

> I've always assumed that a TM tape is two-way infinite.

That is by far the more usual presentation these days.  A lot about
Turing's presentation has been tidied up over the years.

> I presume that one-way and two-way infinite tapes are computationally
> equivalent, so the distinction doesn't matter all that much.

Yes.  That's often presented as an "exercise to the reader".  There are
also multi-tape TMs, non-deterministic TMs and random TMs that can
access a tape of randomly chosen symbols.

> (Though with a one-way tape, I'm not sure what happens if the TM
> runs off the end of the tape.)

The usual presentation just says that TM stops if the action can't be
taken.  It need be no different to what happens if the state transition
function does not include the current state/input pair in its domain.

-- 
Ben.

Thread

How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-14 13:13 +0800
  Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 07:02 +0100
  Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 09:51 -0500
    Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 00:43 +0800
      Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 18:14 +0100
        Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:33 +0800
          Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 18:49 +0100
            Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 02:01 +0800
              Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 19:38 +0100
                Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 13:00 -0700
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 15:02 -0500
                Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 21:19 +0100
                Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 21:16 +0100
                Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 13:49 -0700
                Re: How to write a self-referencial TM? Mr Flibble <flibble@red-dwarf.jmc.corp> - 2025-05-14 21:13 +0000
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:24 +0300
                Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 22:28 +0100
                Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 14:40 -0700
                Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 23:02 +0100
                Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-15 01:09 +0100
                Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 17:19 -0700
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 09:38 +0800
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 09:58 +0800
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 10:11 +0800
                Re: How to write a self-referencial TM? Ben Bacarisse <ben@bsb.me.uk> - 2025-05-15 00:55 +0100
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:17 +0300
      Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 12:24 -0500
        Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:39 +0800
          Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 12:45 -0500
            Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 02:13 +0800
        Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:53 +0800
          Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-15 17:08 +0100
            Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 11:47 -0500
              Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 03:57 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 15:50 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:33 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:43 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 12:10 -0400
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-17 11:58 +0300
              Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-15 19:37 -0400
              Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:27 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:40 -0500
                Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-19 10:21 +0200
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:39 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:41 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 11:47 +0300
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-21 07:11 -0400
            Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 02:49 +0800
              Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 14:15 -0500
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 04:08 +0800
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:45 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:47 -0500
                Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-16 21:34 +0200
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:40 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:44 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-17 12:02 +0300
              Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 01:40 +0100
                Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-16 01:59 +0100
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 09:47 +0800
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 03:26 +0100
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 19:40 +0800
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 16:33 +0100
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 03:35 +0800
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 23:51 +0100
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:01 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:12 -0500
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:23 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:40 -0500
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:49 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:58 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-17 09:02 -0400
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-17 15:45 +0100
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-18 03:26 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-17 14:39 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-18 11:20 +0300
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 04:35 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 15:57 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 17:45 -0400
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 05:46 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 17:09 -0500
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 06:35 +0800
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 19:09 -0400
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 07:54 +0800
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:52 +0300
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:48 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:36 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 11:56 +0300
                Re: How to write a self-referencial TM? André G. Isaak <agisaak@gm.invalid> - 2025-05-18 15:58 -0600
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 17:08 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 19:19 -0400
                Re: How to write a self-referencial TM? André G. Isaak <agisaak@gm.invalid> - 2025-05-18 21:21 -0600
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 23:07 -0500
                Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-19 09:54 +0200
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 15:29 +0300
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:33 -0500
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 12:03 +0300
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-21 07:16 -0400
                Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-21 21:43 +0200
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-21 14:49 -0500
                Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-23 13:03 +0200
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:44 +0300
                Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:41 +0300
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-17 20:46 +0100
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-17 14:55 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-17 16:07 -0400
                Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-16 12:22 +0100
                Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 16:57 +0100
                Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-16 21:04 +0100
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 15:38 -0500
                Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 05:21 +0800
                Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 16:40 -0500
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 20:32 -0400
                Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 17:59 -0400
        Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:24 +0300
          Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:37 -0500
  Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:07 +0300

csiph-web