Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!crdgw1!rpi!bu.edu!m2c!umvlsi!dime!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: comp.lang.misc
Subject: Re: Turing equivalence (was first-class composable functions)
Keywords: infinite tape, sophistry
Message-ID: <26788@dime.cs.umass.edu>
Date: 16 Feb 91 16:35:56 GMT
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu> <320@smds.UUCP> <926@creatures.cs.vt.edu> <11077@pasteur.Berkeley.EDU>
Sender: news@dime.cs.umass.edu
Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Organization: University of Massachusetts, Amherst
Lines: 26

In article <11077@pasteur.Berkeley.EDU> boyland@sequoia.Berkeley.EDU (John B. Boyland) writes:
>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

This is a time-honored argument, but requires radical redefinition of
"computer". If the operation of your "computer" depends on actions of the
operator, then the operator is part of the computer. I'm perfectly
willing to admit that a human being combined with a finite mechanical
computing device may not be a finite state machine. But, if we limit our
attention to digital computing devices that occupy finite space, we are
within the realm of finite state machines, not turing machines.