Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

turing machine...who cares?

1 view
Skip to first unread message

Ralph Silverman

unread,
Apr 26, 1996, 3:00:00 AM4/26/96
to

the turing machine was rather fully
defined
<1942
and
reasonably,
electronic binary digital computer(s)
postdates this time...

now,
it is the
electronic binary digital computer
that has become so ubiquitous,
not the
turing machine...
though there may not be universal agreement
regarding the essential nature of the computers
we do, actually, have...
frequently these are represented as being
vonneumann machine(s)
.
why is it not more interesting to study the kind
of
computers
we have, actually,
than the kind
we do not
?

--

Ralph Silverman
z007...@bcfreenet.seflin.lib.fl.us


Patrick Juola

unread,
Apr 27, 1996, 3:00:00 AM4/27/96
to

Mr. Silverman, your naivety is starting to astonish me. All computers
that we are able to build can be shown to be at best equivalent in
computational abilities to Turing machines -- and furthermore, any
reasonably intelligent design produces something that, given infinite
memory, would be exactly equivalent to a Turing machine. So the direct
answer to your question is that, we *do* study the kind of computers
we have -- they're Turing machines.

More generally, I suggest that you find and read a copy of Hopcroft
and Ullman's _Theory of Automata and Languages_ since most of the
questions you've been posing recently are quite well answered therein.

Patrick

Ralph Silverman

unread,
Apr 29, 1996, 3:00:00 AM4/29/96
to

Patrick Juola (pat...@gryphon.psych.ox.ac.uk) wrote:

: Patrick

--
************begin r.s. response*************

right now i program on
an antiquated
COMPAQ model 2551
286 12
.
even regarding this, now,
modest capability system...
there never has been a
turing machine
made
"...equivalent in computational abilities..."
to it.

also,
if
the interpretation of what a
turing machine
is...
is a
non-finite machine
then
it is very different than
the ones we so customarily use!!!!!!!!!!!!!


************end r.s. response***************
Ralph Silverman
z007...@bcfreenet.seflin.lib.fl.us


Patrick Juola

unread,
Apr 29, 1996, 3:00:00 AM4/29/96
to

In article <4m2hri$m...@nntp.seflin.lib.fl.us> z007...@bcfreenet.seflin.lib.fl.us (Ralph Silverman) writes:
right now i program on an antiquated COMPAQ model 2551 286 12 .
even regarding this, now, modest capability system...
there never has been a turing machine made
"...equivalent in computational abilities..." to it.

You're half right. Formally, a Turing machine has infinite memory, which
precludes its being physically made. Informally, any program that runs
on your '286 will run w/o modification on a "Random Access Machine", which
can be mechanistically converted into a TM program. See Hopcroft and Ullman
for details.

Patrick

Ralph Silverman

unread,
Apr 30, 1996, 3:00:00 AM4/30/96
to

Patrick Juola (pat...@gryphon.psych.ox.ac.uk) wrote:

: Patrick

--
*************begin r.s. response**************

turing's machine
is an abstraction of computer systems
that predates the computer systems
we have...
and actually,
resembles them little!
why embrace this antiquated and
peculiar
abstraction now?

for example...
normally,
actual computers
are routinely expected to support
generalized arithmetic division operations.
there is reason to believe that no
algorithym for this on turing's machine
has been published and proven valid!!!
a period of time
>50 years
has passed since turing's paper published...
is it not getting a little late?
and
is there any responsible opinion that
turing's machine
is a effective basis for the study of
algorithyms
now
???

*************end r.s. response****************
Ralph Silverman
z007...@bcfreenet.seflin.lib.fl.us


Gary William Flake

unread,
Apr 30, 1996, 3:00:00 AM4/30/96
to

In article <4m55bj$5...@nntp.seflin.lib.fl.us>,

Ralph Silverman <z007...@bcfreenet.seflin.lib.fl.us> wrote:
>
> turing's machine
> is an abstraction of computer systems
> that predates the computer systems
> we have...

True.

> and actually,
> resembles them little!

True on a superficial level. False if you consider that they compute
the same functions.

> why embrace this antiquated and
> peculiar
> abstraction now?

