Groups > comp.theory > #119086

Re: How to write a self-referencial TM?

Path	csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From	Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups	comp.theory
Subject	Re: How to write a self-referencial TM?
Date	Wed, 14 May 2025 13:49:03 -0700
Organization	None to speak of
Lines	37
Message-ID	<87ldqyapfk.fsf@nosuchdomain.example.com> (permalink)
References	<1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com> <1002akp$2i4bk$2@dont-email.me> <479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com> <1002j0r$2k04b$1@dont-email.me> <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> <1002tma$2k04c$5@dont-email.me>
MIME-Version	1.0
Content-Type	text/plain
Injection-Date	Wed, 14 May 2025 22:49:03 +0200 (CEST)
Injection-Info	dont-email.me; posting-host="28f21fc31a5e376fbb703380c9354ddd"; logging-data="2799377"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+ZT/YIxPqUKV6gbmwU+8Ao"
User-Agent	Gnus/5.13 (Gnus v5.13)
Cancel-Lock	sha1:+J7dY46eOVnONls3sCNuzE1E6as= sha1:4NcMX9B4aIZrt09yZLPWxMRlMiA=
Xref	csiph.com comp.theory:119086

Show key headers only | View raw

Richard Heathfield <rjh@cpax.org.uk> writes:
> On 14/05/2025 21:00, Keith Thompson wrote:
> <snip>
>
>> I presume that one-way and two-way infinite tapes are computationally
>> equivalent, so the distinction doesn't matter all that much.
>> (Though with a one-way tape, I'm not sure what happens if the TM
>> runs off the end of the tape.)
>
> I should imagine that you could build one hell of a stack on one-way
> tape.
>
> Of course, the tape doesn't /have/ to be infinite. It only has to be
> long enough so that you /don't/ run off the end. Just how long that is
> depends on what problem you're addressing.
>
> In the Real World, tapes can't be infinite, so an implementor has to
> decide how long 'long enough' is.

TM's don't necessarily operate in the Real World.

> If the TM's alphabet consisted of 256 discrete symbols (no reason why
> not) a megabyte would give you a disk-based 'tape' a million cells
> long.
>
> Ought to be enough for `take one down and pass it around'.

Sure.  "Infinite tape" might be more precisely expressed as
"sufficient tape".  But a TM that advances in one direction along
the tape in a loop will require more than any finite length of tape
if you leave it running long enough, though the amount of tape it
consumes in any finite number of steps is still finite.  For that
kind of TM in particular, "infinite tape" is a convenient shorthand.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

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