Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!ccu.umanitoba.ca!herald.usask.ca!alberta!ubc-cs!uw-beaver!zephyr.ens.tek.com!uunet!shelby!agate!pasteur!aspen.Berkeley.EDU!boyland
From: boyland@aspen.Berkeley.EDU (John B. Boyland)
Newsgroups: comp.lang.misc
Subject: Re: Turing equivalence (was first-class composable functions)
Keywords: infinite tape, sophistry
Message-ID: <11077@pasteur.Berkeley.EDU>
Date: 13 Feb 91 19:25:58 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu> <320@smds.UUCP> <926@creatures.cs.vt.edu>
Sender: news@pasteur.Berkeley.EDU
Reply-To: boyland@sequoia.Berkeley.EDU (John B. Boyland)
Followup-To: comp.lang.misc
Lines: 23

In article <926@creatures.cs.vt.edu>, lavinus@csgrad.cs.vt.edu writes:
|> A Turing machine, by definition, has an infinite tape.  Therefore, no
computer
|> in existence can simulate a "real" Turing machine, dynamic allocation
or not.
|> What a real-life computer CAN simulate is a Linear Bounded Automata, i.e.,
|> a Turing machine with a finite tape.  [...]

And, now, my two cents:

A Turing machine during some time period t, never uses more than kt units of
tape, where 'k' depends on the speed of the Turing machine.  Thus in a finite
time, a Turing machine always is limited within a finite section of tape.
As long as the machine runs slow enough, one could splice on new reels of tape
on the tape being used on a REAL machine (assuming this real machine had a
bidirectional tape reader/writer).   So, basically, one could run any Turing
program.  Of course, the operator may decide to interrupt computation (because
funding is dropped, or whatever), but assuming the current model of Big Crunch,
where the universe has a limited "lifetime", it is theoretically possible to
build a Turing machine which never runs out of tape.

John Boyland
boyland@sequoia.Berkeley.EDU