For the same reason that biologists study fruit flies. If you want to
make a profound statement about computers, it should apply to all
computers, not just one particular model. You could base all of your
analysis on a Cray, but the fact that Turing machines (along with
lambda calculus, general recursive functions, and lisp) are simple
makes it easier to prove general statements that apply to all
computers.

> for example...
> normally,
> actual computers
> are routinely expected to support
> generalized arithmetic division operations.
> there is reason to believe that no
> algorithym for this on turing's machine
> has been published and proven valid!!!
> a period of time

This is patently false. For example, it is not too difficult to prove
that a random access machine and a Turing machine are equal in
computing power. Take your favorite division algorithm that runs on a
random access machine, and use the emulation algorithm from the proof
as a subroutine. Voila.

Better yet, use a simplified version of lisp and represent integers as
unary lists, and rationals by two integers. For fun you can write a
square root operation. It may take a year to finish, but it is
amazing that it can be done with little more than the cons, cdr, and
car operators.

> >50 years
> has passed since turing's paper published...
> is it not getting a little late?
> and
> is there any responsible opinion that
> turing's machine
> is a effective basis for the study of
> algorithyms
> now
> ???

Listen. No one is suggesting that a Turing machine be built. As an
applied device a TM would be very cumbersome. But as a theoretical
device it is tremendously useful. Why? Primarily because it is so
simple. But more importantly, a TM as a model of computation is
universal. Pick your favorite program that runs on your home PC. If
it runs in time f(n), where n is the input length, then there exists a
TM that runs th same program in time g(f(n)), where g() is a
polynomial (and, therefore, well-behaved). This means that the two
models of computation are for the most part "equivalent" in processing
speed as well.

I hope this clarifies things for you.

>Ralph Silverman
>z007...@bcfreenet.seflin.lib.fl.us

--
Gary W. Flake, Ph.D., fl...@scr.siemens.com, Vox:609-734-3676, Fax:609-734-6565
Project Manager and MTS, Adaptive Information and Signal Processing Department
Siemens Corporate Research, 755 College Road East, Princeton, NJ 08540, USA

Ralph Silverman

unread,
Apr 30, 1996, 3:00:00 AM4/30/96
to

From bl...@ai.uiuc.edu Tue Apr 30 15:17:02 1996
Date: Mon, 29 Apr 1996 15:42:33 -0500
From: Gunnar Blix <bl...@ai.uiuc.edu>
To: z007...@bcfreenet.seflin.lib.fl.us
Newsgroups: comp.ai.philosophy,comp.ai,comp.ai.alife
Subject: Re: turing machine...who cares? 2

Please keep this crap out of comp.ai, as you clearly have no clue what
you are writing about, and as you clearly don't read comp.ai, and as
this is repeat of previously expressed opinion that does not
contribute. I also doubt that the other AI newsgroups are interested.

- Gunnar

In comp.ai you write:

> turing's paper was published in
> 1938
> however,
> the ideas were kicking around
> english academic circles before then...
> by
> 1939
> this reached
> bell telephone laboratories
> where a group was developing automated binary
> arithmetic systems for actual, practical,
> calculations...
> the features of turing's proposal regarding
> arithmetic operations
> were studied with great interest there and,
> on review, were viewed to be comedic...

> in fairness...
> reasonably,
> turing himself, would not have proposed these
> for a practical system...
> this not withstanding...
> turing's machine was of little practical...
> or theoretical interest...
> by
> 1940
> in advanced groups advancing such development!


>--

>Ralph Silverman
>z007...@bcfreenet.seflin.lib.fl.us

--
Gunnar Blix bl...@cs.uiuc.edu
University of Illinois http://www-ilg.ai.uiuc.edu/~blix/

Nothing so ridiculous but some philosopher has said it. -- Cicero

--

Ralph Silverman
z007...@bcfreenet.seflin.lib.fl.us


Patrick Juola

unread,
Apr 30, 1996, 3:00:00 AM4/30/96
to

In article <4m55bj$5...@nntp.seflin.lib.fl.us> z007...@bcfreenet.seflin.lib.fl.us (Ralph Silverman) writes:
> turing's machine
> is an abstraction of computer systems
> that predates the computer systems
> we have...
> and actually,
> resembles them little!

In other words, "I didn't bother to read either your article or the
references therein."

Mr. Silverman, using words of only one syllable (except for "Turing"
and "machine") :

