问题标签 [computability]

我想知道[标题]上面的这句话是真的还是假的。

这是我已经拥有的：非递归意味着不可判定。

我读过这篇文章 所有无限语言都无法确定吗？

其中说：

如果一种语言是不可判定的（非递归的），则必须有一些字符串使 TM 无法停止。所以它必须有无限的字符串使 TM 无法停止。

这怎么能证明我的陈述[标题]？谁能更清楚地向我解释一下？

谢谢

附言。对困惑感到抱歉。是的，TM 表示图灵机。也很清楚我的问题是：所有非递归语言都是无限的吗？

autogram是一个描述它包含的字符的句子，通常列举字母表中的每个字母，但也可能列举它包含的标点符号。这是 wiki 页面中给出的示例。

这句话使用了两个a、两个c、两个d、二十八个e、五个f、三个g、八个h、十一个i、三个l、两个m、十三个n、九个o、两个p、五个r、二十五个s、23 个 t、6 个 v、10 个 w、2 个 x、5 个 y 和 1 个 z。

想出一个很难，因为在你完成句子之前你不知道它包含多少个字母。这促使我问：是否有可能编写一个可以创建自动图的算法？例如，给定的参数将是句子的开头作为输入，例如"This sentence employs"，并假设它使用与上述相同的格式"x a's, ... y z's"。

我并不是要您实际编写算法，尽管无论如何我很想看看您是否知道存在一个算法或想尝试编写一个算法；相反，我很好奇这个问题是否是可计算的。

我知道如果存在用于一种语言的图灵机，那么该语言是递归可枚举的，因此存在它的枚举过程。但是，如果一种语言是可数的，这是否意味着它必须有一个 TM 呢？

谢谢！

我想知道任何人都可以笼统地向我解释 Lambda 演算和图灵机等价的一些证明以及证明的一般方法。尽可能通俗易懂。

如果 L 是任何语言。语言 perms(L) 是 L 中所有单词排列的语言。

对或错：如果 L 是递归可枚举的（可计算可枚举的），那么 perms(L) 也是递归可枚举的。

这是在之前的决赛中出现的问题：如果 L 是可判定的，那么 perms(L) 也是可判定的，我发现这是真的。

我想我会说假的，但我没有证据支持这种说法。

我正在学习计算机科学专业的高级理论课程，并​​负责设计 NFA。如果我没记错的话，如果 NFA 中的任何路径可以获取字符串并进入接受状态，则 NFA 接受输入。我理解并且可以很好地创建 DFA，并且理解 NFA 需要表达在等效 DFA 中明显更大的问题。但我对 NFA 接受某些东西的具体程度感到有些困惑。

例如，我的一个作业问题如下：

为 {wxw^R | 给出一个 NFA x ∈ {0, 1}∗, w ∈ {0, 1}^2},

其中，如果我正确解释了这一点，w^R 是字符串 w 的倒数，x 是任意长度的二进制字符串，w 是“00”、“01”、“10”、“11”。

所以本质上 NFA 会接受一个以 w 开头的字符串，有一些字符串 x，然后以 w 的倒数结尾。

我已经正确设计了，尽管在之前的作业中为此设计了非常大的 DFA，但我确定的练习是教我 NFA 在某些情况下比 DFA 更易于使用。我想出了这样的答案：

http://s1056.photobucket.com/user/pcd132/media/Untitled_zps4317347c.jpg.html

这个 NFA 几乎接受任何非空二进制字符串，那么它是否满足这个问题？我只是对如果它以某种方式接受某些东西，它应该被接受的概念感到困惑。或者我应该以某种方式只接受条件而不接受其他方式来构建它？如果我不理解这一点，感谢您的帮助和澄清。

第一次在这里发帖，对格式感到抱歉。

我需要帮助方法重载让我的程序添加整数和浮点数，例如 4 和 5 = 9

4.0 和 5.0 = 9.0

但是到目前为止，即使我只是输入带有 int 值的数字，我的输出也只给了我浮点值。

据我所知，可以制作图灵机来执行磁带上编码的指令的循环或迭代。这可以通过识别行分隔符并使图灵机返回直到达到特定的行分隔符计数（即，在循环内）来完成。但是，图灵机也可以执行递归程序吗？

有人可以描述这种图灵机的各种细节吗？

我想，如果递归可以由图灵机执行，那么快速排序也可以执行？