Sunday, February 15, 2004

Is it Recursive, Computable or Decidable?

Every reader of this weblog should know about the recursive and recursively enumerable (r.e.) sets, languages accepted by Turing machines where for recursive sets the machines must halt on all inputs and for r.e. sets the machines could run forever on strings not in the language.

So where's the recursion? The terminology comes out of historically different definitions of the recursive and r.e. sets and now we're stuck with it. Or are we?

In the mid-90's, Chicagoan Robert Soare decided his field of recursion theory suffered harm with its confusing terminology. He wrote a manifesto describing the origin of the concepts and the terminology and gave a passioned argument for changing the terms to computable and computably enumerable (c.e.) sets.

Was Soare successful? Yes and no. Within his own field most researchers now use the new notation. However the fundamental concept of recursive sets goes well beyond the relatively small sub-branch of logic now known as computability theory and it will take a much longer time for these name changes to propagate throughout computer science.

Soare missed another problem of the terminology, namely the word "enumerable." This term comes from the simple theorem that the r.e. sets can be alternatively defined as those languages of strings enumerated on an infinite output tape by a Turing machine with no input.

Because of these terminological issues, Michael Sipser, in his popular textbook, uses decidable and recognizable for the recursive and r.e. sets. I understand his motivation but find the new terminology only adds to students' confusion later in their career.

Whether I use recursive, decidable or computable depends on whom I am talking to. By default I find myself using recursive not because it's the best term but because it's the one that I grew up with.


  1. is it possible to prove that a function can be recursive, yet not computable? Thanks.

  2. Also "listable set" stands for a r.e. set.