Turing Machines, An Introduction
Alan Turing
It would be difficult to overstate the genius of Alan Turing.
He elucidated the very essence of computation, and perhaps thought itself.
Darwin showed us that we are not as far from the other animals as one might first suspect;
Turing showed us we are not that far away from a computer either, at least in theory.
Yes, our thoughts, our emotions, our consciousness,
could indeed be purely mechanical.
There is no soul after all; there never was.
Let us jettison,
once and for all,
our anachronistic religions -
those conduits of blind certainty (otherwise known as faith)
that we cling to because we are afraid of death,
or of life itself.
The universe is beautiful, even if it is an accident -
and your lover is beautiful, even if she is a mortal collection of neurons.
Prior to his groundbreaking work in computation,
Turing was instrumental in the defeat of the Nazis,
cracking their Enigma codes
and providing vital information to the allies.
Yes, England appreciated his efforts,
and called him a national hero - until he openly acknowledged his homosexuality.
The government revoked his security clearance,
and administered drugs in an attempt to make him "normal".
Hounded by the zealots of his day, this marvelous, troubled man took his own life.
We've come a long way in the past 50 years, but we still have a long way to go.
As I write this, our homophobic president,
Bush 43,
supported by millions of religious idiots,
wants to write his prejudices into the Constitution,
permanently denying gay individuals an equal status in our society.
Sorry, but I've had quite enough of George Bush, and certain religions, for one lifetime.
It's time to move on.
And yet, who knew that 8 years later we would elect somebody truly horrific, of Hitlerian status.
Makes Bush look like an intelligent, reasoned man.
But I digress.
Alan Turing is one of the most important, and most interesting
mathematicians of our time.
Do take a moment to read his
biography.
Turing Machine
At a high level, the turing machine (tm) is a state machine with an infinite read/write tape,
and that makes all the difference.
Far more powerful than a
pdm,
the tm can record intermediate results, and perform computations,
and recognize or generate languages of unprecedented complexity.
Turn the page, and we'll formally define the turing machine, and explore its properties.