[Agda] Theoretical limits of termination checking (reference request)

[Altenkirch Thorsten]

This is a good question.

If we restrict ourselves to Agda w.o. codata and sized types then Agda only recognizes programs whose termination order is the lexical product of the structural order of datatypes. Let’s call such programs structurally recursive. However, the set of structurally recursive programs is not decidable and Agda only recognizes those which are “guarded on the left”.  Now one concrete question would be wether any structurally recursive program can be transformed into an equivalent one which is guarded. I suspect the answer is no, because even though a program is semantically structural this may not be provable within Agda.

Any thoughts?

Thorsten

From: Kirill Elagin <kirelagin at gmail.com<mailto:kirelagin at gmail.com>>
Date: Tue, 29 Jul 2014 22:26:37 +0100
To: "agda at lists.chalmers.se<mailto:agda at lists.chalmers.se>" <agda at lists.chalmers.se<mailto:agda at lists.chalmers.se>>
Subject: [Agda] Theoretical limits of termination checking (reference request)

Hello,

I was going through the great articles by Andreas Abel and I suddenly started asking myself very basic questions about theoretical limits of termination checking. The halting problem is often cited as an explanation for impossibility of sound&complete termination checker. The termination checking problem is not exactly the halting problem, but indeed it is quite easy to derive impossibility of general termination checking from impossibility of solving the halting problem.

But then, another question arises. When we encode proofs, say, in Agda, we often have a terminating program in mind, but we have to write it down in some specific way, so that the termination checker “sees” that the program is fine. So, is it possible to develop a “programming style” such that there is a sound&complete termination checker for programs “written in this style”, _and_ any program can be “written in this style” (the “translation” function is obviously not computable)? Formally: is there a subset of programs, such that there is an algorithm correctly checking termination of programs from this subset _and_ for any program there is an equivalent in this subset (by “equivalent” I mean “extensionally equal”)?
I used to think that it is impossible, but I recently realized that my “proof” was wrong. Turns out that when we are working with the whole universe of programs, undecidability of termination checking follows from undecidability of the halting problem. But if we restrict ourselves to a subset, it is no longer necessarily true, and sound&complete termination checking (for programs from this subset) _is_ possible for some subsets.

Then, there are more questions. How good can we become at translating arbitrary programs to equivalents from some of those good subsets? As I said, the translation function is clearly not computable. But can it be that it is not computable only for programs we don't care about? Or maybe it is not computable by algorithms, but computable by human brains? Are any of the existing means of checking termination already “perfect” in this sense, that is can I write _any_ terminating function, say, in MiniAgda, so that it passes the termination check?
I haven't come up with any answers to those ones yet.

For some reason I couldn’t find any information on this topic. I guess that either those questions are so trivial and the answers to them are so obvious that no one even bothers to write them down, or everything about this was published long ago in 70s, so it’s somewhat difficult to find those papers now.
I feel that negative results are most likely to come from the computability theory, while positive ones—from more specific fields.

Is there an ultimate source of this kind of funny, useless, purely theoretical facts?

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it.   Please do not use, copy or disclose the information contained in this message or in any attachment.  Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.



This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system, you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.









-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20140731/59cf8b44/attachment-0001.html