Turing Compliant?

Hrvoje Niksic hniksic at srce.hr
Thu Sep 2 03:37:06 EDT 1999


François Pinard <pinard at iro.umontreal.ca> writes:

> Skip Montanaro <skip at mojam.com> writes:
> 
> > A Turing Complete language is one that can compute anything that you
> > can compute with a simple Turing machine.
> 
> A "simple" Turing machine has infinite memory.  Who has that? :-)

Actually, garbage-collection can be defined as "emulation of infinite
memory".  The idea is that you consider every object to be immortal
and its memory image intact.  The underlying system does cheat by
putting a new object at the same place in your finite memory, but only
when it proves that you can't tell it's cheating.

Thus Lisp has been Turing complete for fourty or so years.  :-)




More information about the Python-list mailing list