[prog] questions, what is a turing machine

[Robert J. Hansen]

> Ok, what is a Turing machine? I've heard of it before, does it relate to
> teaching how a processor functions?

Short version: the Turing Machine is a mathematical model of a
computer.  The model can describe the behavior of any computer, no
matter what technology it's based upon or what programming language is
being used.  That sounds like a very audacious claim, but Alan Turing
gave formal mathematical proof that his model could do this.

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.  There are other problems which you can prove a Turing
Machine cannot solve, and therefore, no computer can solve those
problems.

Long version: Read this paper.

Turing, Alan Mathison, "On Computable Numbers, With an Application to
the Entscheidungsproblem", _Proceedings of the London Mathematical
Society_, Series 2, Volume 42, published 1936.

> "If people prefer $foo, great, prefer $foo. ".
>
> I'm really confused on what you are talking about, BTW where is 'foo' and
> 'bar' used?? All GNU/Linux programmers seem to enjoy using the names...

In the Perl programming language, many variables are prepended with a
dollar sign.  Whenever Perl sees a dollar-sign-and-text anywhere in a
string, it will substitute the value of $foo for the actual letters
"$foo".  

When programmers want to talk in generalities, they often use Perl
syntax.  "What do I want on my pizza?  Uhh... $foo."  That's a hackerish
way of saying "anything".  Or, to translate "If people prefer...", try
this: "If people prefer <insert your language here>, great, prefer
<insert your language here>".

Insofar as what foo means, check the Jargon File (
http://www.tuxedo.org/~esr/jargon or a mirror at
http://www.science.uva.nl/~mes/jargon/t/thejargonlexicon.html ). 
Bookmark that site--it's a great reference to deciphering terms you
don't understand.