Algorithm for detecting ribbon or slice links?

This is addressing the last part of your question. There are a couple of issues with trying to implement normal surface theory for immersed surfaces. If an immersed surface is $\pi_1$-injective, then one may homotope it to be normal (meaning that the components of preimages of each tetrahedron is a normal disk - triangle or quadrilateral). In fact, one needs only the weaker condition that the surface is simple loop injective - every homotopically non-trivial curve in the surface is $\pi_1$-injective in the 3-manifold.

The first issue is that a ribbon disk might not be simple loop injective. You may always modify an immersed surface by surgeries along simple loops which are homotopically trivial in the 3-manifold to obtain a simple-loop injective surface. However, starting with an immersed ribbon disk (thought of as a planar surface in the knot complement), there is no guarantee that it is simple loop injective, and such surgery modifications may mess up the ribbon singularities. I thought about this a bit before, but I didn't see how to deal with this issue.

The second issue is that even if one had an immersed normal representative for the ribbon disk (with respect to a triangulation of the knot complement), how does one find such a ribbon disk algorithmically? The usual method for embedded normal surfaces is to analyze the normal surface solution space with compatible quadrilaterals, and notice that the normal coordinates uniquely determine the surface. One then uses linear programming to reduce this to a finite collection of possible surfaces of bounded complexity. For immersed surfaces, this strategy fails, and people haven't found a suitable generalization.

In the special case that your knot in $S^3$ is a fibered knot, there is an algorithm to determine if it is ribbon. It comes from a sequence of papers, due to Darren Long and Andrew Casson. The last paper in the sequence is:

• Algorithmic compression of surface automorphisms. Invent. Math 81 295--303 (1985).

As far as I know we're still some ways from implementing this algorithm but it would be interesting to see someone try.

There is in principle an algorithm to determine if a link is smoothly slice, in that it will terminate on a smooth slice link but on a non smoothly slice link it will run forever.

The algorithm: put your link in $S^3$, triangulate $S^3$ so that the link is transverse and normal in the triangulation (normal meaning appearing linear in each tetrahedron). Extend this triangulation of $S^3$ to a triangulation of $D^4$. Do a search for "normal" 2-manifolds in this triangulated $4$-manifold that bound the link, such that every component is discs. Normal meaning "looks linear and transverse to the skeleton in each 4-dimensional simplex". This is a linear programming problem but of course, if the link is slice it's slice discs may not appear in this triangulation. So you subdivide the triangulation of $D^4$, barycentrically. After enough iterations of this, any slice discs for your link have to appear, by a general position argument / linearization argument.

This could be turned into a semi-useful algorithm if there were useful upper bounds on the number of subdivisions you have to do.

I suppose you could make a similar algorithm for determining if a link is ribbon -- but staying entirely in the realm of triangulations of $S^3$. I believe ribbon discs require subdivision to appear as solutions of the normal surface equations -- i.e. they don't "normalize" so it can't be a straightforward application of normal surface theory. There likely has to be some kind of acceptance that the triangulation will have to get more complicated. Off the top of my head I don't have an example but if such examples haven't been worked out, they should be readily found using Regina.