Thoughts on Turing-completeness

Writing this sparse matrix calculator has gotten me thinking about software tools and Turing-completeness.  The sparse calculator, at least as originally conceived, wasn't meant to be a a general-purpose computing tool.  It was simply meant to do some simple computations with sparse matrices: mainly find the eigenvalues and solve matrix equations.

It seems to be the fate, however, of just about every software tool (especially mini-languages) to acquire, at some point, the trappings of a full-featured programming language.  Suppose you want to write your own solver or eigenvalue routines instead of just using using built-in functions?  At the very least this will require iteration capability and the ability to exit from that iteration based on some criterion.

The complexity required for Turing-completeness is surprisingly low.  I'm wondering at what point the sparse calculator will acquire it--or perhaps it has already with the addition of vector-subscripting and subscript assignment?  In the course of the minimal research I've performed, one thing that comes up repeatedly is this idea of non-halting programs.  After all, one of the properties of a Turing-complete Turing-machine is halting theorem: that no general algorithm exists that can prove with certainty whether a program on a Turing-complete machine halts or not.

First of all, I've always thought that halting theorem was over-emphasized.  After all, human programmers write programs that halt all the time and they can frequently determine whether a program halts or, if it does not, why.  Just because you cannot prove whether or not some programs halt, does not mean that you should not do the work for those that are less pathological, i.e., that are easy to classify.  Typically these less pathological cases will be the ones of interest anyway, that is, more real world as opposed to "of theoretical interest."  The problem is equivalent to that of automated theorem proving.  There is plenty of work being done and plenty of software in that area, even though theorems exist that are unproveable.

It's obvious that being capable of non-halting behaviour is a necessary, not sufficient, condition of being Turing-complete.  But I question this as well: couldn't we have languages that are, for all intents-and-purposes, Turing-complete, yet still always halt?  In array-based languages such as APL, MatLab, Interactive Data Language and many others, you can do a lot of both the iteration and conditionals using array operations.  And at least in IDL, you ought to because it is more efficient: array operations are built-in while loops and other control-of-flow operations are interpretted from byte code.  Since arrays always have a finite length, this implies that any array operation will ultimately halt.  I find I like the idea of element-by-element comparison, array element selection and similar mechanisms since these have more of a declarative feel.  I remember being disappointed by the control structures in Awk, because while in concept the language had a strongly declarative feel, the control structures simply aped those of common imperative languages.