Re: Turing Machines and Physical Computation

stephen_at_nomail.com
Date: 11/27/04 

Date: 27 Nov 2004 21:20:14 GMT

In sci.math Neil W Rickert <rickert+nn@cs.niu.edu> wrote:
: examachine@gmail.com (Eray Ozkural exa) writes:
:>Well, our instructors were careful enough to teach us the Cinderella
:>book which says no such stupid thing. It talks about abstract
:>machines, but it takes pains to make it awfully clear that this is
:>indeed the theory of real-world computers. Abstract does not mean
:>non-physical, and I'm grateful that the authors are clever persons.

: Abstract does mean non-physical.

: Turing machines are abstract. They are not physical. It is the
: abstractness of the Turing machine that makes it so useful in
: theorizing about real world computers.

For those who claim that Turing machines must be physical,
how do you address the following?

A language is said to be decidable if there exists a TM that
outputs yes when given a string in the language, and no otherwise.

The language a^n b^n (n a's followed by n b's) is clearly
decidable by a non-physical Turing machine with unlimited memory.
However no real PC can recognize all strings in this language.
A real PC can only count so high and will run out of memory,
so it will fail for very large values of n.

To me the options seem to be:
        
        declare that a^n b^n is not a decidable language. The
                only languages that are decidable are those decidable
                by a real physical PC with finite memory. This would mean that
                the decidable languages are the regular languages.

        declare that a^n b^n is not a language at all because
                it contains strings that are too large to be physically
                represented. This means that all languages are finite,
                and therefore regular.

In both cases you basically have to restrict yourself to
regular languages. If all you have are regular languages,
then all you need are finite state machines. Why even
bother with Turing machines if you actually believe that
finite state machines are all that you need?

Stephen

Relevant Pages