> it would be nice to be able to ascertain before running a program, certain time & space complexity bounds on it
I don't know about knowing what "space" a program will consume ahead of time, but I believe the halting problem[1] means there'd be no way of computing a time requirement.
The halting problem assumes a program from a Turing-complete model of computation. Not all computational models are Turing-complete. The parent is pointing out that if you limit yourself to a language or a sub-set of a language that is not Turing-complete, then you can make static assertions about things such as halting.
A trivial example would be a programming language that did not allow any loops or explicit backward branches. You would be able to provide upper bounds on how many operations such programs can perform.
> if you limit yourself to a language or a sub-set of a language that is not Turing-complete, then you can make static assertions about things such as halting
There's already something that is non-Turing complete, but comes with a halting guarantee -- it's called total functional programming[1]. This paper (linked below) is actually what got me thinking about this whole thing. The author argues in it how functions in functional programming languages aren't really like mathematical functions, because they have the possibility to execute infinitely (never halt) and thus not have a proper return value. To mitigate that, he creates "total functional programming".
Total functions are guaranteed to have a return value (i.e. terminate eventually), but they could take very long to run. If we could actually have complexity bounds, or be able to determine a given function's complexity, that would be a great boon to software engineering (i.e. assuming they adopt it... which is a whole different matter).
The author also makes a very good point that most parts of your program are meant to terminate (i.e. the vast set of functions and algorithms that comprise you program). Only the top-level needs to be Turing-complete, the rest can at least be total.
I actually want to see if it's possible to push this concept further, to create a ring-like hierarchy of languages -- the lowest one being the weakest and the one we can extract the most static assertions out of, and so on. There's a language called Hume[2] that sounds like it accomplishes at least part of this goal, but I haven't really looked into it.
I don't know about knowing what "space" a program will consume ahead of time, but I believe the halting problem[1] means there'd be no way of computing a time requirement.
[1] http://en.wikipedia.org/wiki/Halting_problem