One of the most thorny problems in knot theory is that of knot equivalence: determining if two knots made in a closed loop can be transformed into one another by a series of moves which do not involve cutting the string. Alan Turing conjectured that the problem might be undecidable—impossible to solve in finite time by an algorithm. In 2011, Alexander Coward and Marc Lackenby proved there was “An upper bound on Reidemeister moves” (full text at link) which solves the equivalence problem for the more general problem of link and knot diagrams. For a link with n crossings, they prove:
Theorem 1.1. Let D_1 and D_2 be connected diagrams for some knot or link in \mathbb{R}^3, and let n be the sum of their crossing numbers. Then D_2 may be obtained from D_1 by a sequence of at most \exp ^{(c^n)}(n) Reidemeister moves, where c = 101,000,000.
Now, what is that innocent-looking \exp function with a superscript expression?
The function \exp(x) is the exponential function 2^x , and \exp^{(r)}(x) means iterate this function r times. Thus, \exp^{(c^n)}(n) is shorthand for a tower of 2s with an n at the top, the height of the tower being c^n.
The paper notes:
This upper bound is very large indeed, but it is explicit and computable
How “very large indeed”?
The \exp function is, then the operation of tetration, or iterated exponentiation, also written in Donald Knuth’s up-arrow notation as (2\uparrow\uparrow 101000000 n)^n.
Thus, the problem is computable, but the upper bound on how long it may take is a number so many times longer than the age of the universe that there aren’t enough elementary particles in the visible universe even to write it down.
So, get started on that tangle of cables underneath your desk—“this may take some time”.
