Annals of OS and network history

From: Doug Yowza <yowza_at_yowza.com>
Date: Tue Mar 10 13:02:33 1998

On Tue, 10 Mar 1998, Allison J Parent wrote:

>
> <Nobody has ever made a Turing machine (it's that nasty infinitely long
> <tape that keeps getting in the way)
>
> Yes I know but it has been done. Back when shift registers were commonly
> available with lengths of 1024 bits it was very trivial to string a few
> and get really long serial memory. With moden megabit rams it's not that
> much more difficult. The tape was not so much the problem but the
> programing...

It's been a long time since I've looked at a CS book, but I remember the
Turing machine as a *theoretical* machine that reads and writes symbols on
an *infinitely long* tape. I'm sure somebody could build an approximation
of this, but the main interest in the Turing machine is that it is used
as the definition of computational "power." One of theories is that no
machine built today, or at any time in the future, no matter what the
architecture, will be able to compute anything that a simple Turing
machine cannot compute..

I think that's basically a long-winded way of saying that all computing
machines are state machines, and the Turing machine was basically a device
that helped visualize the mechanical realization of a state machine. Once
you actually build one, however, the "tape" is no longer infinitely long,
so the machine suddenly has limited computational power, and the theorem
no longer applies.

-- Doug
Received on Tue Mar 10 1998 - 13:02:33 GMT