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.
is it possible to prove that a function can be recursive, yet not computable? Thanks.
ReplyDeleteAlso "listable set" stands for a r.e. set.
ReplyDelete