<p>One way to answer this is to consider the computational complexity of the decision problems for the classes of partial correctness and termination queries that are known to be decidable.  Abstract interpretation using the polyhedral domain can infer the partial correctness annotations you mention in cases where the required annotations are conjunctions of linear inequalities.  Computing the abstract post-condition is exponential in the number of variables.  Then there is the overhead of finding the fixed point.  See Cousot's early papers for more on this and the Apron library if you want to play with it directly.</p>

<p>Finding variant functions is decidable when the variant functions are linear.  I couldn't find a complete characterization of the complexity of this, but "Termination of Linear Programs" by Tiwari has a section that discusses complexity.  See also "A Complete Method for the Synthesis of Linear Ranking Functions" by Podelski and Rybalchenko.  Also, Byron Cook has done work on leveraging abstract interpretation to help construct termination arguments.  See, for example, "Ranking Abstractions" and "Variance Analyses from Invariance Analyses".  These may give further insight into the relationship between partial correctness and termination.</p>

<p>Links:</p>

<ul>
<li><a href="http://www.csl.sri.com/users/tiwari/html/cav04.html" rel="nofollow">http://www.csl.sri.com/users/tiwari/html/cav04.html</a></li>
<li><a href="http://www7.in.tum.de/~rybal/papers/vmcai04-linear-ranking.pdf" rel="nofollow">http://www7.in.tum.de/~rybal/papers/vmcai04-linear-ranking.pdf</a></li>
<li><a href="http://www.dcs.qmul.ac.uk/~hyang/paper/esop08.pdf" rel="nofollow">http://www.dcs.qmul.ac.uk/~hyang/paper/esop08.pdf</a></li>
<li><a href="http://research.microsoft.com/terminator/popl07a.pdf" rel="nofollow">http://research.microsoft.com/terminator/popl07a.pdf</a></li>
</ul>

CC BY-SA 2.5
2011-02-02T08:33:00.597Z
I hope you don't mind my editing your answer and making the links active.
Andrej Bauer
CC BY-SA 2.5
2010-08-23T20:43:01.143Z
2011-02-02T09:33:12.323Z
2011-02-02T09:33:12.323Z
Stephen Magill
<p>There's an obvious reduction from <em>necessary non-termination</em> to partial correctness, namely:</p>

<p><em>P</em> never terminates when started in an initial state satisfying <i>&phi;</i> iff {<i>&phi;</i>} <em>P</em> {false} is valid.</p>

<p>I am aware that this is another non-answer. Its advantage is that it is shorter than those above.</p>

CC BY-SA 2.5
2011-02-02T05:02:45.127Z
2011-02-02T05:02:45.127Z
Kai
<p>There's a standard technology – usually undecidable, of course – for populating your graph with its pre- and post-conditions, namely <a href="http://en.wikipedia.org/wiki/Predicate_transformer_semantics#Weakest_liberal_precondition" rel="nofollow">weakest liberal precondition semantics</a>, which is a form of predicate transformer semantics that gives weakest preconditions for either satisfaction of the specification or non-termination.  This essentially is a complete theory of partial correctness for such languages, and, indeed, full correctness</p>

<p>It's chalk and cheese deciding which of termination and partial correctness is where the hard work lies, since both are so badly undecidable.  But partial correctness is tangled up with language design issues, both for program and specification languages, whilst the difficulty of termination is of a clean sort: for any theory used for proving termination there will be algorithms that terminate, but connot be proven to terminate relative to that theory.  For example, computations in <a href="http://en.wikipedia.org/wiki/System_F" rel="nofollow">the pure polymorphic lambda calculus</a> must terminate, but Peano arithmetic cannot prove this.</p>

<p>My impression is that the work on <a href="http://www.di.ens.fr/~cousot/AI/" rel="nofollow">abstract interpretation</a> pioneered by Patrick Cousot, has been the most dynamic in this area, but I don't pretend to be an expert.</p>

