This talk is geared towards an audience of science fiction readers, who are supposed to find computation interesting for two reasons.

First, as technologically curious persons, we want to understand the role played computation in current society:

Why do Google, genome sequencing, and car navigation systems work? These are computationally feasible tasks with astounding consequences for society.
Why can’t I use natural language to talk to my computer, like in Star Trek? This computational task is routinely solved by our brains, but we don’t seem to be able to automate it, to our great annoyance. Why can’t my neighbour break my home banking cryptosystem? A seemingly computationally infeasible task, to our great pleasure. 

Second, as consumers of speculative fiction, we want to understand the questions that permeate the genre. In general, the nature of our computational world determines the possibility of strong artificial intelligence, a trope of Science Fiction. In particular, writers such as Charles Stross make the transition between these computational worlds a central world-building or plot element. 

The talk provides a non-fiction counterpoint to the fiction, including a gentle introduction to theoretical computer science, in particular the theory of computation, focussing on the question “Which computational problems can be solved?” (Solved, for example, using an electronic omputer – but it’s not really a question about hardware.) Depending on the answer, we live in one of five different computational realities, which we can call Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania. The greatest challenge – or, if you want, embarrassment – of computer science is that we don’t know which.