A Turing machine is a device/computer that follows a strip of different symbols, manipulating them according to a table of rules.
The machine itself has at any given time only a single state, and the action the machine takes and its new state depends on the Transition rule for its current state plus the symbol under it.
The concept itself is very simple, but using these rules you could theoretically simulate any computer algorithm.
You can read more about Turing machines at http://en.wikipedia.org/w iki/Turing_machine
In this flash the machine has a table of rules that allows it to play Tic Tac Toe against a human opponent. It just takes a very long time for it to make its move.