turing-machines

如何找到升补， L = {<M>: M is a TM, which accepts some palindrome} 什么是寻找一个补充的一般规则？我在这个特殊的情况下，以为这将是 L_bar = {<M_bar> : M_bar is a TM, which rejects any palindrome .???

-1热度

1回答

递归可判定语言，接受无限语言

所以我的理解是递归可Decidable语言是我们可以构建一个图灵机的语言，因此如果从该语言输入w，图灵机将始终接受并暂停或拒绝并停下来。我感到困惑的是可以长到无限的语言。举个例子，我们有一个语言L = {0^p | p是素数}。所以我们可以编写一个算法来确定一个数是否是线性空间中的素数。所以我的理解是，既然这个算法或者告诉我们数字是素数或者不是素数，那么L必须是递归可判定的吗？但是由于p不受任何固

0热度

1回答

可删除性不可定义

我想问一下有关减少。在证明ETM是在M1的定义undecideable是 1.如果X！= W，拒绝 2.如果X = W，输入运行男女并接受如果M确实在我遇到的很多证据中，我看到了粗线，但我不明白我该怎么做，因为我不知道它是否会停止。我会很高兴知道我在哪里错了。谢谢。

0热度

1回答

这种语言是否可确定

L = {（，，x）| M1（x）严格执行多于M2（x）的步数}。（如果两个计算都是永久运行的，那么两个计算都不会比另一个严格得多）。该语言是否可判定？如何证明它？

0热度

1回答

图灵机：取两个数字的mod？

设计一个图灵机，它将输入两个非负数并对它们执行mod操作，例如mod（3,7）= 3和mod（7,3）= 1。显然，指定关于TM的输入和输出的任何假设和格式。