On the importance of Turing completeness

In taking a graduate class in theoretical computer science, I developed a question that was never answered in a way that I felt comfortable with accepting, and now I can't stop thinking about it.

We discussed that most computer languages are Turing complete, but did not discuss why that is necessary. When I asked, I got an answer of the type: because there are problems only solvable by Turing complete languages. Yet, I feel no examples coming immediately to mind. Pushdown-automata or stacks are always decidable, and there is an enormous amount of problems that can be solved using them. Also, very many practical problems can be solved in the form of a graph. Yet, many other problems can be solved with primitive recursion which is also decidable.

So, I still feel like I am missing something; what are the practical benefits of making a language Turing complete? Or to ask another side of the question: what practical benefits would be lost by not being Turing complete?

Any help on this one, I would tremendously appreciate.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Here's a concrete example of

Here's a concrete example of an interesting semi-decidable problem: full intuitionistic first-order predicate logic. You can write a theorem prover that will always find the proof of a proposition P, if it is in fact true. However, there's no way to make this complete: there's no way to ensure that the theorem prover will halt if P is not provable. (If it were, then you could solve the Halting problem.)

So a complete theorem prover for FOL has to be written in a Turing-complete language.

So a complete theorem

So a complete theorem prover for FOL has to be written in a Turing-complete language.

That's not actually true. Consider a language consisting of only one valid program - "RunFOLTheoremProver()" - with appropriate semanics :). There are also less trivial examples.

This is Turing-complete!

This is a sufficient primitive to write an interpreter for any other Turing complete language. What you do is say "If the reduction predicate Eval(x,y) for language L is foo, then does there exist an x such that Eval(p, x) holds for program P?" Then, if the prover returnss a proof, then you can look at x to figure out what that program P evaluated to. If the prover never returns, then the program must have gone into an infinite loop. It won't be efficient, but it will work....

Hmmm

Well I guess you have a point. I was too busy trying to be flip to think it through :/.

Writing an interpreter

One can write an interpeter for an Turing-complete language in a Turing-complete language. You can, obviously, write an interpreter for something less than Turing-complete in a Turing complete langauge.

However, less powerful formalisms are generally incapable of self-interpretation. You cannot create a "universal state machine"--a device which takes as input a "program" (for state machines, a regex or some other means of specifying an arbitrary regular language), followed by input strings to match against that language--using a state machine.

Likewise, you cannot write an intepreter for a primitive-recursive language using a primitive-recursive language; you need full recursion.

This paper may be of interest; it covers the relevant computational theory and its consequences.

That said...

despite the fact that there are indeeed practical problems (not just theoretical exercises like computing Ackerman's function) that require full-Turing-completeness...

there are many that do not, and benefit from decideability.

Consider the advice of Sir Tim Berners-Lee, expressed as the Principle of Least Power. Also consider the similar (and excellent) advice by LtU's own Peter Van Roy in Concepts, Techniques, and Models of Computer Programming, although in the context of choosing a declarative vs an imperative programming model/language. PVR advises choosing more declarative models when you can, the less declarative models (which are more expressive, but harder to reason about) when you have to. (If I have misquoted you Peter--I don't have my copy of CTM handy to browse here at work--please correct me).

Ackerman Termination

Charity was an interesting exercise in non-Turing complete programming languages that is capable of expressing the Ackerman function. Alas, it seems to have not been active over the last 10 years. Though it would be of interest to anyone interested in seeing how far one can take a non-TC language.

Why Turing Completeness?

There's a practical argument as well. It's usually much easier and more natural to express an algorithm using general recursion than primitive recursion or another sub-Turing language that guarantees termination. A trivial example is the factorial function; you can write it using primitive recursion, but the excercise is a lot more intuitive with general recursion.

Most programming in languages guaranteed to terminate reduces to writing programs in a very convoluted way so as to prove that they terminate. Turing-complete languages have no such burden, so you can just write your algorithm directly.

Also why Turing incompleteness.

Conversely, this is also why languages where programs are guaranteed to terminate may be useful in proof systems / dependent types / static verification. If you are going to accept code of type "program that produces a proof of X when run" as proof of X you had better show that the program will actually terminate. If you need the termination proof anyway it is hopefully easier to bend the algorithm a bit so it is "obviously" terminating rather than also providing a completely independent termination proof (though you can usually do that if necessary, with well-founded recursion).

random algorithms, iterate-until-done algorithms

Here's a couple more examples of algorithms that would be annoying to write in a language where all computations provably terminate.

Consider this plausible algorithm to give a uniformly distributed random number <200, given a source of uniformly distributed random bytes:

def random_lt_200():
    while True:
        v = get_random_byte()
        if v < 200: return v

