RS#3
- Turing Machines -TMs


Examples

TM - algorithms using head, infinite tape, memory/states
 variations - multiple tape, nondeterminism

decidable problems, recursive (r.) languages
recognizable problems, recursively enumerable (r.e.) languages

A language is r. if and only if both it and its complement are r.e.
The complement of a r.e. language (that is not r.) is not r.e.

Librarian Paradox
Countable Sets
Diagonalization
A_TM is r.e. and not r.
The Halting Problem

Reduction
If A reduces to B then A can be solved in the presence of B. 
Thus B is no easier than A and A is at least as easy as B.

If A reduces to B and B is decidable then A is decidable.
If A reduces to B and A is undecidable then B is undecidable.

Rice's Theorem - Any nontrivial question about r.e. languages is undecidable.

Facts:
 It is decidable if:
    - you can build a decider for it.
    - it and its complement are r.e.
    - you can reduce it to another decidable language

 It is recognizable if:
    - you can build a decider or recognizer for it.
    - you can reduce it to another recognizable language
   
 It is not recognizable if:
    - its complement is r.e. and not r.
    - diagonalization proofs

 It is not decidable if:
    - its complement is r.e. and not r.
    - An undecidable language can be reduced to it.
    - Rice's Theorem