问题标签 [turing-complete]

我设计了一个假设的指令集，我认为它是图灵完备的。我想不出该指令集无法完成的任何计算操作。我只想验证这个假设的指令集确实是图灵完备的。

寄存器

IP = 指令指针

FL = 标志

记忆

冯诺依曼

其他信息

指令有两种形式（条件/立即跳转是异常值）：

• 使用标量作用于内存
• 使用其他内存作用于内存

所有指令都作用于固定大小的无符号整数

每条指令由一个一字节操作码和三个尾随一字节参数组成（并非所有参数都必须使用）。

假设一个字节能够保存任何内存地址

指示

移动 = MOV

基本算术 = ADD、SUB、MUL、DIV、REM

二进制逻辑 = AND、NOT、OR、NOR、XOR、XNOR、NAND、SHR、SHL

比较 = CMP（该指令通过比较两个值来设置标志（不包括无符号整数溢出标志））

Conditional Jumps = JMP，基于标志的各种条件跳转

标志

• “无符号整数溢出”
• ">"
• “<”
• ">="
• "<="
• “=/=”
• “=”

或任何其他压缩算法，就此而言。

（话又说回来，如果有一个图灵完备的压缩算法，它还会被认为是一种压缩算法，而不是一种编程语言吗？）

我在阅读以太坊白皮书时想到了图灵完备这个词。我做了一些研究，发现这是一个完整的数学理论。我如何开始在技术层面上学习图灵机和图灵完备性。我不关心与以太坊的联系，我只想了解科学部分。我的意思是介绍技术级别升级。我用谷歌搜索了这个，发现了一般的 powerpoints/pdf，但这不是我要找的。我决定在这里询问（寻求指导/教科书），因为我很确定这里有专家在这个主题上工作。对不起，一般类型的问题。我只是一个喜欢数学和密码学的人，试图理解如何世界函数。

亲切的问候，
尼克

我经常听说 C++ 模板是图灵完备的。这是什么意思？

我之前的搜索将我引向链接[1]和[2]，它们很好，但它们没有回答我的问题。

它能够通过简单地使用引用自身的模板并使用模板专业化来做出决策来表达一般递归。

递归和决策是否等同于图灵完备性？

有人可以在编程方面（而不是从计算机科学方面）分解图灵完整性的要求吗？

我想知道是否可以这样做？

谢谢

给定下表：

我如何计算最终的 AST：AND(NOT(AND(K, OR(X, A, B))), OR(Y, Z))

我尝试了使用递归 CTE 的不同方法，但我的问题是 CTE 既不允许在 CTE 的递归部分进行聚合，也不允许在使用 CTE 的子查询中进行聚合。

我尝试的最新方法是：

但由于 CTE 的限制，它不起作用。

文档说 CTE 是图灵完备的，但我找不到计算所需结果的方法。我是否遗漏了什么或者我对图灵完整性的理解是错误的？:)

（我有 Postgres 9.6）

自从我在大学里学会了如何操作装配以来，我就对从尽可能小的开始并建立无限复杂性的想法着迷。我一直在研究我自己的理论最小指令集，它避免了像“subleq”这样的复合指令。我对这类指令的问题是它们的行为就像两个（或更多）独立的指令，并保持状态。换句话说，它们可以分解为（IBM 伪代码）：

所以我想用来在其上构建更多复杂性的最小指令集应该已经被原子化并且不应该包含状态。

到目前为止，我想出了三个指令：(s)tore、(n)and 和 (j)ump。有一个累加器和一个 PC 计数器 - 没有别的了。所有指令都采用两位后跟包含相对地址的 X 位，这意味着没有“立即”值。我可以使用这些指令（8位）将一个值加载到累加器中：

很明显，指令编辑允许有效地进行有条件的跳转，但我还不完全确定如何完成这样的任务。如此简单的事情仍然是图灵完整的，还是这是天上掉馅饼的想法？

图灵完整性是否会阻止语言具有CFG？我找不到任何这样说的论文。

我发现了这一点： “TeX 只能由完整的图灵机（以可用的有限空间为模）解析，这使其无法拥有 BNF。”

我想开发一个基因程序，可以解决一般问题，比如在电脑游戏中生存。由于这是为了娱乐/教育，我不想使用现有的库。

我想出了以下想法：

输入是一个包含 N 个整数的数组。遗传程序由多达 N 个 AST 组成，每个 AST 从一些数组元素中获取输入，并将其输出写入单个特定数组元素。

AST 可以是任意复杂的，并且仅包含四个算术运算符（+、-、*、/），并且可以对给定数组的常量和固定元素进行操作（无随机访问）。

所以对于 [N=3]，我们有 3 个 AST，例如：

N AST 一个接一个地执行，并且无限重复。

现在我的问题是，这个系统是否足够“强大”（图灵完备？）还是无法解决游戏 AI 常见的一些问题？

我正在阅读有关图灵机的库克定理。在其证明中，据说图灵最多需要 n^k 步（其中 k 是整数且 k > 0）来计算长度为“n”的输入

这可能是假设图灵机对于给定的输入确实停止了它进一步说我们最多有 n^k 步，我们不需要无限的磁带。带有 n^k 个元素的胶带就足够了，因为车床不会移动超过

为什么我们说图灵机最多需要 n^k 步？