&gt; If we do, then we have to consider whether we want our equality to distinguish terminating and non-terminating programs.<p>But this is what bugs me. As someone working on algorithms (and does not care as much about semantics and abstractions), the algorithm&#x27;s correctness is only slightly more important than its complexity. While there are (pragmatic) reasons to care about proving partial correctness more than total correctness (or prioritizing <i>safety</i> over <i>liveness</i> in algorithmists&#x27; terms), it seems funny to me to almost completely sweep complexity -- the mother of all effects, and the one at the very core of computation -- under the rug. Speaking about total functions does us no favors: there is zero difference between a program that never terminates, and one that terminates one nanosecond &quot;after&quot; the end of the physical universe. Semantic proof of termination, then, <i>cannot</i> give us any more <i>useful</i> information than no such proof. Just restricting our computational model from TM to total-FP doesn&#x27;t restrict it in any useful way at all! Moreover, in practical terms, there is also almost no difference (for nearly all programs) between a program that never terminates and one that terminates after a year.<p>Again, I fully understand that there are <i>pragmatic</i> reasons to do that (concentrate on safety rather than liveness), but pretending that there is a <i>theoretical</i> justification to ignore complexity -- possibly the most important concept in computation -- in the name of &quot;mathematics&quot; (rather than pragmatism) just boggles my mind. The entire notion of purity is the leakiest of all abstractions (hyperbole; there are other abstractions just as leaky or possibly leakier). But we&#x27;ve swayed waaaay off course of this discussion (entirely my fault), and I&#x27;m just venting :)