Search code examples
theoryturing-machines

turing computable function

Here are few True False questions: Somebody please answer these:

  1. Let F(0) = 1, and let F(n) = 2^F(n-1) for n>0. Then Is F Turing-Computable?

  2. No language which has an ambiguous context-free grammar can be accepted by a DPDA. Is this true ? If not which grammar is that.

Solution

  • For (1), ask yourself this question: could you write a computer program that could compute this function? If so, then by the Church-Turing thesis, then you know that there must be a TM that could do the same computation, so the function is computable. If not, then you know that no TM could evaluate the function either.

    For (2), remember that ambiguity is a property of grammars. There can be multiple grammars for the same language.

    Hope this helps!