We can think of a computably enumerable (or c.e.) set as a bag which some computer program puts more and more numbers into over time. The set then consists of all numbers which are in the bag from some point on (i.e., the numbers which are eventually put in the bag by the program).
Suppose [...]
Entries from October 2008
October 26, 2008
Another Puzzle in Recursion Theory: n-Enumerable Sets
October 16, 2008
Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets
Let be the set of all such that the th Turing machine halts. (For these puzzles, we will assume that Turing machines are always run on a blank initial state, i.e., they take no input.) Recall that is computably enumerable, but not decidable.
Puzzle #1. Describe a winning strategy for the following [...]
October 13, 2008
When are the Real Numbers Necessary?
The natural numbers can all be finitely represented, as can the rational numbers. The real numbers, however, cannot be so represented and require some notion of “infinity” to define. This makes it both computationally and philosophically interesting to determine for what purposes you need the real numbers, and for what purposes you need [...]
October 13, 2008
What Would the World Look Like if Everything was Computable?: An Introduction to Hyland’s Effective Topos
Suppose that we wanted to construct a mathematical universe where all objects were computable in some sense. How would we do it?
Well, we could certainly allow the set into our universe: natural numbers are the most basic computational objects there are. (Notation: I’ll use to refer to when we’re considering [...]
October 7, 2008
A language which does term inference
Many strongly typed languages like OCaml do type inference. That is, even though they’re strongly typed, you don’t have to explicitly say what the type of everything is since a lot of the time the compiler can figure it out by itself. For example, if you define a function which takes an x [...]
