Question

Which of the following can be recognized by a Turing machine?

1. Palindrome recognition

2. GCD computation

3. SQUARE(SQUARE(.....(x)) where SQUARE(x) = x ²

4. All the above

Answer 1

All the function given here are Turing decidable .So all function can be recognized by $LBA$ .So Turing machine can easily recognize these functions .

We can say Every effectively calculable function is a computable function.

First language is palindrome which can be recognized by non deterministic PDA as well as Turing machine.

Second and third are computable function which can be easily recognized by Turing machine.

Anything a real computer can compute ,Turing machine can also compute.

So option D is correct.