标签: turing-machines

图灵机的定义说，禁止人们阅读/修改其指令表（程序）。确实，图灵机无法访问其自己的程序。

如果可以弱化这一限制，可以获得什么好处？如果机器可以分析和/或修改其程序。这会扩展图灵计算任务的类别吗？

我正在努力理解和实施最简单的图灵机,如果我有意义的话,我想要反馈.

我们有一个无限的磁带(假设一个名为T的数组,指针在开始时为0)和指令表:

( S , R , W , D , N )

S->STEP (Start at step 1)
R->READ (0 or 1)
W->WRITE (0 or 1)
D->DIRECTION (0=LEFT 1=RIGHT)
N->NEXTSTEP (Non existing step is HALT)

我的理解是3状态2符号是最简单的机器.三态我不明白.2符号,因为我们使用0和1进行READ/WRITE.

例如:

(1,0,1,1,2)
(1,1,0,1,2)

从步骤1开始,如果Read为0,则{Write 1,Move Right> else {Write 0,Move Right>,然后转到步骤2 - 不存在停止程序.

三态是什么意思？这台机器是否作为图灵机通过？我们可以简化更多吗？

我找到了维基百科的图灵机等效列表文章.但是,它没有说明如何确定给定机器是否与图灵机等效的方法.

我是否需要使用图灵机的定义来证明它？你举个例子吗？

谢谢.

w ^ R是w的反向,w是{0,1}*.因此,TM需要决定一个单词,然后是该单词的反向,后跟单词.我不想要答案,我只想要领先一步并走上正轨.

假设存在图灵机M1,M2,M3,它们识别的语言分别是L(M1),L(M2)和L(M3).以下语言L = {(M1,M2,M3):L(M1),L(M2)和L(M3)不相等}语言是否可判定？递归可枚举？或者都不是？

我不明白为什么没有标记接受状态时Turing Machine T，ACCEPTS并在标记接受状态时为什么拒绝：

E（dfa）= {| A是DFA，L（A）=空集（没有符号）}

E（dfa）是一种可决定的语言。

证明：DFA可以接受一些字符串，当从起始状态到达接受状态时，可以通过>沿DFA的箭头进行移动来实现。为了测试这种情况，我们可以设计一个> TM T，它使用类似于示例3.23的标记算法。

T =“在input上，其中A为DFA：1.标记A的开始状态。2.重复直到未标记任何新状态：3.标记从已标记的任何状态进入转换的任何状态4.如果没有标记接受状态，则接受；否则，拒绝。”

在我看来，这是倒退的。谁能解释一下？

谢谢。

非上下文无关的递归可枚举语言的简单示例是什么？我的教科书在明确提供这样的例子方面非常糟糕。

需要明确的是，这不是一个 hmk 问题。

如果L1和L2是语言,我们有一种新语言

INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ? L1, v1v2 . . . vn ? L2}.

例如,if abc ? L1和123 ? L2thena1b2c3 ? INTERLACE(L1, L2)

我怎样才能证明INTERLACE:

1. 可判定的？
2. 可识别？

我知道如何显示这种语言是正常的.对于可判定的我不太确定..

这就是我的想法:

为了表明在操作中关闭可判定语言的类INTERLACE需要表明如果A和B是两种可判定的语言,那么有方法可以找到INTERLACE语言是否可判定.假设A,B可判定语言M1,M22 TM谁决定,分别.

在我想我必须说如何构建识别语言的DFA之后？

令 T = {<M> | M 是一个 TM，只要它接受 w}，它就接受 w ^r。
证明 T 是不可判定的。

我对这个问题有两个答案 -圣地亚哥：

5.9
令 T = { <M> | M 是一个 TM， 只要它接受 w } 就接受 w ^r。

假设 T 是可判定的，让决策者 R 决定 T。通过构造一个 TM S从 A _TM减少如下：

• S：在输入 <M,w> 上
  1. 如下创建 TM Q：
     在输入 x 上：
     1. 如果 x 没有表格 01 或 10 拒绝。
     2. 如果 x 的形式为 01，则接受。
     3. 否则（x 的形式为 10），在 w 上运行 M，如果 M 接受 w，则接受。
  2. 运行 R
  3. 如果 R …

Datalog不是图灵完备的。

但它的计算类是什么？

它相当于有限状态机或下推机（即上下文无关）……还是介于两者之间？