Path: utzoo!utgpu!news-server.csri.toronto.edu!csri.toronto.edu!norvell
Newsgroups: comp.lang.misc
From: norvell@csri.toronto.edu (Theo Norvell)
Subject: Re: Turing equivalence (was first-class composable functions)
Message-ID: <1991Feb13.181137.26189@jarvis.csri.toronto.edu>
Organization: CSRI, University of Toronto
References: <1991Feb7.150537.9257@spool.cs.wisc.edu> <1991Feb11.164821.10486@spool.cs.wisc.edu> <320@smds.UUCP> <926@creatures.cs.vt.edu>
Date: 13 Feb 91 23:11:37 GMT
Lines: 29

In article <926@creatures.cs.vt.edu> lavinus@csgrad.cs.vt.edu () writes:
>Well, I guess I'll throw my two cents' worth into this whole Turing machine
>debate:
>
>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.

What do you mean by "finite"?  All tapes are always finite.  It's just that
Turing machine tapes grow as is needed.  If you mean a constant size tape,
you are talking about Finite State Automata, not LBAs..

A Linear Bounded Automaton is a Turing machine with a tape that is linear in the
size of the input. I fail to see why this is any easier in principle to simulate
than one that uses an amount of tape that is some other kind of finite function
of the input size.  In other words, why do you pick _Linear_ Bounded Automata,
rather than, say, Quadratic Bounded Automata?

The tricky kind of Turing machines are those that might run for ever using
more and more tape.  Of course this includes all universal Turing machines,
but few other interesting functions.

One can imagine a physical machine that just keeps asking for more and more
tape (real machines do request tapes).  Eventually the universe might run out
of the raw materials to manufacture the tape, but by that time people
will probably have lost interest in the problem.

Theo Norvell