In practice, this will terminate very quickly; but if get_random_byte returns truly random numbers, this may not terminate at all (although it will terminate with probability 1). If get_random_byte() returns pseudo-random numbers with a reasonable generator, then this probably can be proved to terminate with pencil and paper, but the proof may not be simple enough to encode in your language (depending on where the non-Turing-completeness comes from).

As another example, consider the Simplex algorithm for linear programming. This starts with an initial solution, then incrementally improves the solution until it reaches the final, optimal answer. This could be written in a non-Turing-complete language by computing an upper bound on the number of improvement iterations required, and then iterating at most that many times, but this has a couple of problems: 1) this upper bound is not an interesting number, so computing it and maintaining a loop counter is wasted work and clutters the code; and 2) you have to write code to deal with the loop ending without finding a solution, even though this can never happen.

On the other hand, sub-Turing-complete languages are very interesting, and can be useful in their niches. I have a programming language design in my head where the core language is sub-Turing-complete (basically Haskell with only primitive recursion), but Turing completeness is restored with a Nontermination monad that allows general looping.

"Natural" programming languages are Turing-complete

At least imperative ones.

If your programming language permits unbounded recursion or loops, then its Turing-complete.

Generally, the languages which are not Turing-complete are not things like BlooP (a non-Turing complete, though primitive recursive, language in imperative style developed by Douglas Hofstadter as a pedagogical exercise)--but data-declarative languages which support limited transforms/queries on the data. The query subset of SQL is not Turing complete, but still highly useful.

Right. To put it more

Right. To put it more bluntly: Turing-completeness is very easy to get when designing a language; non-TC requires more careful thought.

well, not quite...

You also need to be able to compute with an unlimited amount of data.

I don't think standard C lets you deal with an arbitrarily large amount of memory (memory is accessed via pointers, and the number of distinct pointers you can have is limited because they are interconvertible with the fixed-size integral type intptr_t). Presumably the inclusion of file I/O does allow standard C to be Turing-complete.

C pointers can be arbitrarily large

There is a requirement that they be convertible to type "long int" and back, but you can create a C dialect with 1024-bit pointers, if you like--sufficient to uniquely address any atom in the universe, and then some. The fact that (void *) is 4 or 8 bytes on most machines is a mere concession to practicality.

Of course, *no* practical (constructible) computing device is Turing-complete, if we are that picky; all machines ever built have a finite amount of memory, after all. Which doesn't seem to be a limitation in practice--any algorithm that terminates will by necessity consume a bounded amount of memory. Fork bombs may (attempt) to consume an infinite amount of memory--but they don't terminate--at least until the OOM killer zaps 'em.

On a practical level

On a practical level, it's much easier for those of us that are at the subgenius level to actually get our work done. Sure there are DSL's and sub-turing languages that allow us to get things done. And a more comprehensive set of languages are always welcomed for specialty tasks. But there is still a lot of territory that is much easier to travel in Turing complete languages.

To take a practical example - SQL. SQL is a very useful language for getting at the data (warts and all). But it has it's limitations. Either you get around those limitations via stored procs (PL/SQL, T-SQL, etc). Or you dive off into a different programming language. The practical question is whether we could keep the determinism of SQL without having to resort to more powerful languages? And if we designed a non-Turing query language that could do all the things we do in stored procs or Java/C#, is it possible for an average programmer to get work done.

On a different note, modularity is also an important concern - the main thrust of any software engineering. We can not tackle problems as one gigantic equation to be solved. We must be able to build it up from pieces of smaller solutions. So any idea on practicality has to incorporate the idea of the open-closed principle. We must be able to isolate things in the small.

Another point with SQL

Would all those query optimizers--a key feature of RDBMS's that make SQL practical to use (it's easy to write queries that, if implemented naively, would take a jakillion years to complete on even the fastest server)--still be possible if SQL didn't limit itself to a logical foundation (predicate calculus) that wasn't Turing-complete?

Probably not.

(This is in general the downside of many declarative languages--they have logical semantics which is well-defined and well-controllable by the user, but the operational semantics are poorly-defined and difficult to control. Whereas full-blown imperative languages typically have operational semantics that the user can control--meaning the programmer can exert a great deal of influence over factors such as performance--but poorly-defined or nonexistant logical semantics).

Fighting the optimizer

As one who spends way too much time cleaning up SQL statements, there is much trivia to be found in guessing how to outsmart the database optimizers. They can be quite fussy at times when you hit the borders of their limits. The expert SQL programmers still have to exert control over the performance, but in a different fashion.

But, yes, the optimizers would have a very tough go if the ceiling were removed.

So, I still feel like I am

So, I still feel like I am missing something; what are the practical benefits of making a language Turing complete? Or to ask another side of the question: what practical benefits would be lost by not being Turing complete?

