Computable Languages

Recursively Enumerable (r.e):

A language L is r.e. if L = L(M) of a Turing Machine.

Membership Determination

1. Regular sets - DFA / / O(n) time.
2. Context-free languages - CYK algorithm, time.
3. R.E. languages - TM does not exist for all r.e. sets.

Recursive Sets:

L is recursive if L = L(M) of TM M and M halts on all inputs.