Gordian Knot

[franktaw at netscape.net]

Strictly speaking, no single problem (with a finite answer) can be 
uncomputable - it is computed by a machine that outputs that answer.  
We may not know which machine that is, but it exists.  (Intuitionists 
reject this argument, of course.)  It is only a family of problems that 
can be considered uncomputable.

There are algorithms known for determining whether two knots are 
equivalent, which will let us determine whether our knot is a true knot 
or an unknot.  The complexity level is very high.

I don't know exactly what presentation mode is required for these 
algorithms - probably something like Dowker notation.  Certainly if you 
present the knot simply as a function from from the circle to R^3, the 
problem is undecidable - since the question of whether one real number 
is larger than another is undecidable.

Franklin T. Adams-Watters


-----Original Message-----
From: jvospost3 at gmail.com

Is there such a thing as an Uncomputable Knot?  An object for which 
determining if it a knot or link or unknot requires an uncomputable 
function? Perhaps as a limit of a sequence of knots with integer 
invariants (which could be an OEIS sequence)? Perhaps from a Hilbert's 
10th Problem issue on a knot polynomial, or from the word problem in 
Groups, or the Homeomorphy problem?

Only an Oracle can tell if the Gordian Knot is uncomputable, or untie 
an Uncomputable Knot?


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.