The Turing Omnibus, Dewdney
A whirlwind tour of lots of different topics in pre-1990 computer science.
This book did not live up to expectations I had for it.
I was expecting it to be like [[Gödel, Escher, Bach]]N, a treatise on the most important parts of computer science, woven together beautifully with intuitive explanations, but it felt more like a list of algorithms and data structures – which there is nothing wrong with! It just that it was no [[Gödel, Escher, Bach]]N.
The bits of the book that I did enjoy were the more theoretical and abstract ones that reminded me a lot of GEB, on Turing machines, self-replicating computers, and Church’s theorem, not DOS, hash tables or how you can turn images into a tree. Again, I’m sure that if I’d had accurate expectations about the book then I’d have appreciated it more.
What was cool though was seeing the stuff from [[AIMA - Logical Agents]]N crop up again. It was like getting in a time machine back into the 1980s when all the logical stuff was more relevant to AI than it is now (or at least from my current impressions of [[AI - A Modern Approach]]N.
Flashcards
What is Turing reduction?
Showing that a problem is uncomputable by reducing it to the halting problem.
What is Codd’s machine?
A Turing machine celular automata capable of replicating itself.
What does this show?
What does this show?The Chomsky hierarchy.
What type of automaton can recognise a recursively enumerable language?
A Turing machine.
What sort of automaton can recognise a context-sensitive language?
A linear bounded automaton.
What sort of automaton can recognise a context-free language?
A pushdown automaton.
What sort of automaton can recognise a regular language?
A finite state automaton.
Why is satisfiablity a central problem in computer science?
Because all NP-complete problems can be reduced to a SAT problem.
What is the busy-beaver game?
Trying to find the halting Turing machine that writes the most amounts of $1$s using only a given set of states.
What is the Church-Turing thesis?
A thesis stating that there is no formulism of computation more powerful than a Turing machine.
What evidence do we have for the Church-Turing thesis?
Every formalism of computation discovered so far has been equivalent to a Turing machine.