I think this is a little bit like asking "What are the practical benefits of having a complete car?" It's easiest to answer if we know which part you're thinking of removing. Each of the decidable systems you mentioned has serious limitations that would make it unsuitable for general computation. You can do alot better (like taking a Turing language and restricting to the portion that can be proved total in ZFC with plenty of inaccessible cardinals), but that will require significant programmer help and/or be unusably slow (edit: to compile).

That's Coq

Sets in Types, Types in Sets shows more or less that the calculus of constructions with a given number of universes is equivalent to ZFC with some other number of inaccessible cardinals. Or, that Coq is basically such a language (and type checking is generally only slow where the automation has produced big terms)

Ya, I actually just read

Ya, I actually just read that paper a few months ago. Coq is an example that falls into the burdensome to use category -- programmers supply most of the proofs. If the programmer is not obligated to provide such complete proofs, checking will get slow.

Turing completeness is overrated

We can divide computation in two groups: those that are supposed to terminate (i.e. algebraic) and those that may not terminate but must do something useful as they go (i.e. coalgebraic, and this property is called productivity). It's very hard to find examples of programs (that are useful, common and aren't theorem provers) that aren't supposed to either terminate or be productive. The main problem isn't writing programs that terminate or are productive but convincing the compiler that the code we wrote has one of these properties, that's the primary reasons why we use Turing complete languages.

Also as a general rule of thumb we can always convert an undecidable program to a provably terminating one by defining a maximum amount of time before timeout, it can even be arbitrarily high, and the vast majority of useful programs are supposed to do what we want in a finite amount of time. A similar trick can be done for programs that we don't know if are productive. In a sense I prefer languages that lack Turing completeness because they allow me to understand the programs better: if a function provably terminates it's easier to reason about the program that uses it. OTOH I agree with many of the above comments: it's usually painful to write certain algorithms without being able to use general recursion. The usual strategies is relying on well known combinators that are proved, fall back to folds and unfolds when they are insufficient and ask for help if this doesn't work. The quality of a language without Turing completeness can be measured by how much work you can do before asking for help ;)

Even theorem provers...

Arguably, theorem provers are being productive - they're exhausting more and more of the search space. And I'd argue that they should be structured as such, exposing their partiality at top level rather than there being some function call findProof() that might hang. They should probably even be visibly productive, displaying their progress to the user and responding to a user request for termination. I think the *only* good reason to allow nontermination in a language is to avoid having to bother to prove that things terminate.

A relevant quote

"> So are you saying that you can determine in advance whether the program will
 > terminate?  If so, how?

   Can you? If not, why are you writing this program?"
 - Matthias Blume

Context?

That's a great quote. Do you have it in its original context?

Google is your friend

It's from this thread.

Google doesn't ignore last names

