[prog] Re: questions, what is a turing machine

[Daniel.]

>Formal computer scientists like Turing Machines because they allow us to
>prove what computers can and cannot do.  For instance, you can prove
>that a Turing Machine cannot sort a list in any less than O(n ln n)
>time.  Therefore, no computer can sort a list any faster, no matter what
>trick you use.

Actually, though Turing machines can solve all the same problems 
other computational models can solve, they cannot necessarily solve 
them as fast as other models, because they have no random-access 
store but must scan through their memory looking for the appropriate 
variable...

For anyone interested, a medium-length description of Turing machines 
(this is a modern version somewhat simplified from Turing's original 
version):
The input is a string of symbols from a specified finite alphabet (a 
two-symbol alphabet like "0 and 1" is proved sufficient but more are 
often convenient) and these symbols are written on successive cells 
of a memory tape. The tape is finite at any given time, but cells are 
added to the ends as needed. The computation is done by a read/write 
head which has an internal state variable, with a finite range of 
possible values and a specified initial value. The head acts 
according to a fixed table of instructions of the form:
"If state is _ and the current cell has symbol _ then erase the cell, 
write symbol _ in the cell, move one cell to the _ (left or right), 
and set state to _." The head continues consulting the table and 
obeying the appropriate instructions until the state variable is set 
to a prespecified value, the "halt state", at which point it 
terminates. Again, this model is mainly used to prove theorems about 
computability; it's far too cumbersome to write serious programs in, 
and I don't think it gives much insight into the way a real computer 
works, either.
-Daniel.
--