regular - regular expression, regular grammar, accepted by a DFA, NFA or NFA-lambdacontext free - context free grammar, PDA (pushdown automaton)context sensitive - not covered in detail, rules like Ab = Abbrecursive - Turing machine that always halts, uses final statesrecursively enumerable - Turing machine that halts to accept, (no final states) but otherwise either does not halt, or halts abnormallyThe complement of a recursive language is recursive. - If it's recursive, it's accepted by a Turing machine that always halts. If you flip the accepting/non-accepting states to get the complement, the machine still always halts, so the complement is recursive. |

**regular** - regular expression, regular grammar, accepted by a DFA, NFA or NFA-lambda

**context free** - context free grammar, PDA (pushdown automaton)

**context sensitive** - not covered in detail, rules like Ab = Abb

**recursive** - Turing machine that always halts, uses final states

**recursively enumerable** - Turing machine that halts to accept, (no final states) but otherwise either does not halt, or halts abnormally

**The complement of a recursive language is recursive.** - If it's recursive, it's accepted by a Turing machine that always halts. If you flip the accepting/non-accepting states to get the complement, the machine still always halts, so the complement is recursive.

If P then Q

If not P, then not Q (contrapositive)

We know the halting problem is [not decidable?]. You can say 'yes' if it halts, but if it hasn't halted yet, you can't say whether it ever will.

For a given program and a given input, you can usually tell whether it will halt or not. You can detect loops by seeing if you're in the same state with the same input. Turing Machines are deterministic, so if you've been in that state with that input before, it's going to happen again.