Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!zaphod.mps.ohio-state.edu!wuarchive!uunet!shelby!msi.umn.edu!cs.umn.edu!thornley
From: thornley@cs.umn.edu (David H. Thornley)
Newsgroups: comp.lang.misc
Subject: Re: Turing equivalence (was first-class composable functions)
Message-ID: <1991Feb19.193522.27651@cs.umn.edu>
Date: 19 Feb 91 19:35:22 GMT
References: <11077@pasteur.Berkeley.EDU> <26788@dime.cs.umass.edu> <GESSEL.91Feb19111858@ilium.cs.swarthmore.edu>
Organization: University of Minnesota, Minneapolis, CSci dept.
Lines: 75

In article <GESSEL.91Feb19111858@ilium.cs.swarthmore.edu> gessel@ilium.cs.swarthmore.edu (Daniel Mark Gessel) writes:
>Many programming languages (some would say all) are "Turing
>Equivalent". That is, anything you can do with a Turing Machine, you
>can express with such a programming language. Many programs do not do all
>that they are cabable of on a real machine because they run out of
>memory, i.e. hit the limitations of the machine.
>
>REAL machines today, and probably ever, cannot run all possible programs
>written in a Turing Equivalent Language without restricting them in
>some way (i.e., a failed malloc call).
>
What "probably ever"?  The Turing Machine has one or more infinite-
length tapes.  No real hardware has such, or will ever have such.
Looked at one way, any real computer system is a deterministic
finite automaton.

>One reason for using a turing equivalent language that may run out of
>memory on a given machine, is to have a large degree of machine
>independence, generally considered a valuable thing, which can use
>whatever resources that exist when it is running.
>
To be practical:

If a language can emulate a Turing machine, it can probably handle
most problems in a more efficient way than writing a Turing
machine in the language.  There are notable exceptions, particularly
in older languages like COBOL.

Treating computers as finite automata is not particularly useful.
Consider the language recognized by a compiler.  If you treat the
computer as a finite automaton, the language recognized is a
regular expression, which is, essentially, every legal program
that will fit in the machine in alternation.  It is far more
useful to consider the computer as a Turing machine, write a
suitable grammar, and to bail out if the system runs out of
resources.

Similarly, if you are analyzing computational complexity of
an algorithm on a large DFA, all algorithms can be expressed as
O(1).

Machine portability is also important.  The same computer with
either 4MB or 8MB of RAM is (DFA) a much different machine with
far more states, or (Turing) the same machine that will fail
less often.

>Is the halting problem solvable then? Not for a program in such a
>language, but for a program in that language on a given machine.
>However, on a given machine, the program has "finite" power, and it is
>not "The Halting Problem" anymore.
>
The halting problem for a DFA is mathematically trivial:  simply
enumerate all possible states, and note whether they halt or not
(they will either halt in the number of steps equal to all possible
states, or they will loop forever).

If you want something more practical, consider special hardware. 
Construct memory chips with two identical banks, and a readout
pin indicating whether the two banks have identical contents.
With a little ingenuity, you can do the same with disk banks.
Construct a dual CPU that can tell if both sides have identical
contents and status information.  Then, load each half of the
system identically, and start running with the left half running
precisely half as fast as the right half.  If the two are ever
identical again, the program loops; if it is looping, there are
strict bounds as to how far it can go before you catch it with
this technique.

IMHO, there is no use for these techniques.  They have no
theoretical importance, and I have never heard of a practical
implementation.

Stick with Turing equivalence.

DHT