4 ms·
Right. But it is important to understand that this is the hardest problem in computer science (human-level AI is much easier), and so general-enough solutions m
by pron 11y ago
Right. But it is important to understand that this is the hardest problem in computer science (human-level AI is much easier), and so general-enough solutions must somehow be aligned with how humans tend to construct programs (because a completely general solution is impossible, and solutions that are not aligned with how people program can only hope to solve human-produced code by accident). For example, we do know that we cannot create a general-purpose language that will make verification easy for all programs written in it; that is a mathematical impossibility. Whatever approach may work one day, it will have to be based on empirical observations of programs people tend to write.
- lmm 11y ago> For example, we do know that we cannot create a general-purpose language that will make verification easy for all programs written in it; that is a mathematical impossibility. 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.
- pron 11y ago> We haven't proven that we'll never be able to create a general-purpose non-Turing-complete language. 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.
- lmm 11y ago> unless, that is, PSPACE=P 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?
- pron 11y ago> Which of course remains an open question. 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.