logo标签列表

一个编程语言能否是图灵完备但在其他方面不完备？

language-agnosticcompiler-constructionprogramming-languageslanguage-theoryturing-complete
10
例如，编写操作系统时是否存在某些无法在图灵完备语言中实现的事情？
10个回答
17

没有。至少，如果您找到一种这样的语言，那么这将是对 Church-Turing Thesis 的证伪。

然而，存在一些图灵完备的语言，但在其中编写某些程序会非常麻烦，例如FORTRAN中的字符串处理、COBOL中的数值编程、sed中的整数算术以及x86汇编中的几乎所有内容。

当然还有brainfuck。

1
已为您修复链接。由于某些原因，某些浏览器在复制链接时无法正确转义URL... - Shog9
2
是的，这种情况经常发生 - 客户端Markdown预览引擎比服务器端渲染引擎更容易处理。 - Shog9
1
那么，戴夫，我猜你是在暗示有些“合理的计算”无法由图灵机计算？你能展示一个吗？ - Charlie Martin
1
我将捐赠一美元给第一个用Brainfuck编写出可运行的引导程序的人。 - kibibu
1
@sblom 不要说你不理解的数学陈述。你刚才做的是重申我的第二段。证明：你肯定可以用机器码做这些事情。任何图灵完备的语言都可以用来编写汇编器以生成所需的机器码，或将该代码插入到内存中。因此，只要付出足够的努力，任何图灵完备的语言都可以直接与硬件交互，这足以驳斥你的说法。 - Charlie Martin
显示剩余4条评论
9

是的，你可以有一种语言，它不允许你直接操作硬件。例如，使用 Bourne shell 编写操作系统会很困难。但这些限制比你想象的要少。操作系统已经用 Standard ML、Scheme 甚至 Haskell 编写过了！

嗯... 图灵机是图灵完备的，对吧？它又如何允许"直接操纵硬件"？ - Pavel Feldman
我的意思是“直接操作硬件”不是语言完整性的问题。如果语言没有goto、循环运算符和子程序，那么它就是不完整的，因此你无法编写循环程序。 - Pavel Feldman
2
@Pavel：问题是，“是否有其他有趣的完整性概念”。我的回答是，“是的，可以访问MMU页表和其他硬件。” cat、ls、grep、ping是用C语言编写的，而不是bash。如果你只有bash，并且没有Unix系统调用，我认为你无法实现Unix系统调用。 - Norman Ramsey
我的答案是，“访问MMU页表和其他硬件”不是主要的语言问题，也与语言完整性无关。它是其他某些因素的不完整性。当然，为了简单起见，您可以说这是语言的不完整性，并且您会被理解，但这种不完整性与图灵所思考的不完整性远不相同。您编写“mov ax，bx”，CPU将执行此操作。您编写“cat /etc/passwd”，操作系统将执行此操作。这是环境/编译器的问题。您编写for（int i = 0; i <10; i ++）{}-那么就是语言。 - Pavel Feldman
@Pavel：没错。看看问题。问题是关于“其他事情的不完整性”。马已经死了，你可以停止打它了... - Norman Ramsey
显示剩余5条评论
9
图灵完备是最通用的完整性定义。某些应用程序需要的语言功能是必需的，但这些功能并不适用于正式定义。
例如，图形能力、产生后台进程的能力、持久化状态的能力以及连接网络的能力等都是有用的功能，但与语言的图灵完备性无关。因此，在Google App Engine上的Python或在沙盒中运行的Java小程序仍然是图灵完备的。
你会注意到，在许多情况下，这些类型的功能是由库提供的，而不是由核心语言提供的。
图形能力、生成后台进程的能力、持久化状态的能力以及连接网络的能力都是非常有用的功能，但在大多数情况下它们并不是语言特性，而是在库中实现的。例如，将类字段设置为受保护或私有、向方法添加属性等功能虽然有用，但并不是必需的完整性功能。 - Pavel Feldman
哦，大家好啊，你们觉得这些库是怎么写出来的呢？ - Charlie Martin
6

如果您在谈论语用学，那么当然...您可以想象一种没有读写文件能力的编程语言（例如，一个可以计算任何整数函数但仅限于此的语言）... 仅仅因为一种语言不能操作我的烤面包机并不意味着它不是图灵完备的，但这确实意味着它有一些事情做不了，所以我不确定这种区别有多么“重要”或有用。

