# Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings...

From the ad-hoc methods I came with the following intuitive idea. Is it possible to formalize termination with algebraic topology? The idea would be:

• look at termination as the problem of finding loops in the code of the program.

• look these loops as a fundamental group at some origin (a point in the source code)

• test whether this fundamental group is simply connected (implying that this node is terminating)

Of course both problems are undecidable (the second one being testing the simple connectedness) but it seems to me theoretically feasible.

Has this been done before? You find it is not feasible?

Resources I find interesting (feel free to add)

Power domains and predicate transformers: A topological view (if I ever get access to it)

The topology of program termination.

Scott approach distance on metric spaces

• Have a look at Eric Goubault's work. Aug 1, 2018 at 0:24
• One issue to keep in mind is that a returning to the same line of code only implies an infinite loop if the state of the memory is the same both times. One of the tricky things about detecting non-halting behavior is that it can occur even when the state of the memory itself never loops. Whether or not this kind of behavior occurs in practice is, of course, a separate question. Aug 1, 2018 at 16:55
• @JoshuaGrochow do you think this is mitigated in the functional context (which is the one I am interested in)? Aug 4, 2018 at 23:18
• @Rodrigo: no, it is not, since in the functional context the "state of the memory" is simply the values of the arguments of the recursive calls, which in many cases will never be identical in a non-terminating sequence (imagine a definition of factorial without a base case).
– cody
Aug 6, 2018 at 13:23
• @Rodrigo It's true, Eric's work is mostly about concurrency. His key intuition is that deadlocks in concurrency correspond to holes in algebraic topology. But one needs to generalise algebraic topology to directed algebraic topology in order to make this work. I think the need for directedness doesn't go away in a purely sequential setting. Also: sequential computation is a special case of concurrency. Aug 22, 2018 at 10:19