Monthly Archives: October 2008

October 26, 2008 · 1:11 pm

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 on (i.e., the numbers which are eventually put in the bag by the program).

Suppose that we relax the restrictions on the program, and we allow it to take a number out of the bag that it has put in (but once the program has done that, the number stays out forever). We call the set of numbers which are in the bag from some point on (i.e., the set of numbers which are put in the bag and never taken out) in a procedure of this sort a 2-c.e. set.

We can analogously let an n-c.e. set be one given by a program which can, for each number, “toggle” that number’s status up to and including n times if it likes.

The puzzle is then to find, for each n, an example of a set which is n-c.e. but not n-1-c.e.

Continue reading →

Leave a Comment

Filed under Puzzles

October 16, 2008 · 7:16 pm

Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets

Let K be the set of all n such that the nth 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 K is computably enumerable, but not decidable.

Puzzle #1. Describe a winning strategy for the following game: You are given three numbers x_1, x_2, x_3. You must correctly say for each number whether or not it is in K. You are allowed to ask (and receive a truthful answer to) two questions of the form “Is n in K?” for any n.

Puzzle #2. Show that there is no winning strategy for the game which is the same as that in Puzzle #1 except you are given two numbers and may ask only one question. (Even stronger, show that if S\subset \mathbb{N} is a set such that you can win that game, then S must be decidable.)

Continue reading →

2 Comments

Filed under Puzzles

October 13, 2008 · 10:44 pm

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 only the rationals.

It’s pretty clear that spatial concepts having to do with distances and rotation require the real numbers. For example, if we took \mathbb{Q}^2 as our model of the plane, the distance from (0,0) to (1,1) would not be rational, and we would not be able to rotate the point (1,0) about the point (0,0) by most angles.

But I always implicitly thought that spatial notions not depending on distances or angles required only the rationals. It turns out that I was wrong: there are spatial notions not depending on distances or angles which differ depending on whether you take space to be \mathbb{Q}^n or \mathbb{R}^n. The fact that I was wrong follows from a theorem of Micha Perles which is very famous in combinatorics, but which I only found out about recently.

Continue reading →

5 Comments

Filed under Uncategorized

· 8:48 pm

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 \mathbb{N} into our universe: natural numbers are the most basic computational objects there are. (Notation: I’ll use N to refer to \mathbb{N} when we’re considering it as part of the universe we’ll building, and just \mathbb{N} when we’re talking about the set of natural numbers in the “real” world.) What should we take as our set of functions N^N from N to N? Since we want to admit only computable things, we should let N^N be the set of computable functions from \mathbb{N} to \mathbb{N}, which we can represent non-uniquely by their indices (i.e., by the programs which compute them).

(For clarity, I’ll use the following notation for computable functions: \phi_e denotes the partial function from \mathbb{N} to \mathbb{N} computed by the eth Turing machine. Given n\in\mathbb{N}, it is possible that the computation \phi_e(n) never halts; in that case, I’ll write \phi_e(n){\uparrow} and say that \phi_e(n) is undefined. If it does halt, I’ll write \phi_e(n){\downarrow} and say that \phi_e(n) is defined. If it halts, then it yields an output m. To indicate what it is, I’ll write \phi_e(n) = m or \phi_e(n){\downarrow} = m.)

So, we’ve decided that N^N should equal \{e \mid \forall n\in\mathbb{N}\, \phi_e(n){\downarrow}\}. What should N^{\left(N^N\right)} equal? At this point, there is a slight subtlety: It’s not simply the set of computable functions from N^N (considered as a subset of \mathbb{N}) to N (considered as N), because we would like to only admit those functions from N^N to N that return the same number when given inputs which represent the same element of \mathbb{N}^\mathbb{N}.

Therefore, we’ll let N^{(N^N)} be the set of e\in\mathbb{N} such that, for all n\in N^N, \phi_e(n){\downarrow}, and whenever n,m\in N^N are such that for all x\in\mathbb{N}, \phi_n(x) = \phi_m(x), then \phi_e(n) = \phi_e(m).

We can similarly define (N^N)^{(N^N)}, except that there are now two places where we should take into account that we consider n,m\in N^N equivalent if for all x\in\mathbb{N}, \phi_n(x) = \phi_m(x): We’ll let (N^N)^{(N^N)} be the set of e such that, whenever n, m \in N^N are equivalent in the aforementioned sense, \phi_e(n) and \phi_e(m) are defined and equivalent in the aforementioned sense.

In a similar fashion, we can define (N^{(N^N)})^{(N^N)} and so on; these sets are called the sets of hereditarily computable functions.

Can we generalize this construction to a category that incorporates all possible computable representations of real objects? More ambitiously, can we generalize to a category that is a genuine mathematical universe in the sense that questions like “Does the Riemann Hypothesis hold in this category?” are meaningful? The answer, due to Martin Hyland, is yes.

Continue reading →

3 Comments

Filed under Toposes

October 7, 2008 · 9:38 pm

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 and adds it to 3, the compiler will figure out that x is an int. (It couldn’t be a float, since it was added to 3 and not 3.0.)

But it often seems like the compiler should be able to infer not just the types of expressions, but the expressions themselves! For example, if the compiler infers that the type of some function f is (int -> int) -> (int list) -> int list (i.e., f is a higher-order function which takes a function from int to int, a list of ints, and produces a list of ints), then f is very probably the map function, defined informally by

map g [x_1;...;x_n] = [g x_1;...;g x_n].

Therefore, if the compiler determines that some expression has that type, and the user has somehow omitted the actual function definition, why not allow the compiler to infer what the expression is?

I made a stab at implementing this type of idea in a toy language I call TermInf (apologies for the weird hosting: I don’t have another hosting service at the moment). It’s a modification of the toy language Poly from Andrej Bauer’s Programming Language Zoo. You’ll need OCaml to compile it. Please feel free to alert me to any bugs or to tell me that my code is horrible.

More details below.

Continue reading →

7 Comments

Filed under Functional Programming