I can prove that a Turing machine does the same things that
a "modern" machine does. I can prove that a modern machine does the
same thing that a Turing machine does.

They are the same.

What you say for one, you say for both.

Patrick

Randolph M. Jones

unread,
May 1, 1996, 3:00:00 AM5/1/96
to

Patrick Juola wrote:
> I can prove that a Turing machine does the same things that
> a "modern" machine does. I can prove that a modern machine does the
> same thing that a Turing machine does.

Hmmm...I guess I'd really like to see that proof. Which commercially
available computer with unlimited memory are you going to use in your
proof?

Patrick Juola

unread,
May 1, 1996, 3:00:00 AM5/1/96
to

Smartass. I couldn't use the word "memory" in the paragraph above because
it has three syllables.

In direct answer to your question, it's fairly easy to prove that
problems solvable in polynomial space on TM-equivalent machine are
solvable in poly-space in any TM-equivalent. (Hopcroft and Ullman, 1969,
cited in Garey and Johnson, 1979). So a proof that a program is
solvable in polyspace on a TM is proof that it's solvable on a modern
computer and vice versa.

Patrick

Greg Sidebottom

unread,
May 1, 1996, 3:00:00 AM5/1/96
to

In article <31870D...@eecs.umich.edu>,

Randolph M. Jones <rjo...@eecs.umich.edu> wrote:
>Patrick Juola wrote:
>> I can prove that a Turing machine does the same things that
>> a "modern" machine does. I can prove that a modern machine does the
>> same thing that a Turing machine does.
>
>Hmmm...I guess I'd really like to see that proof. Which commercially
>available computer with unlimited memory are you going to use in your
>proof?

The fact that a Turing machine is defined to have an infinite tape is
irrelevant with respect to the functions it can compute. This is
because any terminating computation can only use a finite part of the
tape. So a Turing machine cannot compute any functions that a finite
computer (whith large enough memory) cannot.

All Turing machine programs which use unbounded tape for a given input
compute a function which is undefined for that input. A finite
computer need only go into an infinite loop for those inputs to
compute the same function.

The reason why we need to define Turing machines with infinite tape is
so that they model all computers we could ever build. Though any
particular computer we build is finite, we like to prove things about
all computers we could ever build, assuming we can build bigger and
bigger ones without bound. I won't get into whether that assumption is
reasonable...

Greg

Bob Riemenschneider

unread,
May 2, 1996, 3:00:00 AM5/2/96
to

In article <4m7qam$8...@bcarh8ab.bnr.ca> gr...@bnr.ca (Greg Sidebottom) writes:

> The fact that a Turing machine is defined to have an infinite tape is
> irrelevant with respect to the functions it can compute. This is
> because any terminating computation can only use a finite part of the
> tape. So a Turing machine cannot compute any functions that a finite
> computer (whith large enough memory) cannot.

