Turing Machine basic properties


#1

Which of the following are true?

  1. If P1 reduces to P2, then if we can solve P2, we can use the solution of P2 to solve P1
  2. Turing Machine can have only one final state.
  3. The set of languages accepted by Turing Machine is called- recursively enumerable language
  4. Every language accepted by a multitape Turing machine is recursively enumerable
  5. No recursively enumerable language is accepted by a three-counter machine
    A. 1,3 B. 1,3,4
    C.1,4,5 D.2,4,5