CC BY-SA 2.5
2010-08-24T12:34:26.133Z
I was trying to ask about the complexity of inferring variant functions. Sorry for not being clear! As a curiosity, Rustan Leino came up with an example last evening (in a pub) that strongly suggested to me that wlp doesn't work as well as wp&sp for the kind of programs I describe here. I'll have to double check when I get to a place more suitable for work :)
Radu GRIGore
CC BY-SA 2.5
2010-08-24T12:37:34.550Z
@Radu: There's work been done on automatic termination proofs, with some nice work being done for Prolog.  I can dig up some refs when I find time.
Charles Stewart
CC BY-SA 2.5
2010-08-23T12:42:05.790Z
2010-08-23T12:42:05.790Z
Charles Stewart
<p>If you are familiar with program verification you are likely to prefer reading the <strong>Question</strong> before the <strong>Background</strong>. If you are not familiar with program verification then you may still be able to answer this question, but you are likely to prefer reading the <strong>Background</strong> first.</p>

<h2>Background</h2>

<p>It is often stated that checking partial correctness is undecidable. For the sake of discussion, let's pick one very particular way of making this statement precise, in the style of Floyd--Hoare. A <em>flowgraph</em> is a digraph with a distinguished <em>initial node</em> from which all nodes are reachable. A <em>program</em> is a flowgraph whose nodes are commands. There are three types of commands (1) assumptions <strong>assume</strong> <em>q</em>, (2) assertions <strong>assert</strong> <em>q</em>, and (3) assignments v:=e. Here <em>q</em> is a fol (first-order logic) formula, <em>e</em> is a fol term, and <em>v</em> is a variable.</p>

<p>We say that a program is <em>partially correct</em> when there is a way to annotate each node <em>x</em> with a precondition <em>a(x)</em> and a postcondition <em>b(x)</em> such that (1) the precondition of the initial node is valid, (2) {<em>a(x)</em>} <em>x</em> {<em>b(x)</em>} holds for all commands <em>x</em>, and (3) (<em>b(x)</em> implies <em>a(y)</em>) is valid for all edges from <em>x</em> to <em>y</em>. Here the Hoare triples are defined as follows:</p>

<ul>
<li>{<em>p</em>} <strong>assert</strong> <em>q</em> {<em>r</em>} means that (<em>p</em> implies (<em>q</em> and <em>r</em>)) is valid</li>
<li>{<em>p</em>} <strong>assume</strong> <em>q</em> {<em>r</em>} means that ((<em>p</em> and <em>q</em>) implies <em>r</em>) is valid</li>
<li>{<em>p</em>} v:=e {<em>r</em>} means that ((<em>p</em> with <em>e</em> substituted for <em>v</em>) implies <em>r</em>) is valid</li>
</ul>

<p>Here's a hand-wavy argument of why checking <em>this</em> partial correctness is undecidable: Once you fill in some <em>a(x)</em> and some <em>b(x)</em> you need to check if some fol formulas are valid, and that is undecidable.</p>

