A Geometrically Natural Uncomputable Function

There are many functions from \mathbb{N} to \mathbb{N} that cannot be computed by any algorithm or computer program. For example, a famous one is the halting problem, defined by f(n) = 0 if the nth Turing machine halts and f(n) = 1 if the nth Turing machine does not halt. Another one in the same spirit is the busy beaver function.

We also know a priori that there must be uncomputable functions, since there are 2^{\aleph_0} functions from \mathbb{N} to \mathbb{N} but only \aleph_0 computer programs. But that is nonconstructive, and the two examples I gave above seem a bit like they’re cheating since their definitions refer to the concept of computability. Is there a natural example of an uncomputable function that does not refer to computability?

In this paper, Alex Nabutovsky found what I think is a great example of such a function from geometry. Details below.

For any n, let S^n be the n-dimensional unit sphere \{x \in \mathbb{R}^n \mid |x| = 1\}. For all n there is an “equatorial” embedding of S^n into S^{n+1} sending \langle x_1,\ldots, x_n\rangle to \langle x_1,\ldots, x_n, 0\rangle. This is certainly the nicest way of embedding S^n into S^{n+1} but there are other ways.

If j is an embedding of S^n into S^{n+1} then let its amount of wiggle room be the maximum amount that j‘s image can be thickened before it intersects itself. More precisely, it is the maximum t such that x_0 + t_0 v_0 \ne x_1 + t_1 v_1, where t_0, t_1 < t, x_0 and x_1 are in the image of j, v_0 is the unit normal to the image of j at x_0 and v_1 is the unit normal to the image of j at x_1. We let j‘s crumbledness be the reciprocal of its amount of wiggle room.

It is known (by a theorem of Stephen Smale) that any embedding of S^n into S^{n+1} can be isotoped to the equatorial embedding (up to reparameterization), but you may have to increase the crumbledness to do it. Nabutovsky proves that, for any dimension n and crumbledness c, there is an f_n(c) such that any embedding of crumbledness <c can be isotoped to the equatorial embedding going through only embeddings of crumbledness <f_n(c). We lose nothing in terms of complexity by considering f_n\colon \mathbb{N}\to\mathbb{N}.

Nabutovsky shows that for any n \geq 5, any f_n satisfying the above condition is uncomputable, and, furthermore, the minimum f_n which works grows like the busy beaver function!

The proof depends on the fact that for n\geq 5, it is undecidable if a compact manifold (presented either as a simplicial complex, or as a zero-set of a polynomial with rational coefficients, or some such representation that a computer can handle) embedded in S^{n+1} is diffeomorphic to S^n. (For a good summary of these types of undecidability results in group theory and topology, see Section 3 of Bob Soare’s Computability and Differential Geometry.) Essentially, the idea is that if f were computable, you could decide if a manifold were homeomorphic to S^n by taking embedding it in S^{n+1}, measuring its crumbledness (say as c), then checking all possible isotopies of the manifold through embeddings of crumbledness < f_n(c). The fact that the manifold’s crumbledness can be measured and that all possible isotopies going through embeddings of bounded crumbledess can be checked computably is related to the fact that often you can computably search over compact spaces, as I wrote about in this post.

If you can get a hold of a copy, I highly recommend Shmuel Weinberger’s book Computers, Rigidity, and Moduli, where he talks about this and other related results in a very lively and engaging manner.

Edit: Fixed some notation.

5 thoughts on “A Geometrically Natural Uncomputable Function

  1. Just to make sure I understand: the f_n has nothing to do with the embedding f, right? And you mean “for any dimension n there is an f_n such that any embedding of crumbledness <c can be isotoped to the equatorial embedding going through only embeddings of crumbledness <f_n(c)“?

  2. You’re absolutely right. Thanks for the correction.

    (By the way, in WordPress $<math in latex>$ doesn’t work. You have to write $latex <math in latex>$. I edited your comment since presumably that’s what you wanted.)

  3. I don’t understand the sentence “We lose nothing in terms of complexity by considering $f_n\colon \mathbb{N}\to\mathbb{N}$”. This doesn’t make sense, because for fixed $n$, $f_n$ is not a function over the natural numbers.

    Is this example geometrically natural because it’s a continuous function for each $n$? So you’ve described a sequence of “naturally defined” continuous functions, all of which are not computable.

    1. We can make f_n into a function into \mathbb{N} by taking ceil (it preserves the property that the function is supposed to have, namely giving an upper bound on crumpledness required for isotopy), then restrict its domain to \mathbb{N} so that we can easily talk about its computational properties.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s