我只是想知道是否有 100% 的可能，如果我的语言是图灵完备的，在其中编写一个可以打印出来的程序（当然不使用文件读取功能）
因此，如果该语言只有真正必要的东西才能使其完整（我会通过将 Brainf*ck 代码翻译成它来证明这一点），比如输出、变量、条件和 goto（地狱是的，gotos），我可以尝试在里面写一个quine？
我也在问这个问题，因为我不确定 quine 是否直接符合图灵机能够执行任何计算任务的图灵定律。我只是想知道，所以我不会尝试多年而不知道这可能是不可能的。
问问题
3876 次
4 回答
32
任何图灵完备的编程语言，并且能够输出任何字符串（通过作为程序的字符串的可计算函数——这是存在的每种编程语言都满足的技术条件）都有一个 quine 程序（并且，在事实上，无限多的 quine 程序，以及许多类似的好奇心）如下定点定理。
于 2010-04-02T17:15:39.857 回答
5
几个月前我遇到了这个问题。
虽然编写 quine 并不一定证明一种语言是图灵完备的，但这是一个强烈的建议；）就图灵完备而言，如果您可以（如您所说）提供从您的语言到另一种图灵完备的有效翻译语言，那么你的语言就是图灵完备的。
话虽如此，任何可以输出字符串的图灵完备语言都应该能够生成 quine。此外，来自维基百科：
当执行环境被视为一个函数时，quine 是执行环境的固定点。Quines 在任何能够输出任何可计算字符串的编程语言中都是可能的，这是Kleene 递归定理的直接结果。为了消遣，程序员有时会尝试在任何给定的编程语言中开发尽可能短的 quine。
于 2010-04-02T17:22:12.367 回答
4
可能有一种编程语言无法打印其表示中的所有符号。例如，I/O 可能被限制为带有阿拉伯语语言关键字的 7 位 ASCII 字符。这是我能想到的唯一例外。
于 2010-04-02T19:17:03.550 回答
3
好吧，从技术上讲，并非总是如此。根据Wikipedia 上的证明，编程语言必须是可接受的编号。实用且理智的图灵兼容编程语言都是可接受的编号。如果可以在图灵兼容的编程语言和另一个可接受的编号之间进行转换，那么图灵兼容的编程语言就是一种可接受的编号。
一个示例图灵完备的编程语言，它不是一个可接受的编号：
源代码总是包含一个或两个双引号转义字符串。如果输入为空，如果有两个字符串则输出第一个字符串，如果有一个则永远循环。否则，使用原始输入作为输入计算 Python 中的最后一个字符串。
这不是一个可接受的编号，因为给定一个 Python 程序，我们必须知道它在输入为空时的行为，才能将其翻译成这种语言。但我们可能永远不知道它是否是一个无限循环，因为我们无法解决停机问题。不过，我们知道翻译总是存在的。
用这种语言写 quines 是不可能的。
于 2017-06-01T11:41:02.820 回答