问题标签 [turing-complete]

Ansible 提供了许多过滤器和条件。据我所知；应该可以实现一个 Ansible 剧本，该剧本执行一组任务，这些任务达到与图灵完备语言相同的结果。那么，图灵完备吗？

我注意到 AND、OR、NOT 这三个逻辑门在功能上是完整的，这意味着我只能通过这三个门来表示任何真值表。

所以，我想知道我是否只能用这三个门来表示任何可计算的函数？

我已经用自己的 BF 解释器在汇编中编写，现在我正在用 Java 编写一个 BF 编译器，它可以编译为汇编代码。

我想实现一个很好的功能，可以检测内存单元数组是否超出范围。数组的一个传统限制是让索引在 中[0, 30000)，否则[0, inf)也是常用的。另一种选择是内存是环绕的，所以在第一种情况下，这可能意味着访问索引 30000 意味着访问索引 0。

在我的编译器中，这种检测将在传统编译器的语义分析阶段完成，因此我们已经从语法分析阶段获得了我们的 AST（抽象语法树）。

在尝试为此提出一个结构一段时间后，我发现在 Brainfuck 程序中检测无限循环，连同 BF 的 Wikipedia 页面，我发现带有内存数组的 BF 程序[0, inf)类似于图灵机。

所以我的问题是，对于这两种情况[0, max)，[0, inf)是否可以检测内存指针是否低于零，而在前一种情况下是否低于最大值？显然，在检查它时不会陷入无限循环，我也宁愿避免设置最大执行时间。

额外问题：是否可以检测循环构造[...]循环的次数？

我一直在寻找这个，但一无所获。

我曾经在一些 python 的书中看到过这个解释，但我不记得是哪一个。那么，编程语言应该包含哪些元素（变量、循环、分支等）是图灵完备的？

如果它的存储单元容量为 1 位，而不是通常的 8 位，编程语言 Brainfuck 的实现是否仍然是完整的？

+ 和 - 指令变得相同，但这不是问题。

例如，我认为 4 位存储单元没有问题，但我无法确定这是否一直扩展到单个位值。

Many programming languages and systems are Turing-complete; they can simulate any Turing machine, and therefore can simulate any finite state machine as well.

Consider the following informal model:
Language A defines a finite set of NAND gates, their connections to each other, and which gates receive input and which are outputted.

In this model, any finite state machine can be built. The NANDs can form latches, registers, busses and control structures, and in the end any finite state machine, including full computers and other systems.

The model, however, does not have the ability to simulate an infinite tape, only a tape of finite size. It cannot simulate any Turing machine because it may not have the memory to do so.

Are Language A and all other systems that can simulate any finite state machine considered Turing complete? Is there a separate class for them, or is there an opportunity to define such?

我正在编写一种基于堆栈操作的笑话语言。我试图找到使其图灵完备所需的最少指令量，但不知道基于一个堆栈的语言是否甚至可以图灵完备。这些说明就足够了吗？

我已经查看了几个问题和答案（例如这个和这个），并相信上述说明就足够了。我对么？还是我需要其他的东西，比如函数调用、变量或另一个堆栈？

如果这些说明足够，它们中的任何一个都是多余的吗？

如果有一个没有变量或函数的图灵完备的单栈语言的例子，那就太好了。

“是否有可能在每一种图灵完备语言中创建一个 quine？ ” 说：

任何图灵完备的编程语言，并且能够输出任何字符串（通过作为程序的字符串的可计算函数——这是存在的每种编程语言都满足的技术条件）都有一个 quine 程序（并且，在事实上，无限多的 quine 程序，以及许多类似的好奇心）如下定点定理。

如果我创建了具有以下输出处理程序的语言 X：

这可以防止以任何方式输出源。

如果语言 X 的解释器一直在屏幕上检查它的源并且找到了源，它会在它到达屏幕之前被删除。

鉴于空程序会抛出非空白错误，Language X 是否仍然是图灵完备的？为什么？

我理解计算机是图灵完备的概念（具有 MOV 或命令或 SUBNEG 命令，因此能够“合成”其他指令，例如）。如果这是真的，那么拥有 100 条像 x86 这样的指令的目的是什么？是提高效率吗？

我参加了 Martin Odersky 关于 Scala 未来的主题演讲：

https://skillsmatter.com/skillscasts/8866-from-dot-to-dotty

在 1:01:00，对观众问题的回答似乎是说未来的 Scala 不会是图灵完备的。

我理解正确吗？Scala 3 将不再是图灵完备的吗？如果是这样，这对像我这样每天在工作中使用 Scala 解决实际问题的人有什么实际影响？换句话说，工业 Scala 程序员失去了什么，他们通过移除图灵完备性获得了什么？