能记忆的图灵机

Question

特殊图灵机的定义与标准图灵机一样，只是每一步都是根据磁带的内容从磁带的左边缘开始到磁头位置进行的。（本例中的转移函数属于 Q X Г* -> Q X Г X {L,R}）

以下内容哪些是对的：

A。每种语言 L 都有一个决定 L 的图灵机当且仅当存在一个决定 L 的特殊图灵机。

B.每种语言 L 都有一个图灵机，可以在多项式时间内决定 L，当且仅当存在一个特殊的图灵机，可以在多项式（输入长度​​多项式）中决定 L。

C。A、B答案正确。

D .A、B 答案错误。

我的问题是：正确答案是D，我不明白为什么。

答案是：每种语言都可以由特殊的图灵机在线性输入长度时间内决定（O(n)，当n是输入长度时）。只要没有看到空白，转换功能就会向右移动，一旦看到空白，就会根据磁带上写的字切换到接收或拒绝。

我的问题是：我如何决定是拒绝还是接受某个词？在其他计算模型中，例如PDA、DFA，我们类似地定义了转换函数，并且没有给模型添加幂。为什么对于图灵机来说，由于转换函数的改变，计算模型似乎变得更加强大了？

谢谢。

Answer 1

给定任何语言 $L$ 有一个特殊的图灵机 $T$ 这决定了 $L$ 在多项式时间内。

图灵机有3种状态：初始状态 $q_0$, 接受状态 $q_A$ 和拒绝状态 $q_R$. 。让 $\伽玛$ 是磁带字母表（包括空白符号 $\瓦瑞普西隆$）， 然后让 $\阿尔法x$ 表示从左边缘开始到磁带头部位置的磁带内容，其中 $\alpha \in \Gamma^*$ 和 $x \in \Gamma$. 。像往常一样，我假设输入是从磁带的开头开始写入的，并且磁头最初位于磁带的开头。过渡函数 $\德尔塔$ 定义如下：

• $\delta(q_0, \alpha x) = (q_0, x, R)$ 如果 $x eq \varepsilon$
• $\delta(q_0, \alpha x) = (q_A, x, R)$ 如果 $x = \varepsilon$ 和 $\alpha \in L$
• $\delta(q_0, \alpha x) = (q_A, x, R)$ 如果 $x = \varepsilon$ 和 $\alpha ot\in L$

由于常规图灵机存在不可判定的语言，因此这立即意味着 A 和 B 是错误的。

答案D和C不明确。他们谈论“两个答案”，但你得到了 $4$ 可能的答案。