Monthly Archives: October 2008
Another Puzzle in Recursion Theory: n-Enumerable Sets
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 … Continue reading
Filed under Puzzles
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, … Continue reading
Filed under Puzzles
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 … Continue reading
Filed under Uncategorized
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 … Continue reading
Filed under Toposes
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 … Continue reading
Filed under Functional Programming
