个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
26
4
在所有的图灵机扩展中(例如双向无限磁带、RAM、多个读/写磁头和非确定性)，它们中的任何一个都允许 TM 决定以前不可判定的问题吗？
最佳答案
双向无限磁带不会拉伸(stretch)计算能力。 RAM 在某些情况下会改变处理速度，但不会改变计算能力。多个读/写头可用于模拟非确定性图灵机 (NDTM)，但仍无法提高其计算能力。
因此，不，这些调整不能解决新问题，但有时可以改变计算速度。
您可以在有限的步骤内将这些额外的增强功能减少到更简单的图灵机，反之亦然。但是，我相信双向无限磁带是 TM 的标准模型。
(虽然我们讨论的是基本 TM 的扩展主题，但看看 Quantum TM，据我所知，它仍然没有解决新问题:http://en.wikipedia.org/wiki/Quantum_Turing_machine)
关于turing-machines - 哪些图灵机扩展扩展了机器的功能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16307160/
26
4
0
我理解图灵机的逻辑。当给出图灵机时，我可以理解它是如何工作的以及它是如何停止的。但是当它被要求构造图灵机，难度更大。 有什么简单的方法可以找到问题的答案，例如: Construct a Turing
我找到了一篇关于 a list of Turing machine equivalents 的维基百科文章.但是，它没有说明如何确定给定机器是否与图灵机等价的方法。 我需要用图灵机的定义来证明吗？你能
图灵机的定义说，禁止人们阅读/修改其指令表(程序)。确实，图灵机无法访问其自己的程序。 如果可以削弱这一限制，可以获得什么好处？如果机器可以分析和/或修改其程序。这会扩展图灵计算任务的类别吗？ 最佳答
下面的语言 L 是不可判定的吗？ L = {M | M is a Turing machine description and there exists an input x of length k
所以我试图寻找语言的精确定义，但所有文章都假设这个定义对每个人都是显而易见的。显然，对我来说不是。 图灵机器语言的定义是什么？ 最佳答案 当你运行一个 TM 时，你给它一个字符串作为输入。然后 TM
安全元组关系演算是图灵完备的语言吗？ 最佳答案 让我们忘记安全。来自 Codd's theorem ，关系演算等价于一阶逻辑。 FOL 是非常有限的，它不能表达在某个图中有从 A 点到 B 点的路径(
如果一种语言有控制结构和变量，但不支持数组、列表、内存访问和分配等，它可以是图灵完备的吗？ 也许如果你可以创建的变量数量没有限制，你可以通过创建像 array_1 这样的变量来模拟数组。 , arra
“字典”是指具有唯一键的键/值对数组。如果不是，为什么？如果时间足够长，您可以使用键作为输入，使用值作为输出，它可以解决您想要的所有问题。只要它足够长以容纳所有可能的输入，它就可以“计算”任何东西。只
我正在寻找图灵机停机问题的简单解释。我知道 TM 的工作原理、它们如何枚举事物、机器配置等，但我对停机问题没有很好的处理。 有人可以对这个主题提供一个很好的解释吗？ 最佳答案 一分钟，让我们忽略图灵机
我需要帮助设计一个图灵机来计算以下 f(x,y) = x*y mod 4 .如何在二进制基础中解决此问题 $x$和 $y$有两个位？ 最佳答案 可能会稍微优化，但它确实有效: 假设 - 输入(仅)由两
如果我有一台机器，将其称为机器1，它可以解决问题:它只是一台机器，本身不是图灵机。它可以解决一个特定的问题。 如果在通用图灵机上可以解决这个完全相同的问题，那么我的原始机器1也是通用图灵机吗？ 这并不
关闭。这个问题是off-topic .它目前不接受答案。 想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。 12 年前关闭。 Improve this
包含任意数量的纸带符号的图灵机 M 可以通过仅包含三个纸带符号的 M' 来模拟:{0, 1, B}(B = 空白)。 M 可以用只有两个纸带符号的 M"来模拟吗，比如说 {1, B}？ 最佳答案 第一
我一直在努力解决一个问题，即将没有前导零的二进制数转换为同一磁带上的一元表示。 例如。 110 -> xxxxxx 我发现马尔可夫算法是一个潜在的解决方案，但我无法实现它。希望得到一些指导! 编辑:我
我在听edX课，教授强调每台能够执行这六个基本原语的机器都可以称为图灵完备。但是六个基本原语是什么？ 最佳答案 使语言具有图灵完整性的六个基本操作/原语是: 右:将机器的头部移动到当前方块的右侧 左:
我儿子最近一直在玩Little Big Planet 2，我注意到游戏编辑器允许AND门，OR门和NOT门...图灵完成了吗？如果是这样，那么有人可以推荐一个学习这些原始内容的条件的资源吗？ 最佳答案
您好，我对可数性有疑问。为什么有必要找出某些事物是否可数。找到它有什么用吗？而且，如果某些事情不可数，是否意味着没有图灵机可以解决它？ 最佳答案 我希望我不是通过回答你的问题来帮助你回答考试问题。 可
在所有的图灵机扩展中(例如双向无限磁带、RAM、多个读/写磁头和非确定性)，它们中的任何一个都允许 TM 决定以前不可判定的问题吗？ 最佳答案 双向无限磁带不会拉伸(stretch)计算能力。 RAM
我想知道邮政通信问题 (PCP) 是否可识别。我学会了如何证明 PCP 的不可判定性。我也想过使用类似的方法来提高可识别性，即考虑 MPCP 并显示它是否可识别。我不确定这是否是一个好方法。 最佳答案
w ^ R是w的倒数，w是{0，1} *。因此，TM需要先确定一个单词，然后再确定该单词的反义词，再确定该单词。 我不想要答案，我只是想要一个线索开始并走上正确的道路。 最佳答案 由于已经过去了一段时
我是一名优秀的程序员,十分优秀！