Well, if you're referring to total languages, then they are Turing complete for all intents and purposes.
Total languages are not immune to the halting problem (or, rather, to its finite generalizations known as "bounded halting"). The classical formulation of the halting problem simply tells you that verifying a program in general is undecidable. But this is simply because a Turing machine is a finite structure that can describe an infinite one. So in some way, the halting problem is undecidable in the same way that finding the maximum or sorting an infinite list doesn't terminate. Yet once the list is finite (or the Turing machine is known to terminate), you then need to ask yourself how hard is it to find the maximum element in a finite list, how hard is it to sort it, and how hard is it to verify a program that is known to terminate? The answers to all these questions are well known, and quite different from one another. Finding the maximum takes Ω(n) (worst-case), sorting is Ω(n lg n), and verification is Ω(|S|), namely at least linear in the number of states the program takes until it terminates (this directly follows from a trivial generalization of the halting problem called "bounded halting"). So sure, total programs are known to terminate, and all we have left to do now to prove them correct is to overcome a super-exponential lower complexity bound... In practice that is just as undecidable as for programs that are not proven to terminate.
And, BTW, the lower complexity bounds for verification of finite state machines written in expressive languages is already PSPACE-complete. There cannot be a useful general programming language with verification bounds that are less than exponential (unless, that is, PSPACE=P); but that is a good thing: verification of total-functional programs is super-exponential. So my point is that even completely general verification of freakin' finite state machines is out of our reach in large-enough programs. It's doubtful you can find a useful computational model that's simpler.
Also, notice that any program could trivially be made total without changing its semantics. Give me a program you want verified, I'll add a decreasing counter starting with 10100 to all its loops/recursions, and now your program is total and you'll never know the difference. Does that make it any easier to verify?
The total-language people know this. They don't claim that this makes practical program verification any easier. In fact, the motivation for totality has nothing to do with program verification but with using C-H to prove general mathematical theorems. Non-termination, as you know, is the same as inconsistencies in those proofs (although not in proofs about programs; non-termination introduces no inconsistency to those). However, some people who are only familiar with the classical formulation of the halting theorem have concluded that totality => no halting problem => verification is possible! This is false, and was abundantly clear even in the 50s. Kurt Gödel, in a letter to von Neumann in 1956, mentions in passing this finite (and obvious) generalization of the halting theorem before raising (for the first time!) the question of P vs. NP.
Which of course remains an open question.
> even completely general verification of freakin' finite state machines is out of our reach in large-enough programs. It's doubtful you can find a useful computational model that's simpler.
Eh, maybe. I find it very hard to reason about finite state machines in programs as a human, so it doesn't surprise me that proving correctness properties about them would be hard. I'm not at all convinced that a general-purpose programming language necessarily includes support for fully general finite state machines.
> Also, notice that any program could trivially be made total without changing its semantics. Give me a program you want verified, I'll add a decreasing counter starting with 10100 to all its loops/recursions, and now your program is total and you'll never know the difference. Does that make it any easier to verify?
Yes - it eliminates the class of errors where one has "implemented" something by an infinite loop. It helps for concrete programs in the same way that it helps for theorems, no?
Technically yes, but as Scott Aaronson says, a universe where P=NP would probably look very different from ours (and PSPACE is harder than NP). In any event, verifying effectively Turing-complete languages (even total ones) is much harder than EXPTIME (and we know that EXPTIME > P).
> I find it very hard to reason about finite state machines in programs as a human
I didn't mean it like that (programming with explicit states). Just a model of computation where the number of states is bounded. Any program with finite memory is a finite state machine. Every language must support at least that.
> it eliminates the class of errors where one has "implemented" something by an infinite loop. It helps for concrete programs in the same way that it helps for theorems, no?
No, because when you prove a program property A you know that you've really proven "A or no-termination". So being able to prove any property is not an inconsistency. This is not the case for mathematical theorems that don't have running time, and where "no termination" is meaningless. If running time is 0, then A just means A, and if A is a contradiction then you have a real problem.
Now, what about eliminating non-termination from programs? Well, you're not really doing that either, because as far as we're concerned, a program that takes 10^100 steps doesn't really terminate at all. One could claim that people are more likely to accidentally write a function that loops forever than one that loops 2^64 times. This may be true, but this again relies on empirical facts rather than general mathematical properties.
In any case, what makes you think that languages like Idris may make verification easy? The few cases of programs verified in this mostly-manual way took years to prove, even for very small and intentionally "dumbed down" code.
Any program is (or can be modeled as) a finite state machine, sure. But useful programs are a small subset of the space of possible finite state machines. It's not beyond hope that we could find a subset that allowed us to write most useful programs but was easier to reason about.
> One could claim that people are more likely to accidentally write a function that loops forever than one that loops 2^64 times. This may be true, but this again relies on empirical facts rather than general mathematical properties.
I am worried about not-terminating-in-reasonable-time (though much less worried than I am about looping forever), but can't we just make that one of the properties we keep track of and prove with the same tools?
> In any case, what makes you think that languages like Idris may make verification easy? The few cases of programs verified in this mostly-manual way took years to prove, even for very small and intentionally "dumbed down" code.
I guess my experience that keeping track of more properties in the type system doesn't make coding any harder. Compare Rust - writing Rust programs essentially means proving that things have valid lifecycles and are not used outside of them. This is a complex property that mainstream programmers were not previously proving at all - that many had despaired of ever being able to prove. And yet in practice people who write Rust find that not only can they do it, but the additional proof effort quickly becomes barely noticeable. Likewise with Idris you're proving termination in finite (though possibly unreasonable) time and once you get used to doing that it doesn't actually seem noticeably harder than not doing so. So I'm kind of hopeful that we can just keep improving the type systems used by mainstream programming languages until writing a program naturally includes proving the important properties of that program without even noticing.
It is beyond hope that we find a subset that's generally easier to reason about. Verifying one line programs of this sort:
if (a && ~b || c || ~d && e ...)
crash()
is already NP-complete (SAT). Adding some loops that are of depth 2 makes it PSPACE-complete (TQBF, aka QSAT). I can't think of a useful programming language that doesn't have even small-constant-depth loops (which makes it finite state) and simple boolean algebra. Software verification is about verifying some subsets of programs that humans happen to write. It is categorically impossible to write a general-purpose language where all programs are easier to verify than PSPACE.> but can't we just make that one of the properties we keep track of and prove with the same tools?
Sure, with super-exponential complexity :) But again, this is in the worst case. We hope that humans usually write programs that are simpler.
> I guess my experience that keeping track of more properties in the type system doesn't make coding any harder.
If you mean H-M types as in Haskell, then the properties those types enforce are either trivial (i.e. true for all programs, e.g. function returns Int), or a result of a finite state machine (that's the proving strength of H-M types). You cannot prove even a single bit of a program's output that's a result of non-constant-depth recursion (there's a special case for recursion which is of depth that's a constant multiple of the input length, like `map`). If we take Haskell, you can replace each of your functions with constant-depth recursion (0 or 1 would suffice in virtually all circumstances) and the program will still typecheck yet will be completely wrong.
As for Rust's linear types, that is precisely what I'm talking about. A certain class of bugs (memory errors) that humans are known to make and that verifying with abstract interpretation is easy. That's what software verification aims to do. We cannot hope of proving general programs generally correct, regardless of the language they're written in.
BTW, thinking of type systems muddles understanding in this case, because type systems are just notation. The verification taking place in most sound type systems is abstract interpretation. Yes, we can find more important properties to verify with abstract interpretation, but it has been proven that some properties will forever elude abstraction.
The way abstract interpretation works is that it translates the program into an "abstract" program which is just a finite state machine, with the number of states equal to the number of concrete types, and running an exhaustive model checker on that; this means that the complexity of inferring this kind of types is Ω(|S|), namely, linear in the number of concrete types. As abstract types can multiply the number of concrete types, the inference can become exponential in the worst-case, but it usually doesn't. Once you introduce dependent types, the algorithm is still Ω(|S|) -- linear in the number of state, i.e. types -- but now the number of types is unbounded, and so the problem becomes undecidable.
> until writing a program naturally includes proving the important properties of that program without even noticing.
You're right, but this entirely depends on which properties are found to be important (and has little to do with type systems specifically; again, this is mostly notation[1]), and that, in turn, is rather empirical.
[1]: Not entirely, though, but mostly.
Eh. Again, I don't think we necessarily need arbitrary boolean algebra - something that's hard enough to reason about as a human - and may be able to capture the valuable use cases in a simpler model. Fundamentally if we have any hope of doing verification at all, surely we can characterize the constraints we need for verification and then push them back to the programming language level.
> If we take Haskell, you can replace each of your functions with constant-depth recursion (0 or 1 would suffice in virtually all circumstances) and the program will still typecheck yet will be completely wrong.
Could you expand on this / give an example? I don't think I follow. And I take it from what you're saying that this doesn't apply if we permit dependent types?
> BTW, thinking of type systems muddles understanding in this case, because type systems are just notation. The verification taking place in most sound type systems is abstract interpretation. Yes, we can find more important properties to verify with abstract interpretation, but it has been proven that some properties will forever elude abstraction.
Properties that are important for real-world programs? Abstract interpretation sounds very similar to how we reason about programs as humans. It just seems like to the extent that we understand how to do something at all we should be able to formalize that understanding.
If we're talking about using programs to address open questions - a best-effort at the travelling salesman problem, say - then I can see how you might end up with a program that had a pile of heuristics that seemed to work but with no concrete understanding of how or if it worked - except that even then you'd probably use a well-known, formally validated heuristic rather than using the program as a medium for mathematical research. I just think (empirically) it would be very rare as a business requirement to need to do something completely unproven, and therefore it might be possible to have a useful general-purpose programming language that didn't allow doing that.
That is not what the verification community is trying to do at all, because trying to find a language that is not even NP-complete to verify and is still generally is absolutely impossible (explanation later). What the verification community is trying to do is to come up with approaches that make it possible/easy to verify some code, which is hopefully the majority of code. As far as languages go, the hope is that a language can make some verification of some code easier than in other languages. A general-purpose language that is at least useful in some cases, and in which all programs are easily verifiable can only exist if P=NP. The reason is this: at best, you can hope that the proof of correctness is checkable in polynomial time. This puts it in NP. If constructing a proof of correctness is possible in polynomial time, so is coming up with the solution in the first place. Namely, such a language wouldn't even need to be programmed. It will be a constraint solver (that somehow is in P). SQL minus boolean expressions might be the best you could do. Possibly useful, but certainly not general-purpose.
> Properties that are important for real-world programs?
Yes, and they are quite common in distributed algorithms.
> It just seems like to the extent that we understand how to do something at all we should be able to formalize that understanding.
Yet we can't because when we reason about something we assume a certain regularity of the state-space, that is often wrong in practice. That link I showed you where there are visualizations of state spaces, shows the one for the CAN bus protocol. It is the most complicated example on that page, and it is the very real protocol used by different components in your car that need to communicate.
> I just think (empirically) it would be very rare as a business requirement to need to do something completely unproven
That depends a lot on what you do. If you design schedulers for OS kernels, concurrent data structures, or distributed algorithms you see that these difficult cases are the rule rather than the exception.
I work on concurrent and distributed algorithms, and I do formal verification (TLA+ is my current tool of choice) most day every day. TLA+ offers both a theorem prover (a la Isabelle/Coq/Agda) as well as a model checker. Manual deductive proofs are virtually never worth the trouble (that would take me years), and even with a model checker -- where you just press a button and if there's a bug, any bug, you get a full trace of the execution that led to the bug -- it's still a lot of work, because distributed algorithms are just essentially complex.
Not true. We know that we cannot create a Turing-complete language with that property. We haven't proven that we'll never be able to create a general-purpose non-Turing-complete language. I might argue that Idris is already an example of such a thing.