你可以想象一种编程语言，它没有读写文件的能力。比如C++。fopen、fread和fclose不是语言的一部分，它们在库里。以x86汇编为例，根本没有文件。只有硬件中断。 - Pavel Feldman
任何图灵完备语言都可以操作你的烤面包机，你只需要编译器。 - Pavel Feldman
“仅仅因为一种语言不能操作我的烤面包机并不意味着它不是图灵完备的，但这确实意味着它有些事情无法做到” - 如果一种语言是图灵完备的，那么它就没有任何无法完成的事情。你需要更好的编译器和环境来完成某些任务。语言可以或者不能够使用循环、类、函数、属性、模板和数据结构。编译器可以或者不能够将这种语言转换成CPU（或其他环境，如JVM）指令。 - Pavel Feldman
@Pavel：首先，你需要让这个烤面包机可以（软件）编程。只有在这种情况下，你才能说“你只需要一个编译器”。 - isekaijin
如果一种编程语言是图灵完备的，那么它没有做不到的事情。但这并不完全正确。如果一种语言是图灵完备的，那么它没有无法解决的可判定问题。从数学角度来看，它可能无法与烤面包机交互，但可以模拟一个烤面包机。它也无法解决停机问题，因为没有图灵机能够解决该问题。 - Peeja
5
根据上下文，“用某种语言完成某事”对不同的人来说有不同的含义。图灵是其中之一，并且他非常准确地定义了他所谓的“完成”。
如果一种语言（或理论上的计算机）是图灵完备的，那么它无法做出任何图灵计算都无法实现的计算。这并不意味着该语言是万能的，只是它擅长计算。有许多“事情”不是图灵计算，因此一个图灵完备的计算机可能无法做到。
“成为操作系统”不是图灵计算。要成为操作系统，你需要做的事情不仅仅是计算，还需要操纵硬件。
给定一个图灵完备的语言，以及执行所有所需硬件操纵的操作的一组操作，包括适当的输入和时间概念，您可以编写操作系统。或者我应该说，编写操作系统是可能的。您能否亲自完成取决于语言使用的难易程度以及图灵定义忽略的物理限制，比如生成的程序是否真正适合并在所需设备的内存中执行，并在现实时间内运行。
尽管忽略实际限制 - 是的，您可以在任何图灵完备的语言中编写操作系统，前提是该语言也具有足够的操作来驱动硬件。如果您希望采用实际的计算机科学方法区分语言和库调用，“库调用”就可以了。图灵没有进行这样的区分，因为他的计算模型根本没有“调用”的概念。您还需要解决引导问题 - 要么您的硬件必须直接运行您编写的语言，要么您需要一个编译器编译成硬件可以运行的语言，或者您需要用硬件可以运行的语言编写一个解释器。同样，图灵忽略了所有这些，因为他的计算模型使用抽象硬件，而编写操作系统则涉及硬件。
用英语（而不是计算机科学术语），通常会说某种语言“缺少某些功能”，并且可以争辩说与拥有这些功能的另一种语言相比，它因此“不完整”。例如，人们可能会反驳说在C中可以实现闭包。例如，可以编写一个C程序作为Lisp解释器，并将Lisp程序嵌入其中作为字符串。嘿，C中有闭包。然而，如果他们说：“我希望C有闭包”，那么大多数人并不是在寻求这种方案。如果您认为每种语言都需要闭包，那么C就是不完整的。如果您认为每种语言都需要结构化编程，则ARM汇编语言是不完整的。如果您认为应该可以将方法动态添加到对象中，则C ++是不完整的，即使您可以完全编写一个C ++类来实现“AddMethod”和“CallMethodByName”方法，并从中伪造自己的方法调用约定等等。
图灵认为语言不需要这些方便：它们不会影响可以执行的计算，只是使编写某些程序更容易。图灵完备性概念与程序的外观或组织方式无关，仅与其输出有关。因此，这些语言是图灵完备的，但从程序员的角度来看，这些语言无法完成某些任务。
3
语言可以或不能执行如子程序、递归、自定义数据类型、循环、定义类、goto等操作。这样的语言特性集决定了它是否完整。例如，如果没有循环、goto和子程序，则语言是不完整的-您无法执行任何循环操作。语言的完整性是非常理论化和科学化的事情。例如，已经证明即使您的语言不允许递归调用函数，但允许函数指针-您也可以模拟递归，即使用y组合器。
像处理文件和硬件之类的东西通常不是语言的一部分。要完成任何编程任务，您需要比语言更多。您需要程序运行的环境。在x86中作为语言，您有带有单个参数的“int”指令，但当您执行“int 21h”时，这取决于操作系统执行某些操作。
语言只需要与环境交互的某种方式并且是完整的-然后由环境来处理它。在x86汇编中写入“mov ax，bx”是有效的，但是由您的CPU执行此操作。
以其他方式不完整-很容易，只需定义自己的完整版本。即我讨厌没有基于类的OOP工作，因此让我们定义如果没有支持基于类的OOP的语言功能，则该语言不完整。好的，那么C和Javascript不是F-完整的。您仍然可以在这些语言中做任何事情，甚至在某种程度上模拟基于类的OOP。
关于操作系统-您仍需要运行指令的处理器和将语言转换为CPU指令的编译器。我可以想象编译器将任何内容转换为机器代码。例如，以下是有效的JS代码。
for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

