是否有可能用每种图灵完备的语言创建一个 quine？
我只是想知道如果我的语言是图灵完备的，是否 100% 可能在其中编写一个将自身打印出来的程序（当然不使用文件读取功能）
所以如果该语言只有真正必要的东西为了使它图灵完备（我会通过将 Brainf*ck 代码翻译成它来证明这一点），比如输出、变量、条件和 gotos（是的，gotos），我可以尝试在其中编写一个 quine 吗？
我问这个问题也是因为我不确定奎因是否直接符合图灵定律，即图灵机能够执行任何计算任务。 我只是想知道，这样我就不会尝试多年而不知道这可能是不可能的。
I just wanted to know if it is 100% possible, if my language is turing-complete, to write a program in it that prints itself out (of course not using a file reading function)
So if the language just has the really necessary things in order to make it turing complete (I would prove that by translating Brainf*ck code to it), like output, variables, conditions and gotos (hell yes, gotos), can I try writing a quine in it?
I'm also asking this because I'm not sure that a quine directly fits into Turing's law that the turing machine is capable of any computational task.
I just want to know so I don't try for years without knowing that it may be impossible.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
参见此处
See here
几个月前我遇到了这个问题。
虽然编写奎因并不一定证明一种语言是图灵完备的，但这是一个强烈的建议;)就图灵完备而言，如果您可以（就像您所说的那样）提供从您的语言到另一种图灵完备的有效翻译语言，那么你的语言就是图灵完备的。
话虽这么说，任何可以输出字符串的图灵完备语言都应该能够生成 quine。另外，来自维基百科：
I ran into this issue a couple of months ago.
While writing a quine doesn't necessarily prove that a language is Turing Complete, it is a strong suggestion ;) As far as Turing Completeness goes, if you can (like you said) provide a valid translation from your language to another Turing-Complete language, then your language is Turing Complete.
That being said, any language that is Turing Complete that can output a string should be able to generate a quine. Also, from Wikipedia:
一种编程语言可能无法打印其表示形式中的所有符号。例如，I/O 可能仅限于 7 位 ASCII 字符，并且语言关键字为阿拉伯语。这是我能想到的唯一例外。
It is possible to have a programming language that cannot print all the symbols in its representation. For example, the I/O may be limited to 7-bit ASCII characters with language keywords in Arabic. That's the only exception I can think of.
嗯，从技术上讲，并不总是如此。根据维基百科上的证明，编程语言必须是可接受的编号。实用且理智的图灵编译编程语言都是可接受的编号。如果可以在图灵编译编程语言和另一种可接受的编号之间进行转换，那么图灵编译的编程语言就是一种可接受的编号。
图灵完备的编程语言示例，不是可接受的编号：
源代码始终包含一个或两个双引号转义字符串。如果输入为空，如果有两个字符串，则输出第一个字符串；如果有一个，则永远循环。否则，使用原始输入作为输入来计算 Python 中的最后一个字符串。
这不是一个可接受的编号，因为对于一个 Python 程序，我们必须知道它在输入为空时的行为，才能将其翻译成这种语言。但我们可能永远不知道这是否是一个无限循环，因为我们无法解决停止问题。不过，我们知道翻译总是存在的。
用这种语言写 quinine 是不可能的。
Well, technically, not always. According to the proof on Wikipedia, the programming language has to be an admissible numbering. Practical and sane Turing-complate programming languages are all admissible numberings. And a Turing-complate programming language is an admissible numbering if it's possible to translate between that and another admissible numbering.
An example Turing-complete programming language that is not an admissible numbering:
The source code always contains one or two doublequoted escaped strings. If the input is empty, output the first string if there are two strings, or loop forever if there is one. Otherwise, evaluate the last string in Python, using the original input as input.
It's not an admissible numbering because, given a Python program, we have to know its behavior when the input is empty, to translate it into this language. But we may never know if it is an infinite loop, as we cannot solve the halting problem. We know a translation always exists, though.
It's impossible to write quines in this language.