turing-complete - 我的编程语言中的 quine 看起来如何？

Question

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

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

我的语言只有以下

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

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

Answer 1

如果你有整数，你可以对字符串进行编码或解码（如 A=1、B=2 等简单的方案就足以做到这一点）。您只需要能够比较常量字符串或比较 int。因此，似乎没有根本问题。

你处理数字并写下类似的东西

if (n == 1) print "A"
if (n == 2) print "B"
...

可能会遇到一些实际困难。字符串的问题不是你有字符，而是它们相当于非常大的数字。您在这里需要的是访问无限精度数字或某种固定大小数字的数组或其他大型数据结构。一个数字数组将为您做一个字符串可以做的事情。但是，如果您的语言是图灵完备的，它应该有一种方法可以轻松访问一些大块内存

图灵完备的语言仅限于 32 位磁带（或者您必须为每个不同的 32 位内存空间指定一个新名称）将是一个遗憾，不确定您是否可以编写具有这种限制的 quine。顺便说一句，如果您没有数组或类似结构，那么知道您如何证明您的语言是图灵完备的会很有趣。我通常使用的常用方法是使用我的语言实现一些图灵机。但要做到这一点，我需要某种阵列来模拟乐队。

这种编码基本上是哥德尔在不完全定理中所做的，找到某种方法将逻辑表达式编码为整数，然后对其进行推理。

如果你提供更多的语法元素，我们甚至可以尝试这样做（如果你没有函数而只有 goto，那也会是一个问题，但你也可以模拟它）。基本问题是您必须找到一种“压缩”编码源代码的方法。如果您有可用的长字符串常量，它可能会有所帮助。

Answer 2

如果您的语言是图灵完备的并且只有一种 quine，那么它们很可能是无限多的。这是一种构建其中一些的方法：

1. 用您的语言实现Brainfuck（或其他一些简单的图灵完备语言）解释器。编写程序，使源X1<brainfuck source>Y1在运行时解释 Brainfuck 程序。
2. string f(string a, string b)用你选择的任何语言编写一个算法，当给定 any 时a，b输出一个 Brainfuck 程序，当运行时输出 string a，整个 Brainfuck 源代码，然后是 string b。您可以调整现有的 Brainfuck quine 来执行此操作。
3. 计算f(X1, Y1)然后将生成的 Brainfuck 程序从 1 嵌入到您的程序中。

第一步是最困难的，但您可能已经完成了，因为证明某事物是图灵完备的最简单方法之一是为已经被证明是图灵完备的另一种语言实现解释器。

第二步已被证明是可行的，并且与您的程序语言无关。

第三步是一个简单的计算。

Answer 3

显然，您的编程语言中的程序是一个字符串。quine 的输出是一个程序。

因此，quine 的输出是一个字符串。如果您没有任何字符串操作，则不可能编写一个。

您应该以数字编码您的程序（而不是简单的可读文本编码）或实现字符串操作。