Description
(In this assignment, TM stands for Turing Machine)
True or False:
1. [1 pts ] Finite automata can be regarded as a simplified version of TM.
2. [1 pts] TM accepts only one language.
3. [1 pts] For any given language L, a TM can only accept or reject it.
4. [1 pts] The language of a TM is not related to property of that TM.
5. [1 pts] A TM is called a decider if it can accept all input.
6. [1 pts] Every Multi-tape TM has an equivalent single-tape TM.
Short Answers:
7. [2 pts] According to Church-Turing thesis, what is the relationship between “A problem is computable” and “The problem is Turing-decidable”？
8. [2 pts]Write down three possible outcomes of TM:
