König’s Lemma and the Kleene Tree
For the benefit of the topology seminar audience at the math department of University of Ljubljana, I have written a self-contained explanation of the Kleene tree, which is an interesting object in computability theory. For the benefit of the rest of the planet, I am publishing it here.
Abstract: I present a basic result about Cantor space in the context of computability theory: the computable Cantor space is computably non-compact. This is in sharp contrast with the classical theorem that Cantor space is compact. The note is written for mathematicians with classical training in topology and analysis. I assume nothing from computability theory, except the basic intuition about how computers work by executing instructions given by a finite program.
Download: kleene-tree.pdf (updated May 3rd, 2006)