What is the difference between recursive and recursively enumerable languages

Question

I was wondering what the difference between recursive and recursively enumerable languages is in terms of halting and Turing Machines. I know that recursively enumerable languages are a subset of recursive languages but I'm not sure about the difference beyond that.

Answer 1

The halting problem (HALT) is the canonical example of a problem that is recursively enumerable (RE) but not recursive (R)

When trying to split complexity classes, it always good to have an example in mind that belong to one but not the the other.

In this case, the canonical example is the language corresponding to the halting problem (HALT) decision problem:

Determine if a Turing Machine halts given a specific input

It is well known that the halting problem cannot be deterministically resolved by any Turing machine, and therefore the language HALT is not in R.

But HALT is obviously in RE. We recall the definition of a recursively enumerable languages as:

A RE language is a language such that there exists a Turing machine that halts on every member of the language with a yes output, and possibly runs forever on non-members

So we just take a Turing machine that simulates another Turing machine (universal Turing machine). Then that machine will halt on every member of HALT, and so HALT is in RE.

This fact alone should highlight how much harder RE is than R:

• RE contains undecidable problems, for which is it provenly impossible to design an algorithm for!
• R, as a direct consequence of its definition, doesn't. Every input results in an output. I.e. these Turing machines represent what we generally call an "algorithm"

Non-RE problems

It is also helpful to have a look at examples that bound both:

• https://cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages
• https://cs.stackexchange.com/questions/12747/relationship-between-undecidable-problems-and-recursively-enumerable-languages

The canonical example is the complement of HALT: the language of all non-halting TM/input pairs.

Looking at the bigger picture

It might also help to zoom out a bit and place both classes in a larger hierarchy to see them in a more global picture. The following inclusions are widely believed to be all strict, although some are unproven:

Graphviz source code:

digraph {
    subgraph cluster_nre {
        label="Non-recursively enumerable"
        subgraph cluster_re {
            label="Recursively enumerable (RE)"
            subgraph cluster_recursive {
                label="Recursive (R)"
                subgraph cluster_exptime {
                    label="Exponential time (EXPTIME)"
                    subgraph cluster_context_sensitive {
                        label="Context sensitive (CSG)"
                        subgraph cluster_p {
                            label="Polynomial time (P)"
                            subgraph cluster_context_free {
                                label="Context free (CFG)"
                                regular[label="Regular"]
                            }
                        }
                    }
                }
            }
        }
    }
}

We might also have a quick look at the worst case time complexity to decide if a given word belongs to some well known languages:

Language	Worse case time
Non-recursively enumerable	∞
Recursively enumerable	∞
Recursive	Finite (but possibly way worse than exponential)
Context-sensitive	Likely exponential (more precisely, PSPACE-complete, which likely requires exponential time but it's not proven)
Context-free	O(n^m) with 2 ≤ m < 3 (reduces to boolean matrix multiplication which occasionally gets new improved results, though there's no optimality proof yet)
Regular	O(n) (linear, can be converted to deterministic finite automaton)

Hopefully all of this should make it clear that the distinction between R and RE has zero practical importance for programming, because in practice we can't really solve anything with exponential time complexity except for the smallest inputs. For practical purposes, what we care about is "is there a polynomial algorithm, and what is the exponent", so the classic "context-sensitive vs context-free vs regular" is where applications will be.

There is however great mathematical and philosophical beauty in considering the higher hierarchies. To me it feels like there is this secret world of Gods, and that they have their hierarchy which we are trying to peer into.

Answer 2

The main difference is that in recursively enumerable language the machine halts for input strings which are in language L. but for input strings which are not in L, it may halt or may not halt.

When we come to recursive language it always halt whether it is accepted by the machine or not. if it accepted it reaches at (q accept) and halt. and if not accepted by the machine it directly reach (q halt).

Answer 3

You have the relationship between R and RE backwards: R is a (proper) subset of RE. Basically, a recursive language is one for which you have a total decider.

Recall a definition of recursively enumerable languages as one for which a partial decider exists; that is, a Turing machine which, given as input a word over your alphabet, will either correctly accept/reject the word according to your language, or if the word is not in your language, it may loop forever.

A recursive language, in contrast, is one for which a total decider exists, i.e. one that will never loop, and always halt in either an accepting or a rejecting state.

Putting these two definitions next to each other, it is obvious that a recursive language is also recursively enumerable, since the total decider is also a partial one (it just never "chooses" to loop instead of halting with a correct answer).