是否有可能用每种图灵完整的语言创建一个quine？

Question

我只是想知道它是否100%可能,如果我的语言是turing-complete,写一个打印出来的程序(当然不使用文件读取功能)

因此,如果语言只有真正必要的东西,以使其完成(我会证明通过将Brainf*ck代码翻译成它),如输出,变量,条件和gotos(地狱是的,得到的),我可以尝试在里面写一个quine？

我也问这个问题,因为我不确定quin是否直接符合图灵定律,即图灵机能够完成任何计算任务.我只是想知道,所以我不会尝试多年而不知道这可能是不可能的.

Answer 1

任何编程语言是图灵完备,并且能够输出任何字符串(由字符串作为程序的可计算函数 - 这是一个技术条件是满足的存在每种编程语言)具有奎因程序(和,在事实上,无限多的quine程序,以及许多类似的好奇心如下定点定理.

看这里

Answer 2

几个月前我遇到了这个问题.

虽然写奎因并不一定证明语言是图灵完备,这是一个强烈的暗示;)至于图灵完备去,如果你能(像你说的),从语言到另一种图灵完备提供有效的翻译语言,然后你的语言是图灵完成.

话虽这么说,任何可以输出字符串的Turing Complete语言都应该能够生成一个quine.另外,来自维基百科:

当执行环境被视为一个函数时,quine是执行环境的固定点.作为Kleene递归定理的直接结果,Quines可以在任何能够输出任何可计算字符串的编程语言中使用.为了娱乐,程序员有时会尝试用任何给定的编程语言开发最短的quine.