Gordian Knot

[Jonathan Post]

Dear Frank,

Up until the surprising answer to Hilbert's 10th problem, exhibiting a
specific Diophantine Equation such that no Turing machine could tell if
there was or was not a solution, the intuitionists had the upper hand.  The
current issue of Notices of the AMS is a special issue on Turing whwich led
me to my rather ill-formed problem.  If it is a knot problem at all, and not
a notknot--problem.

On 12/6/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
>
> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061206/161891c2/attachment-0002.htm>