L(M) = {w | M accepts w}. We call L a recursively enumerable language (or RE in short)
where q ∈ F and α1,α2 are some strings.
- Note that the machine may not read all the symbols in w.
- It may pass back and forth over some symbols of w many-many times.
- Convention : We will always consider TMs that halt when they reach an accepting state.
- Semi-decidable : L is semi-decidable if there is a TM M such that L = L(M).
- So on strings w ∈ L, M reaches a final state and halts
- on string w / ∈ L M either halts without reaching a final state or it never halts
- Decidable/Recursive : L is decidable/recursive if there is a TM that halts on every input and L = L(M)