theory - 图灵可计算函数

Question

这里有几个真假问题：请有人回答这些问题：

1. 令 F(0) = 1，并令 F(n) = 2^F(n-1) 时 n>0。那么 F 图灵可计算吗？

2. DPDA 不能接受具有不明确上下文无关语法的语言。这是真的 ？如果不是，那是哪种语法。

Answer 1

我猜第一个是真的。

根据 Church-Turing 论文，可计算函数正是在无限时间和存储空间的情况下，可以使用机械计算设备计算的函数。等效地，本文指出任何具有算法的函数都是可计算的。

Answer 2

对于（1），问自己这个问题：你能写一个可以计算这个函数的计算机程序吗？如果是这样，那么根据 Church-Turing 命题，你就知道一定有一个 TM 可以做同样的计算，所以这个函数是可计算的。如果不是，那么您知道没有 TM 也可以评估该函数。

对于 (2)，请记住歧义是语法的一个属性。同一种语言可以有多种语法。

希望这可以帮助！