Actually, you've mixed up the order of a couple of quantifiers here. No
finite physical computer can compute any total function from N to N -- the
identity function, for example -- because all but a finite number of
inputs are too large for the computer to deal with. By increasing the
machine's resources, we can make the smallest input the computer can't
handle larger, but there is always a limit. So, for any f: N -> N and any
computer C, there is an n such that C cannot compute f(n), although -- as
you note -- for every f, there is no n such that no C can compute f(n)
(assuming unbounded resources). Thus Turing machines can do things no
finite physical computer can, like compute all of the identity function,
and some idealization is involved in applying recursion theory to actual
computing. You can either assume that an infinite supply of tape -- or
SCSI disks -- are available (to connected on demand so that only a finite
number are actually being used at any given time, if you prefer, but
that's still an infinite computer) or simply say that you're taking a
limit.

-- rar

Randolph M. Jones

unread,
May 3, 1996, 3:00:00 AM5/3/96
to

Patrick Juola wrote:
>
> In article <31870D...@eecs.umich.edu> "Randolph M. Jones" <rjo...@eecs.umich.edu> writes:
> >Patrick Juola wrote:
> >> I can prove that a Turing machine does the same things that
> >> a "modern" machine does. I can prove that a modern machine does the
> >> same thing that a Turing machine does.
> >
> >Hmmm...I guess I'd really like to see that proof. Which commercially
> >available computer with unlimited memory are you going to use in your
> >proof?
>
> Smartass.

Be that as it may, I was not being entirely facetious when I
challenged the idea that you could create such a proof.

> I couldn't use the word "memory" in the paragraph above because
> it has three syllables.
>
> In direct answer to your question, it's fairly easy to prove that
> problems solvable in polynomial space on TM-equivalent machine are
> solvable in poly-space in any TM-equivalent. (Hopcroft and Ullman, 1969,
> cited in Garey and Johnson, 1979).

I'm with you so far...

> So a proof that a program is
> solvable in polyspace on a TM is proof that it's solvable on a modern
> computer and vice versa.

It is this leap that "a modern computer" is somehow equivalent to
"any TM-equivalent" that I challenge. This would have to be the
key part of your proof.

Randolph M. Jones

unread,
May 3, 1996, 3:00:00 AM5/3/96
to

Greg Sidebottom wrote:
>
> In article <31870D...@eecs.umich.edu>,
> Randolph M. Jones <rjo...@eecs.umich.edu> wrote:
> >Patrick Juola wrote:
> >> I can prove that a Turing machine does the same things that
> >> a "modern" machine does. I can prove that a modern machine does the
> >> same thing that a Turing machine does.
> >
> >Hmmm...I guess I'd really like to see that proof. Which commercially
> >available computer with unlimited memory are you going to use in your
> >proof?
>
> The fact that a Turing machine is defined to have an infinite tape is
> irrelevant with respect to the functions it can compute. This is
> because any terminating computation can only use a finite part of the
> tape. So a Turing machine cannot compute any functions that a finite
> computer (whith large enough memory) cannot.

I did not say that the computer had to have infinite memory, I said
that it would have to have unlimited memory, and that is *entirely*
relevant to setting apart a Turing machine from a finite state
automaton. Although only a finite amount of the tape is ever used,
there is *no limit* on what could theoretically be used. This is not
the case in a "modern machine".

>
> All Turing machine programs which use unbounded tape for a given input
> compute a function which is undefined for that input. A finite
> computer need only go into an infinite loop for those inputs to
> compute the same function.
>
> The reason why we need to define Turing machines with infinite tape is
> so that they model all computers we could ever build. Though any
> particular computer we build is finite, we like to prove things about
> all computers we could ever build, assuming we can build bigger and
> bigger ones without bound. I won't get into whether that assumption is
> reasonable...

Sorry, but I just don't buy your argument. The reason why we define
Turing machines as having unlimited, unrestricted-access
memory is because that is *the*
key feature of turing machines that sets them apart from finite state
automata and push-down automata, which in turn bears directly on
which classes of languages the automata can recognize.

Modern computers with fixed amounts of memory are finite state
machines. Their memories are generally quite large, so they can
recognize a *lot* of languages (because they can have a lot of
different states)...but they can still only recognize
members of the class of regular languages (because their memories
are limited). If you want to add the ability to add memory to the
machine every time you decide you need some, you are no longer looking
just at the machine itself...you are looking at a new machine that
encompasses the finite state machine and whatever omniscient machine
is doling out the unlimited amounts of memory. This super-machine
would be a turing-machine equivalent, but I challenge you to build
one (one that can really do *unlimited* memory, not just really
huge amounts...that is the key).

Benton Jackson

unread,
May 4, 1996, 3:00:00 AM5/4/96
to

Randolph M. Jones wrote:
>
> Patrick Juola wrote:

< big snip>

> > So a proof that a program is
> > solvable in polyspace on a TM is proof that it's solvable on a modern
> > computer and vice versa.
>
> It is this leap that "a modern computer" is somehow equivalent to
> "any TM-equivalent" that I challenge. This would have to be the
> key part of your proof.

The basic idea of the proof is quite simple, although the actual proof is
quite involved. You merely have to prove that each element of a modern
computer is simulatable with a turing machine, and that you can link these
parts together. You just have to write a bunch of turing machines to
show each element. It's been done, and I've seen the proof, and I'm
convinced. It's not a leap.

Also, you have to prove that you can simulate a turing machine with
a modern computer (assuming unlimited memory, which Microsoft seems
to do a lot of). This is an easy and common undergraduate assignment.

So, once you've done this, now you can take any computable system, and
to prove that it is computationally equivalent to a modern computer, you
merely have to prove that you can compute each element of a turing
machine with the system, and that you can hook the parts together into
a whole. This has been done with Conway's Life game!

Now, nobody ever said anything about EFFICIENTLY computing things with
a turing machine. That's ridiculous.

--
Benton Jackson, Goat Rider at Fenris Wolf Electronic Games
ben...@fenriswolf.com Wolfheim: (612)785-9819
http://www2.bitstream.net/~benton Fax: (612)785-0852

Patrick Juola

unread,
May 5, 1996, 3:00:00 AM5/5/96
to

In article <318A3D...@eecs.umich.edu> "Randolph M. Jones" <rjo...@eecs.umich.edu> writes:
>> In direct answer to your question, it's fairly easy to prove that
>> problems solvable in polynomial space on TM-equivalent machine are
>> solvable in poly-space in any TM-equivalent. (Hopcroft and Ullman, 1969,
>> cited in Garey and Johnson, 1979).
>
>I'm with you so far...
>
>> So a proof that a program is
>> solvable in polyspace on a TM is proof that it's solvable on a modern
>> computer and vice versa.
>
>It is this leap that "a modern computer" is somehow equivalent to
>"any TM-equivalent" that I challenge. This would have to be the
>key part of your proof.

So look it up. _Computers and Intractability : A Guide to the Theory
of Incompleteness_, Michael R. Garey and David S. Johnson, New York:
W.H.Freeman, 1979.

Patrick

Ken Nakata

unread,
May 5, 1996, 3:00:00 AM5/5/96
to

pat...@gryphon.psych.ox.ac.uk (Patrick Juola) writes:
>>It is this leap that "a modern computer" is somehow equivalent to
>>"any TM-equivalent" that I challenge. This would have to be the
>>key part of your proof.

>So look it up. _Computers and Intractability : A Guide to the Theory
>of Incompleteness_, Michael R. Garey and David S. Johnson, New York:
>W.H.Freeman, 1979.

Oh, really? Are "a modern computer" and a Turing machine really
equivalent? I thought, whether modern or not, a tangible digital
computer is equivalent to a linear bounded automaton which is a
restricted type of Turing machine with an only finite amount of tape
and a head not allowed to move beyond either end of the tape. The
thing is, a LBA is *not* equivalent to a universal Turing machine with
an infinitely long tape.

At any rate, it seems to me that this thread does not belong in
comp.ai.*, but in comp.theory.

ken
--
Ken Nakata . . . . Cook College, Rutgers - The State University of New Jersey
http://remus.rutgers.edu/~kenn/, ftp://remus.rutgers.edu/pub/NetBSD/index.html
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
"He who refuses to do arithmetic is doomed to talk nonsense." -- John McCarthy

Greg Sidebottom

unread,
May 6, 1996, 3:00:00 AM5/6/96
to

In article <318A3F...@eecs.umich.edu>,

Randolph M. Jones <rjo...@eecs.umich.edu> wrote:
*Greg Sidebottom wrote:
**
** In article <31870D...@eecs.umich.edu>,
** Randolph M. Jones <rjo...@eecs.umich.edu> wrote:
** *Patrick Juola wrote:
** ** I can prove that a Turing machine does the same things that
** ** a "modern" machine does. I can prove that a modern machine does the
** ** same thing that a Turing machine does.
** *
** *Hmmm...I guess I'd really like to see that proof. Which commercially
** *available computer with unlimited memory are you going to use in your
** *proof?

Hmmm, I wish you'd presented your reasoning below at this point to
save me the following embarrassment.

**
** The fact that a Turing machine is defined to have an infinite tape is
** irrelevant with respect to the functions it can compute. This is
** because any terminating computation can only use a finite part of the
** tape. So a Turing machine cannot compute any functions that a finite
** computer (whith large enough memory) cannot.
*
*I did not say that the computer had to have infinite memory, I said
*that it would have to have unlimited memory, and that is *entirely*
*relevant to setting apart a Turing machine from a finite state
*automaton. Although only a finite amount of the tape is ever used,
*there is *no limit* on what could theoretically be used. This is not
*the case in a "modern machine".

OK, I was wrong (<blush> <grin>).

*
** [my erroneous reasoning deleted]

*
*Sorry, but I just don't buy your argument. The reason why we define
*Turing machines as having unlimited, unrestricted-access
*memory is because that is *the*
*key feature of turing machines that sets them apart from finite state
*automata and push-down automata, which in turn bears directly on
*which classes of languages the automata can recognize.
*
*Modern computers with fixed amounts of memory are finite state
*machines. Their memories are generally quite large, so they can
*recognize a *lot* of languages (because they can have a lot of
*different states)...but they can still only recognize
*members of the class of regular languages (because their memories
*are limited). If you want to add the ability to add memory to the
*machine every time you decide you need some, you are no longer looking
*just at the machine itself...you are looking at a new machine that
*encompasses the finite state machine and whatever omniscient machine
*is doling out the unlimited amounts of memory. This super-machine
*would be a turing-machine equivalent, but I challenge you to build
*one (one that can really do *unlimited* memory, not just really
*huge amounts...that is the key).

Thanks for persisting in clearing this up for me and probably others.

Greg


Antti Juhani Ylikoski

unread,
May 7, 1996, 3:00:00 AM5/7/96
to

>From: ke...@eden.rutgers.edu (Ken Nakata)


>Subject: Re: turing machine...who cares?

Message-ID: <4mjr31$8...@er7.rutgers.edu>
References: <31870D...@eecs.umich.edu> <4m7buu$k...@news.ox.ac.uk> <318A3D...@eecs.umich.edu> <4mhtv0$b...@news.ox.ac.uk>
NNTP-Posting-Host: er7.rutgers.edu
Xref: nntp.hut.fi comp.ai:36965 comp.ai.philosophy:40678 comp.ai.alife:5550

[snip]

>Oh, really? Are "a modern computer" and a Turing machine really
>equivalent? I thought, whether modern or not, a tangible digital
>computer is equivalent to a linear bounded automaton which is a
>restricted type of Turing machine with an only finite amount of tape
>and a head not allowed to move beyond either end of the tape. The
>thing is, a LBA is *not* equivalent to a universal Turing machine with
>an infinitely long tape.

A computing system -- a LBA, or a computer -- with a finite memory is
always a deterministic finite automaton, or, a finite state
automaton. When DFA:a were invented some thirty years ago by Michael
O. Rabin et al., one of the motivations for inventing them was to
build a model of a computer which has a finite memory [1]. Threrfore,
for example, the Pumping Lemma [1] applies to all real computers.

>At any rate, it seems to me that this thread does not belong in
>comp.ai.*, but in comp.theory.

In his book Artificial Intelligence, Patrick Henry Winston notes that
AI concerns studying any intelligence, in humans and in machines (and
even in androids!), thus there is some justification for this
discussion in comp.ai.

References.

[1] Lewis-Papadimitriou: Elements of the Theory of Computation

Cheers,

Andy Ylikoski

Sverker Nilsson

unread,
May 10, 1996, 3:00:00 AM5/10/96
to

Randolph M. Jones wrote:
>
> Greg Sidebottom wrote:
> >
> > In article <31870D...@eecs.umich.edu>,

> > Randolph M. Jones <rjo...@eecs.umich.edu> wrote:
> > >Patrick Juola wrote:
> > >> I can prove that a Turing machine does the same things that
> > >> a "modern" machine does. I can prove that a modern machine does the
> > >> same thing that a Turing machine does.
> > >
> > >Hmmm...I guess I'd really like to see that proof. Which commercially
> > >available computer with unlimited memory are you going to use in your
> > >proof?

> >
> > The fact that a Turing machine is defined to have an infinite tape is
> > irrelevant with respect to the functions it can compute. This is
> > because any terminating computation can only use a finite part of the
> > tape. So a Turing machine cannot compute any functions that a finite
> > computer (whith large enough memory) cannot.
>
> I did not say that the computer had to have infinite memory, I said
> that it would have to have unlimited memory, and that is *entirely*
> relevant to setting apart a Turing machine from a finite state
> automaton. Although only a finite amount of the tape is ever used,
> there is *no limit* on what could theoretically be used. This is not
> the case in a "modern machine".
>
> >
> > All Turing machine programs which use unbounded tape for a given input
> > compute a function which is undefined for that input. A finite
> > computer need only go into an infinite loop for those inputs to
> > compute the same function.
> >
> > The reason why we need to define Turing machines with infinite tape is
> > so that they model all computers we could ever build. Though any
> > particular computer we build is finite, we like to prove things about
> > all computers we could ever build, assuming we can build bigger and
> > bigger ones without bound. I won't get into whether that assumption is
> > reasonable...
>
> Sorry, but I just don't buy your argument. The reason why we define
> Turing machines as having unlimited, unrestricted-access
> memory is because that is *the*
> key feature of turing machines that sets them apart from finite state
> automata and push-down automata, which in turn bears directly on
> which classes of languages the automata can recognize.
>
> Modern computers with fixed amounts of memory are finite state
> machines. Their memories are generally quite large, so they can
> recognize a *lot* of languages (because they can have a lot of
> different states)...but they can still only recognize
> members of the class of regular languages (because their memories
> are limited). If you want to add the ability to add memory to the
> machine every time you decide you need some, you are no longer looking
> just at the machine itself...you are looking at a new machine that
> encompasses the finite state machine and whatever omniscient machine
> is doling out the unlimited amounts of memory. This super-machine
> would be a turing-machine equivalent, but I challenge you to build
> one (one that can really do *unlimited* memory, not just really
> huge amounts...that is the key).

That sounds like a challenging project indeed!

However, it might in fact be possible, depending on the physical
properties of the universe. Even if the universe is finite, contains
finite matter. As I understand it, the requirement is that it should be
"open", i.e. expand for ever, and that the basic nuclear particles
are stable. (The proton never decays.) I quote the following from an
interesting paper I found on this URL:

http://www.hia.com/pcr/dyson.html

[Begin quote]

FUTURE SPACE

TIME WITHOUT END: PHYSICS AND BIOLOGY IN AN OPEN UNIVERSE (*)

Freeman J. Dyson

[snip]

It is possible to say a little about memory without getting into
detailed architectural problems, since memory is an abstract
concept. The capacity of a memory can be described quantitatively as a
certain number of bits of information. I would like our descendants to
be endowed not only with an infinitely long subjective lifetime but
also with a memory of endlessly growing capacity. To be immortal with
a finite memory is highly unsatisfactory; it seems hardly worthwhile
to be immortal if one must ultimately erase all trace of one's origins
in order to make room for new experience. There are two forms of
memory known to physicists, analog and digital. All our computer
technology nowadays is based on digital memory. But digital memory is
in principle limited in capacity by the number of atoms available for
its construction. A society with finite material resources can never
build a digital memory beyond a certain finite capacity. Therefore
digital memory cannot be adequate to the needs of a life form planning
to survive indefinitely. Fortunately, there is no limit in principle
to the capacity of an analog memory built out of a fixed number of
components in an expanding universe. For example, a physical quantity
such as the angle between two stars in the sky can be used as an
analog memory unit. The capacity of this memory unit is equal to the
number of significant binary digits to which the angle can be
measured. As the universe expands and the stars recede, the number of
significant digits in the angle will increase logarithmically with
time. Measurements of atomic frequencies and energy levels can also
in principle be measured with a number of significant figures
proportional to (log t). Therefore an immortal civilization should
ultimately find ways to code its archives in an analog memory with
capacity growing like (log t). Such a memory will put severe
constraints on the rate of acquisition of permanent new knowledge, but
at least it does not forbid it altogether.

[snip]

[End quote]

"Hope this helps,"

Sverker Nilsson

Sampo H Smolander

unread,
May 27, 1996, 3:00:00 AM5/27/96
to

: ultimately find ways to code its archives in an analog memory with

: capacity growing like (log t). Such a memory will put severe
: constraints on the rate of acquisition of permanent new knowledge, but
: at least it does not forbid it altogether.

: "Hope this helps,"

: Sverker Nilsson

I just wonder how can they possible code things to such a memory
because at the moment of coding they can just be sure of a certain
amount of beginning digits, right?
So, all increase in the information which comes by the time, is random,
am I right?

* Sampo Smolander I study biology and
* email: Sampo.S...@Helsinki.Fi mathematics at The University
*** HTTP://www.helsinki.fi/~ssmoland/ of Helsinki, Finland

0 new messages