Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #119086
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: How to write a self-referencial TM? |
| Date | 2025-05-14 13:49 -0700 |
| Organization | None to speak of |
| Message-ID | <87ldqyapfk.fsf@nosuchdomain.example.com> (permalink) |
| References | (5 earlier) <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> |
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 */
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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