每种图灵完备语言中都可以存在这种程序吗？
在每种图灵完备的语言中，是否有可能为自己创建一个工作
- 编译器，它首先在用其他语言编写的解释器上运行，然后编译它自己的源代码？ （Bootstrapping）
符合标准的 C++ 编译器，可输出二进制文件，例如：Windows？
正则表达式解析器和评估器？
魔兽世界克隆？ （假设该语言获得必要的 API 绑定，例如 OpenGL 和 WoW 源代码可用）
（这里的一切都是理论上的）
让我们以 Brainf*ck 作为示例语言。
In every Turing-Complete language, is it possible to create a working
Compiler for itself which first runs on an interpreter written in some other language and then compiles it's own source code? (Bootstrapping)
Standards-Compilant C++ compiler which outputs binaries for, e.g.: Windows?
Regex Parser and Evaluater?
World of Warcraft clone? (Assuming the language gets the necessary API bindings as, for example, OpenGL and the WoW source code is available)
(Everything here theoretical)
Let's take Brainf*ck as an example language.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
如果一种图灵完备的语言可以做到，那么它们都可以。从这个意义上说，它们都同样“强大” ”。由于您描述的所有内容都已经存在于至少一种图灵完备语言中，因此这些程序中的任何一个都可以用任何其他图灵完备语言编写。
但是，仅仅因为某件事可能并不意味着它容易，甚至可行。这是非常重要的区别，这是不同编程语言存在的关键。他们在开发特定类型的软件方面并不都同样擅长——如果他们是，我们只需要一种语言！
If one Turing-complete language can do it, then they all can. In this sense, they're all equally "powerful". Since everything you described already exists in at least one Turing-complete language, any of these programs can be written in any other Turing-complete language.
However, merely because something is possible doesn't mean it's easy, or even feasible. That's a hugely important distinction, and it's the crux of why different programming languages exist. They're not all equally good at making specific kinds of software -- if they were, we'd only need one language!
图灵完备只表达计算能力，不表达I/O能力！
Turing-Complete only express computation capability, nothing about I/O capability !
不，图灵完备性与 I/O 和硬件无关。
但是，您可以通过使用变量（或“内存磁带”）假装 I/O、硬件系统和图形系统存在。在 BF 中，您可以使用前 2 个单元格（x、y）作为“假装”屏幕分辨率，然后再使用另一个 x 倍 >y 个单元格代表屏幕上的所有像素，然后下一个单元格 (n) 代表“假装”文件系统大小，然后下一个 n 个单元格代表文件系统内容...
No, Turing completeness have nothing to do with I/O and hardwares.
However, you can pretend I/O, hardware systems and graphic systems existed by using variables (or the "memory tape"). In BF, you could use the first 2 cells (x, y) for the "pretended" screen resolution, then another x times y cells for all pixels on the screen, then next cell (n) for the "pretended" filesystem size, then next n cells for the filesystem content...
是的，当然，所有这些。毕竟，这就是“图灵完备”的含义：它可以计算所有可以计算的东西。
Yes, of course, all of those. That's what "Turing-complete" means, after all: it can compute everything that can be computed.
图灵完备真正需要的是你可以做简单的数学，有一些变量，并且可以做一个 while 循环。或任意数量的等效事物。如果你想做真正的程序，你需要更多一点（特别是系统调用）并且你还必须担心效率（图灵机可能非常慢......）理论上，图灵等效系统之间没有区别，但在实践中有。
如果有人在 BF 中开发了《魔兽世界》客户端，我会非常印象深刻！
All that being Turing-complete really requires is that you can do simple math, have some variables, and can do a while loop. Or any number of equivalent things. If you want to do real programs, you need a bit more (notably syscalls) and you have to worry about efficiency too (turing machines can be very slow...) In theory there's no difference between turing-equivalent systems, but in practice there is.
If anyone does a WoW client in BF, I will be very impressed!
任何可以用一种图灵完备语言实现的算法也可以用任何其他语言实现。您的问题更多地与操作系统服务和 API 有关，这些服务和 API 必须通过相关语言提供。
简而言之，从形式语言的角度来看，上述所有问题的答案都是肯定的。
Any algorithm that can be implemented in one Turing-Complete language can be implemented in any other. Your questions have more to do with the operating system services and APIs which must be made available through the language in question.
In short, the answer is yes to all of the above from a formal language point of view.
从理论上讲，是的。但一个更有趣的问题是，如果使用某种“深奥”的编程语言，这实际上是否可能。
Theoretical, yes. But a much more interesting question is if it would be practically possible given a certain "esoteric" programming language.
每种图灵完备语言都可以计算相同的函数集。
因此，图灵完备的语言可以完成您编写的所有操作，因为这些事情是用其他图灵完备的语言计算的。
Every Turing-Complete language could compute the same set of functions.
So, a turing-complete language could do all what you wrote because that things are computed with other turing-complete languages.