<p>A typical way to encode termination in partial correctness is to add some special assertions that essentially say "since last time I was executed, there was progress towards termination." These <em>progress assertions</em> must be placed such that all infinite walks on the flowgraph (that start at the initial node) contain infinitely many progress assertions. To be more specific, let's say that progress assertions always have the form <strong>assert</strong> <em>u</em> &lt; <em>v</em>, where <em>u</em> and <em>v</em> are positive integers, are preceded by the assignment <em>u</em>:=<em>f</em>, and are followed by the assignment <em>v</em>:=<em>u</em>. Here <em>f</em> is a <a href="http://en.wikipedia.org/wiki/Loop_variant" rel="nofollow">variant function</a>, <em>u</em> is its current value, and <em>v</em> is its former value. Now, since we talk about "positive integers" and we compare them, we need to ensure that a bit more than fol is available: Let's say <a href="http://en.wikipedia.org/wiki/Peano_axioms" rel="nofollow">Peano arithmetic</a> is available. (I don't feel strongly about this choice. Feel free to disregard if convenient.) Of course, <em>f</em> may use any other functions and constants that are mentioned in the program. (Note that adding assumptions at the beginning of the program is equivalent to introducing non-logical axioms.)</p>

<p>Now, if the program with progress assertions is still partially correct, then we know that the original program terminates.</p>

<h2>Question</h2>

<p>Given a terminating program, it feels that coming up with variant functions for progress assertions is hard. But how hard? (I know that even with the huge background above, I still left this question sort of open-ended, or ill-defined, depending on how you want to look at it.)</p>

<p>To put it differently: I'm looking for a reference that formalizes the problem of reducing termination to partial correctness and then says something about its complexity. An answer that does all this would of course be welcome.</p>

CC BY-SA 2.5
2010-08-31T18:48:46.267Z
Let me check whether I understand this. What you are asking for would give us, among other things, an algorithm which takes a program that computes a total recursive function and outputs a proof of a statement that the function is total (in the form of variant functions and proofs that they are suitable)? That sounds awfully uncomputable to me.
Andrej Bauer
CC BY-SA 2.5
2010-09-01T09:12:49.640Z
Andrej, it sounds uncomputable to me too. What I'm asking for is a proof that it is uncomputable.
Radu GRIGore
<cc.complexity-theory><lo.logic><program-verification><program-logic>
How hard is it to reduce termination to partial correctness?
Radu GRIGore
# How hard is it to reduce termination to partial correctness?

(Asked by: username_0 on 2010-08-18)

If you are familiar with program verification you are likely to prefer reading the **Question** before the **Background**. If you are not familiar with program verification then you may still be able to answer this question, but you are likely to prefer reading the **Background** first.

## Background

It is often stated that checking partial correctness is undecidable. For the sake of discussion, let's pick one very particular way of making this statement precise, in the style of Floyd--Hoare. A *flowgraph* is a digraph with a distinguished *initial node* from which all nodes are reachable. A *program* is a flowgraph whose nodes are commands. There are three types of commands (1) assumptions **assume** *q*, (2) assertions **assert** *q*, and (3) assignments v:=e. Here *q* is a fol (first-order logic) formula, *e* is a fol term, and *v* is a variable.

We say that a program is *partially correct* when there is a way to annotate each node *x* with a precondition *a(x)* and a postcondition *b(x)* such that (1) the precondition of the initial node is valid, (2) {*a(x)*} *x* {*b(x)*} holds for all commands *x*, and (3) (*b(x)* implies *a(y)*) is valid for all edges from *x* to *y*. Here the Hoare triples are defined as follows:

* {*p*} **assert** *q* {*r*} means that (*p* implies (*q* and *r*)) is valid
* {*p*} **assume** *q* {*r*} means that ((*p* and *q*) implies *r*) is valid
* {*p*} v:=e {*r*} means that ((*p* with *e* substituted for *v*) implies *r*) is valid

Here's a hand-wavy argument of why checking *this* partial correctness is undecidable: Once you fill in some *a(x)* and some *b(x)* you need to check if some fol formulas are valid, and that is undecidable.

A typical way to encode termination in partial correctness is to add some special assertions that essentially say "since last time I was executed, there was progress towards termination." These *progress assertions* must be placed such that all infinite walks on the flowgraph (that start at the initial node) contain infinitely many progress assertions. To be more specific, let's say that progress assertions always have the form **assert** *u* < *v*, where *u* and *v* are positive integers, are preceded by the assignment *u*:=*f*, and are followed by the assignment *v*:=*u*. Here *f* is a [variant function](http://en.wikipedia.org/wiki/Loop_variant), *u* is its current value, and *v* is its former value. Now, since we talk about "positive integers" and we compare them, we need to ensure that a bit more than fol is available: Let's say [Peano arithmetic](http://en.wikipedia.org/wiki/Peano_axioms) is available. (I don't feel strongly about this choice. Feel free to disregard if convenient.) Of course, *f* may use any other functions and constants that are mentioned in the program. (Note that adding assumptions at the beginning of the program is equivalent to introducing non-logical axioms.)

Now, if the program with progress assertions is still partially correct, then we know that the original program terminates.

## Question

Given a terminating program, it feels that coming up with variant functions for progress assertions is hard. But how hard? (I know that even with the huge background above, I still left this question sort of open-ended, or ill-defined, depending on how you want to look at it.)

To put it differently: I'm looking for a reference that formalizes the problem of reducing termination to partial correctness and then says something about its complexity. An answer that does all this would of course be welcome.

**Tags:** cc.complexity-theory, lo.logic, program-verification, program-logic

> **Comments:**
> **username_1**: Let me check whether I understand this. What you are asking for would give us, among other things, an algorithm which takes a program that computes a total recursive function and outputs a proof of a statement that the function is total (in the form of variant functions and proofs that they are suitable)? That sounds awfully uncomputable to me.  
> **username_0**: Andrej, it sounds uncomputable to me too. What I'm asking for is a proof that it is uncomputable.  

---

## 3 answers

### Answer by username_2 on 2010-08-23. Score: 7

One way to answer this is to consider the computational complexity of the decision problems for the classes of partial correctness and termination queries that are known to be decidable. Abstract interpretation using the polyhedral domain can infer the partial correctness annotations you mention in cases where the required annotations are conjunctions of linear inequalities. Computing the abstract post-condition is exponential in the number of variables. Then there is the overhead of finding the fixed point. See Cousot's early papers for more on this and the Apron library if you want to play with it directly.

Finding variant functions is decidable when the variant functions are linear. I couldn't find a complete characterization of the complexity of this, but "Termination of Linear Programs" by Tiwari has a section that discusses complexity. See also "A Complete Method for the Synthesis of Linear Ranking Functions" by Podelski and Rybalchenko. Also, Byron Cook has done work on leveraging abstract interpretation to help construct termination arguments. See, for example, "Ranking Abstractions" and "Variance Analyses from Invariance Analyses". These may give further insight into the relationship between partial correctness and termination.

Links:

* <http://www.csl.sri.com/users/tiwari/html/cav04.html>
* <http://www7.in.tum.de/~rybal/papers/vmcai04-linear-ranking.pdf>
* <http://www.dcs.qmul.ac.uk/~hyang/paper/esop08.pdf>
* <http://research.microsoft.com/terminator/popl07a.pdf>

> **Comments:**
> **username_1**: I hope you don't mind my editing your answer and making the links active.  

---

### Answer by username_3 on 2011-02-02. Score: 4

There's an obvious reduction from *necessary non-termination* to partial correctness, namely:

*P* never terminates when started in an initial state satisfying *φ* iff {*φ*} *P* {false} is valid.

I am aware that this is another non-answer. Its advantage is that it is shorter than those above.


---

### Answer by username_4 on 2010-08-23. Score: 3

There's a standard technology – usually undecidable, of course – for populating your graph with its pre- and post-conditions, namely [weakest liberal precondition semantics](http://en.wikipedia.org/wiki/Predicate_transformer_semantics#Weakest_liberal_precondition), which is a form of predicate transformer semantics that gives weakest preconditions for either satisfaction of the specification or non-termination. This essentially is a complete theory of partial correctness for such languages, and, indeed, full correctness

It's chalk and cheese deciding which of termination and partial correctness is where the hard work lies, since both are so badly undecidable. But partial correctness is tangled up with language design issues, both for program and specification languages, whilst the difficulty of termination is of a clean sort: for any theory used for proving termination there will be algorithms that terminate, but connot be proven to terminate relative to that theory. For example, computations in [the pure polymorphic lambda calculus](http://en.wikipedia.org/wiki/System_F) must terminate, but Peano arithmetic cannot prove this.

My impression is that the work on [abstract interpretation](http://www.di.ens.fr/~cousot/AI/) pioneered by Patrick Cousot, has been the most dynamic in this area, but I don't pretend to be an expert.

> **Comments:**
> **username_0**: I was trying to ask about the complexity of inferring variant functions. Sorry for not being clear! As a curiosity, Rustan Leino came up with an example last evening (in a pub) that strongly suggested to me that wlp doesn't work as well as wp&sp for the kind of programs I describe here. I'll have to double check when I get to a place more suitable for work :)  
> **username_4**: @Radu: There's work been done on automatic termination proofs, with some nice work being done for Prolog.  I can dig up some refs when I find time.  

---

