7

在每一种图灵完备语言中,是否有可能创建一个工作

  • 自己的编译器,它首先在用其他语言编写的解释器上运行,然后编译它自己的源代码?(自举

  • 标准兼容 C++ 编译器,输出二进制文件,例如:Windows?

  • 正则表达式解析器和评估器?

  • 魔兽世界克隆?(假设语言获得了必要的 API 绑定,例如 OpenGL 和 WoW 源代码可用)

(这里的一切都是理论上的)

让我们以 Brainf*ck 作为示例语言。

4

8 回答 8

8

图灵完备仅表达计算能力,与I/O能力无关!

于 2010-04-08T18:38:28.377 回答
8

在每一种图灵完备语言中,是否有可能创建一个工作...

如果一种图灵完备的语言可以做到,那么他们都可以。从这个意义上说,它们都同样“强大”。由于您描述的所有内容都已经存在于至少一种图灵完备语言中,因此这些程序中的任何一个都可以用任何其他图灵完备语言编写。

然而,仅仅因为某事是可能的并不意味着它是容易的,甚至是可行的。这是一个非常重要的区别,也是不同编程语言存在的关键所在。他们并非都同样擅长制作特定类型的软件——如果是,我们只需要一种语言!

于 2010-04-08T15:19:15.590 回答
5

不,图灵完备性与 I/O 和硬件无关。但是,您可以通过使用变量(或“内存磁带”)来假装存在 I/O、硬件系统和图形系统。在 BF 中,您可以将前 2 个单元格(xy)用于“假装”屏幕分辨率,然后将另一个x乘以y单元格用于屏幕上的所有像素,然后将下一个单元格(n)用于“假装”文件系统大小,然后是文件系统内容的下n 个单元...

于 2010-04-09T01:37:35.440 回答
2

是的,当然,所有这些。毕竟,这就是“图灵完备”的含义:它可以计算所有可以计算的东西。

于 2010-04-08T15:16:40.213 回答
1

图灵完备真正需要的是你可以做简单的数学运算,有一些变量,并且可以做一个while循环。或任何数量的等效事物。如果你想做真正的程序,你需要更多(特别是系统调用)并且你也必须担心效率(图灵机可能非常慢......)理论上图灵等效系统之间没有区别,但在实践中有。

如果有人在BF做魔兽客户端,我会印象深刻的!

于 2010-04-08T15:25:52.933 回答
0

可以用一种图灵完备语言实现的任何算法都可以用任何其他语言实现。您的问题更多地与操作系统服务和 API 有关,它们必须通过相关语言提供。

简而言之,从形式语言的角度来看,以上所有问题的答案都是肯定的。

于 2010-04-08T15:18:14.710 回答
0

理论上,是的。但一个更有趣的问题是,如果给定某种“深奥”的编程语言,它实际上是否可行。

于 2010-04-08T15:19:16.070 回答
-2

每种图灵完备语言都可以计算相同的函数集。所以,一个图灵完备的语言可以做你写的所有事情,因为这些东西是用其他图灵完备的语言计算的。

于 2010-04-08T15:19:47.530 回答