next up previous contents
Next: Are All Languages Recursively Up: Recursive Languages Previous: Recursive Languages

Recursive languages = TMs that always halt

A subset of r.e. languages is the recursive languages. A recursive language L(M) which can be accepted by at least one TM guaranteed to halt on all its inputs, whether or not the input is a member of L(M). This does not mean that all inputs are accepted, but rather that all inputs can be either accepted or rejected in a finite time. Such a TM will always halt .