Turing Machine ( True or False )

1. A Universal Turing Machine can compute anything that any other Turing Machine could possibly compute.
True

2.The Turing Test is a test of whether a problem can be solved by a Turing Machine.
True

3. Every acceptable language is also decidable.
False

4. Decidability is a special case of decidability
True

5. Regular languages are decidable
True

6. Context free languages are not decidable
False

Useful Websites

Countability Proofs
http://mathrefresher.blogspot.com/2006/09/countability.html

Theory of Automata video lectures
http://web.cs.wpi.edu/~kal/courses/cs503/

Decidability Slides
http://www.cs.virginia.edu/~robins/cs6160/slides/Deciders,%20Recognizers,%20Rice%27s%20Theorem%20(parts%2013%20and%2014).pps

List of Automata theorems
http://web.njit.edu/~marvin/cs341/listofthms.pdf

Proof for REGTM
http://www.cs.tut.fi/~elomaa/teach/iTCS-8.pdf