问题标签 [turing-complete]

我将 sed 用于批量 ptovess，而我无法使用 awk 来完成。awk 能做到吗？还是更多的是选择问题并调用 awk 和 sed 等效的用法。他们都使用 i/o 进行常见的搜索替换。有没有一个很好的例子，一个不能做而另一个不能做？

如果一种语言具有控制结构和变量，但不支持数组、列表、内存访问和分配等，它可以是图灵完备的吗？

也许如果您可以创建的变量数量没有限制，您可以通过创建像array_1, array_2, ...之类的变量来模拟数组array_6000并手动循环它们，并以某种方式创建复杂的数据结构和递归？

编辑：即使您不能通过名称操作访问变量（array_10+i不允许）？

我不太了解图灵机的整个想法。

我目前的任务是制造一台繁忙的海狸图灵机。但我没有真正得到的是它模拟输入。那么我模拟什么样的输入呢？例如，它问我 3 州忙碌的海狸机器在磁带上写了多少个 1？我确定我需要写一个图灵机，但是一旦我有了它，我该怎么办呢？

我应该用什么字符串来模拟它？

安全元组关系演算是图灵完备的语言吗？

据我所知，CSS 不是图灵完备的。但是我对 CSS 的了解非常有限。

• CSS Turing 是否完整？
• 是否有任何现有的草案或委员会正在考虑可能实现图灵完整性的语言特性，如果不是现在？

我只是想知道是否有 100% 的可能，如果我的语言是图灵完备的，在其中编写一个可以打印出来的程序（当然不使用文件读取功能）

因此，如果该语言只有真正必要的东西才能使其完整（我会通过将 Brainf*ck 代码翻译成它来证明这一点），比如输出、变量、条件和 goto（地狱是的，gotos），我可以尝试在里面写一个quine？

我也在问这个问题，因为我不确定 quine 是否直接符合图灵机能够执行任何计算任务的图灵定律。我只是想知道，所以我不会尝试多年而不知道这可能是不可能的。

在每一种图灵完备语言中，是否有可能创建一个工作

• 自己的编译器，它首先在用其他语言编写的解释器上运行，然后编译它自己的源代码？（自举）

• 标准兼容 C++ 编译器，输出二进制文件，例如：Windows？

• 正则表达式解析器和评估器？

• 魔兽世界克隆？（假设语言获得了必要的 API 绑定，例如 OpenGL 和 WoW 源代码可用）

（这里的一切都是理论上的）

让我们以 Brainf*ck 作为示例语言。

我已经创建了一个图灵完备的编程语言（已经被证明），所以必须可以为它写一个quine，对吧？

但是我知道的所有 quines 都将它们的源代码存储在一个字符串中，然后使用类似chrand的东西替换其中的一个特殊字符ord。

我的语言只有以下

• 基本算术
• 整数和字符串类型
• 变量
• == 运算符
• 有条件的 goto

我不知道如何编写 quine，因为我没有可用的真正字符串操作，我只能输出常量字符串。然而，它是 100% 图灵完备的。

语言是图灵完备和 lisp 变体所需的最小原语集是多少？

似乎 car、cdr 和一些流控制以及 REPL 的东西就足够了。如果有这样的清单就好了。

假设只有 3 种类型的数据，整数、符号和列表。（就像在 picolisp 中一样）

我试图找到逻辑上的艾伦图灵解释为什么不能有一个程序来检查另一个程序。

我记得我们在计算课程上学过，但现在我找不到解决方案，我需要向工作中的某个人解释。

感谢帮助。