In fact, I did google for it, in several combinations; but all of those had his last name, I guess, so it only found references to this LtU thread. =[

fall back to folds and

fall back to folds and unfolds when they are insufficient

Is programming primarily with folds and unfolds that onerous? I realize that iterating over two collections at once can be difficult with fold, but I believe it's doable. What are the fundamental limitations or downsides of fold? Or are the downsides perhaps limitations of current type systems?

folds and unfolds are trickier

Is programming primarily with folds and unfolds that onerous?

They are trickier to use than just well known combinators. Writing map f (filter p) xs is easier than writing the equivalent fold. Also you need to do lots of mental origami to solve some problems with nothing more than fold/unfold, a delightful exercise but it isn't something that most programmers would like to face with a pressing deadline. The good thing is that today we have good combinators to almost everything one would like to do, so we just need to find them (usually if you can spell the type you expect a tool like Djinn or Hoogle can write down the function for you).

Yes

Basically, fold captures the principle of one-step structural induction. However, we often want to recursions that have more complex structure, and emulating them with folds gets yucky. For example, here are two examples which are doable but ugly with folds:

(* We want both 0 and 1-element lists as base cases here *)

fun concat [] = ""
  | concat [x] = x
  | concat (x :: xs) = x ^ ", " ^ (concat xs)

(* with foldr, we need a flag to identify the last item *) 

fun concat ss =
  fst (foldr
	 (fn (s, (acc, islast)) =>
	    if islast then (s, false) else (s ^ ", " ^ acc, false))
	 ("", true)
	 ss)


(* We are using a course-of-values recursion here *) 

fun fib 0 = 1 
  | fib 1 = 1 
  | fib n + 2 = (fib n) + (fib (n + 1))

(* with folds, you need a higher-order fold to emulate course-of-values *)

fun foldnat s z n =
  if n = 0 then z else s (foldnat s z (n-1))

fun fib n =
  let val (_, fib', _) = 
    foldnat
      (fn (k, fibp, fibpp) =>
	 (k + 1,
	  (fn n => if n < k then fibp n else fibp n + fibpp n),
	  fibp))
      (0, (fn n => if n > 0 then 1 else 0), (fn n => 0))
      n
  in
    fib' n
  end

Things get more annoying when you want to iterate over two collections at once naturally.

This is because the natural way to put two collections together is with a zip, which is an unfold, and since folding over an unfold may fail to terminate this won't typecheck. Unfolds generate elements of greatest fixed points, and folds consume elements of least fixed points. So the typechecker has to rule out (fold f) o (unfold g) because it doesn't know for sure that a call to unfold g will produce something typed by the least fixed point. (Haskell and ML don't care about this issue because they both admit nontermination.)

-*-*-*-

This is all more or less fixable with enough dependent type theory, because you can give a general induction principle more or less equivalent to the Knaster-Tarski theorem, and use it to derive all the specific induction principles you want. There will likely need to be some research done on the scaffolding you need to make this all work in a clean way, though -- today, most type theories are at the spartan end, because proof assistants want simple type theories to get small trusted bases, whereas programming languages call for rich type theories to get small programs.

Ah thank you,

The point about making life easier actually makes a lot of sense. In a language that lacks Turing completeness, the programmer must do a great deal more work.

Thus it seems that the biggest benefit of Turing complete languages are that better/more abundant abstraction is available; which in turn allows efficient solutions and algorithms.

Of course, there are algorithms that cannot be done in a decidable language, but I feel I was missing the point that in a non-Turing complete language everything must be spelled out to explicitly halt.

However, there is a language Charity which can express the Ackerman function which cannot be done through primitive recursion, yet the language is not Turing complete. I have not used Charity and only looked into briefly as I sometimes get pulled into the world of categories. So now I am wondering, if many of the concerns expressed about primitive recursive languages would be much less a problem in a language like Charity.

You would probably be

You would probably be interested in this thread on total functional programming. The paper is about building a language that is not Turing complete, and how much can still be accomplished given that constraint.

Yes

That paper is exactly the kind of thing I was hoping to see. A very interesting read.

More transformations in terms of folds

neelk wrote

Basically, fold captures the principle of one-step structural induction.
However, we often want to recursions that have more complex structure, and
emulating them with folds gets yucky. For example, here are two examples which
are doable but ugly with folds:

Well, these particular examples are actually quite easily doable with
folds.

(* We want both 0 and 1-element lists as base cases here *)
fun concat [] = ""
| concat [x] = x
| concat (x :: xs) = x ^ ", " ^ (concat xs)

With fold (and using OCaml), we write just as easily:

let concat = function
| [] -> ""
| [x] -> x
| (x::xs) -> List.fold_left (fun seed a -> seed ^ ", " ^ a) x xs

# concat [];;
- : string = ""
# concat ["a"];;
- : string = "a"
# concat ["a";"b";"c"];;
- : string = "a, b, c"

The second example:

(* We are using a course-of-values recursion here *)
fun fib 0 = 1
| fib 1 = 1
| fib n + 2 = (fib n) + (fib (n + 1))
(* with folds, you need a higher-order fold to emulate course-of-values *)

actually, no. A simple fold suffices:


let rec foldnat s z n =
if n = 0 then z else s (foldnat s z (n-1));;

let fib n = fst (foldnat (fun (a,b) -> (a+b,a)) (1,0) n);;

# fib 0;;
- : int = 1
# fib 1;;
- : int = 1
# fib 2;;
- : int = 2
# fib 8;;
- : int = 34

Things get more annoying when you want to iterate over two collections at once
naturally.

Not that annoying:

How to zip folds: A library of fold transformers (streams)

Once we know how to get takeWhile and dropWhile via folds, the rest is
quite trivial. Essentially, we need a way to `split a stream', which
is doable for any stream represented as fold -- and even represented
as a monadic fold (where the production of each element may incur a
side effect, and we have to be careful not to repeat the
side-effects).

My "Turing Completeness

My "Turing Completeness Considered Harmful" unpublished paper might be related here. I think its much harder to design a simple language that is not expressive but still useful than it is to design a powerful language that can do anything. The benefit, at least in the area that I'm in, is usability: these languages are easier to use even if they put users in a straightjacket.

Isn't Turing Completeness just derived from adding...

...an if, cond or branching conditional statement to the language?

If not, what am I missing?

Unbounded loops or recursion

A conditional statement doesn't get you Turing-completeness, but any of the following will:

* General recursion--the ability of a function to call itself, directly or otherwise. (Some early languages, such as certain FORTRAN dialects, essentially created a partial ordering of functions such that only calls to lesser functions were permitted--such languages lack recursion. Many of those languages didn't stack activation records either, with the result that functions weren't re-entrant anyway).

* An unbounded loop--a loop that can potentially run forever. Bounded loops (i.e. a for loop with fixed bounds and an index which cannot change inside the loop body; or a map over a finite container) don't create Turing-completeness, but while(foo) {} does.