turing computable function

Question

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.

Answer 1

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!

Answer 2

I guess the first one is true.

According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable.