是否有可能建立在每一个图灵完备的语言奎因?
-
24-09-2019 - |
题
我只是想知道这是否是100%可能的,如果我的语言是图灵完备的,在这上面写一个程序,打印出自己(当然不是使用文件阅读功能)
因此,如果语言只是有真正所需的东西,以便使它图灵完整的(我将证明,通过翻译Brainf * CK代码吧),如输出,变量,条件和跳转(地狱是,goto方法)我可以尝试在它上面书写奎因?
我也问这个,因为我不知道,一个奎因直接融入图灵的法律,图灵机能够支持任何计算任务。 我只是想知道,所以我不数年而没有知道这是不可能的尝试。
解决方案
任何编程语言是 图灵完整,并能 输出任何字符串(由一个可计算 字符串作为程序的功能 - 这是一个技术条件就是 满足了所有的编程 存在语言)具有奎因 程序(和,事实上,无限多 奎因程序,和许多类似的 好奇心)由如下 固定点定理。
其他提示
我几个月前就遇到了这个问题。
在写一个奎因并不一定证明语言是图灵完备,这是一个强烈的暗示;)至于图灵完备去,如果你能(像你说的),从语言到另一种提供有效的翻译图灵完备的语言,那么你的语言是图灵完备。
这就是说,即图灵完整,能够输出一个字符串应该是能够产生喹任何语言。另外,从百科:
一个quine指的执行环境的一个固定点,当执行环境被视为一个函数。基内斯在有能力输出的任何可计算的字符串任何编程语言是可能的,由于克林的一个直接后果递归定理。用于娱乐,程序员有时尝试开发最短的喹在任何给定的编程语言。
有可能有一种编程语言,不能打印在其表示中的所有符号。例如,I / O可以被限制为7位ASCII字符与阿拉伯语的关键字。这是我能想到的唯一的例外。
当然,从技术上,并非总是如此。根据维基百科上中证明,编程语言必须是一个受理编号。实用和理智图灵complate编程语言都可以受理numberings。和图灵complate编程语言是否有可能到和其他受理编号之间进行转换的受理编号。
一个例子图灵完整的编程语言不是可容许的编号:
的源代码总是包含一个或两个doublequoted转义字符串。如果输入为空,输出的第一个字符串,如果有两个字符串,或永远循环下去,如果有一个。否则,评估在Python最后一个字符串,使用原始输入作为输入。
这不是一个受理编号,因为,给定一个Python程序,我们必须知道它的行为,当输入是空的,把它翻译成这种语言。但是,我们可能永远不知道,如果它是一个无限循环,因为我们解决不了的停机问题。我们知道,翻译一直存在,虽然。
这是不可能写入基内斯这个语言