There are many functions from to that cannot be computed by any algorithm or computer program. For example, a famous one is the halting problem, defined by if the th Turing machine halts and if the th 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 functions from to but only 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 , let be the -dimensional unit sphere . For all there is an “equatorial” embedding of into sending to . This is certainly the nicest way of embedding into but there are other ways.

If is an embedding of into then let its amount of wiggle room be the maximum amount that ‘s image can be thickened before it intersects itself. More precisely, it is the maximum such that , where , and are in the image of , is the unit normal to the image of at and is the unit normal to the image of at . We let ‘s crumbledness be the reciprocal of its amount of wiggle room.

It is known (by a theorem of Stephen Smale) that any embedding of into 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 and crumbledness , there is an such that any embedding of crumbledness can be isotoped to the equatorial embedding going through only embeddings of crumbledness . We lose nothing in terms of complexity by considering .

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

The proof depends on the fact that for , 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 is diffeomorphic to . (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 were computable, you could decide if a manifold were homeomorphic to by taking embedding it in , measuring its crumbledness (say as ), then checking all possible isotopies of the manifold through embeddings of crumbledness . 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.