并且将其编译成机器码也不应该很难。

在现代世界中，你不仅选择语言，还选择平台、标准和非标准库、文献、社区、支持等。所有这些都影响你完成某些事情的能力，而它们一起可能是或可能不是对于你的任务“足够完整”。但如果我不能将C++代码编译为Java小程序，这并不意味着C++语言不完整。这只是缺少将C++代码转换为JVM可加载内容的编译器。

如果你想要，你可以设计一种具有“OpenFile、PingNetworkHost、DownloadMpeg4FileOverHttpsAndPlayBackwards”等语言特性的语言。但如果语言没有它们，它们仍然可以通过其他语言特性和环境支持实现，因此缺乏这些特性并不会使语言不完整。如果你的语言类似于C，但没有goto运算符、循环运算符（for、while、do while）和函数，则无法编写循环程序，也没有环境和库可以帮助你。

1
答案是肯定的。图灵完备性只意味着一个图灵完备语言可以用来计算任何可计算函数。首先，它并没有说明计算的复杂度。
通常可以预期，任何多项式时间算法都可以表示为另一种图灵完备语言中的多项式时间算法，但仅此而已。特别是任何实时要求（软性或硬性）都会被忽略，如果你的唯一关注点是图灵完备性。
另一个重要的事情是语言的表达能力，这在很大程度上是一种主观属性，但你可以欣赏到，在任何机器代码中编写程序比在Java中编写程序要困难得多。
至于操作系统，与硬件的接口是必须的，但任何语言都可以配备这样的实用程序。
[编辑] 我想补充的另一件事是，由于我们有限的计算机器的本质，任何编程语言的实际实现都不是图灵完备的。虽然 Church-Turing 命题以及相关的开创性发现（如停机问题）奠定了我们对计算的理解基础，但它们很少涉及实际计算的世界。
0
不完整的可用性 :)
0

当谈到编程语言时，通常认为这些语言运行在一些非常简单的机器上。因此，任何从文件中读取或访问网络的概念通常不会考虑到语言的能力。

有不同类别的编程语言经常用于可计算性理论（每种语言都有无数的修改版本）。

有限状态自动机。这是最简单的机器类别，它们可以识别最小的语言类别，这恰好是正则表达式可以识别的确切语言，例如：字符串是否以两个“a”开头并以“d”结尾。它们无法用于识别字符串是否包含一个平衡的括号集。
下推自动机。这实质上是带有堆栈的有限状态自动机扩展。与有限状态机不同，它们可以用于判断特定字符串是否包含平衡的括号集。下推自动机能够识别的语言恰好是可以使用上下文无关语法描述的语言集合，并且它们通常用于解析源代码。
图灵机。这些是这里机器类别中最强大的，但这并不意味着它们可以用来回答所有问题。它们无法回答这个问题：这个字符串是否描述了一个永远运行的图灵机？事实上，任何图灵机都不能对任何图灵机的非平凡属性做出任何判断（Rice 定理）。
因此，图灵机确实有局限性，而且有些机器类别能够做到图灵机无法做到的事情，但它们只存在于理论上（很可能），而不是在实践中。
0

我认为，除了图灵（或正则表达式、下推自动机）之外的完备性定义对于语言并不相关。但是这种完备性仅针对数字或符号计算设施。

你提到的事情在我看来更多地是运行时和环境的功能，而不是语言本身。这是一个重要的区别，形式上的完备性概念通常只适用于语言本身。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接