# The Turing Omnibus

> Source: https://ollybritton.com/notes/books/the-turing-omnibus/ · Updated: 2024-10-11 · Tags: notes, book

![the-turing-omnibus.jpg](https://ollybritton.com/assets/attachments/img/the-turing-omnibus.jpg)

> 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 [Godel, Escher, Bach](https://ollybritton.com/notes/books/godel-escher-bach/), 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 [Godel, Escher, Bach](https://ollybritton.com/notes/books/godel-escher-bach/).

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](https://ollybritton.com/notes/textbooks/ai-a-modern-approach/knowledge-reasoning-and-planning/logical-agents/) 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](https://ollybritton.com/notes/textbooks/ai-a-modern-approach/).

## 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.

##### ![PHOTO CHOMSKY HIERARCHY](chomsky-hierarchy.png) 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.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt