用任何一个图灵完备的编程语言可以实现另一个图灵完备的编程语言 这个理论出自哪里？

2022-08-05 22:46:49 +08:00
 edis0n0
1110 次点击
所在节点    程序员
1 条回复
yanqiyu
2022-08-06 01:43:20 +08:00
图灵等价，图灵等价意味着这个计算系统和通用图灵机能互相模拟，这要求这个计算系统能计算得到函数是且只能是图灵可计算函数

如果编程语言具体到现实存在的计算机上的编程语言，它们一定不会是超图灵完备的（不能计算非图灵可计算函数），所以图灵完备就是图灵等价

要是编程语言包含假象中的神谕机上的语言就不一定了，两个语言有可能一个只是图灵完备，一个超图灵完备

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/870996

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX