例如，在编写操作系统时，是否有某些事情无法用图灵完备的语言来完成？
问问题
3227 次
10 回答
17
不，或者至少如果你发现一个会反驳Church Turing Thesis的论文。
然而，有些语言是图灵完备的，但编写某些程序是一件非常痛苦的事情，例如，FORTRAN 中的字符串处理、COBOL 中的数值编程、sed 中的整数运算，几乎所有东西都在 x86 汇编程序中。
然后当然还有brainfuck。
于 2009-05-01T23:13:05.193 回答
9
是的，您可以使用一种不允许您直接操作硬件的语言。例如，很难使用 Bourne shell 编写操作系统。但这些限制比你想象的要少。操作系统已经用标准 ML、Scheme 甚至Haskell编写！
于 2009-05-01T23:12:47.160 回答
9
图灵完备是完整性的最一般的正式定义。某些应用程序需要一些语言特性，但这些特性不符合正式定义。
例如，图形功能、生成后台进程的能力、保持状态的能力以及连接到网络的能力都是有用的功能，但与语言的图灵完备性无关。因此，Google App Engine 上的 Python 或在沙箱中运行的 Java 小程序仍然是图灵完备的。
您会注意到，在许多情况下，这些类型的功能是由库而不是核心语言提供的。
于 2009-05-01T23:13:05.053 回答
6
如果您说的是语用学，那么当然...您可以想象一种无法读取或写入文件的编程语言（例如，一种可以在整数上计算任何函数的语言，仅此而已）... 仅仅因为一种语言可以'不操作我的烤面包机并不意味着它不是图灵完备的，但它确实意味着它不能做一些事情，所以我不确定这种区别有多“重要”或有用。
于 2009-05-01T23:15:06.407 回答
5
根据上下文，“用一种语言完成某事”对不同的人意味着不同的事情。图灵就是其中之一，他非常准确地定义了“完整”的含义。
如果一种语言（或理论机器）是图灵完备的，那么就没有它不能进行的图灵计算。这并不意味着该语言是无所不能的，只是它擅长求和。有许多“事情”不是图灵计算，因此图灵完备的计算机可能无法做到。
“成为一个操作系统”不是图灵计算。要成为一个操作系统，你需要做的不仅仅是计算。您还需要操作硬件。
给定一门图灵完备的语言，以及一组用于完成所需的所有硬件操作的操作，包括合适的输入和时间概念，您就可以编写一个操作系统。或者我应该说，可以编写操作系统。你个人是否能做到这取决于语言的易用性，以及图灵定义忽略的物理限制，例如生成的程序是否真的适合并在你希望它运行的设备的内存中执行，并在现实时间运行。
尽管忽略实际限制 - 是的，您可以使用任何图灵完备语言编写操作系统，前提是该语言还具有足够的操作来驱动硬件。“库调用”，如果您希望采用实用的 CS 方法将语言与库区分开来。图灵没有做出这样的区分，因为他的计算模型无论如何都没有“调用”的概念。您还需要解决引导程序问题 - 您的硬件必须直接运行您正在编写的语言，或者您需要将编译器编译成硬件可以运行的语言，或者您需要使用一种语言编写的解释器硬件运行。同样，图灵忽略了这一切，因为他的计算模型使用抽象硬件，而编写操作系统完全是关于硬件的。
在英语（而不是 CompSciSpeak）中，通常会说一种语言“缺乏某些特征”，因此与具有这些特征的另一种语言相比，可以说它是“不完整的”。有人可能会反驳说可以在 C 中实现闭包。例如，可以编写一个作为 Lisp 解释器的 C 程序，并将 Lisp 程序作为字符串嵌入其中。瞧，C 中的闭包。但是，如果他们说“我希望 C 有闭包”，这并不是大多数人所要求的。如果您认为每种语言都需要闭包，那么 C 是不完整的。如果您认为每种语言都需要结构化编程，那么 ARM 汇编程序是不完整的。如果您认为应该可以为对象动态添加方法，那么 C++ 是不完整的，即使完全可以使用 "
图灵认为语言不需要任何这些便利：它们不影响可以执行的计算，只影响编写某些程序的难易程度。图灵完备性的概念与程序的外观或组织方式无关，仅与输出的内容有关。所以这些语言是图灵完备的，但是从程序员的角度来看，有些事情是那些语言无法完成的。
于 2009-05-02T11:35:51.383 回答
3
语言可以或不能做诸如子例程、递归、自定义数据类型、循环、定义类、转到等之类的事情。这样的语言特性集使其完整或不完整。例如，如果您没有循环、goto 和子例程，则语言是不完整的 - 您无法执行任何循环操作。语言完整性是一个非常理论和科学的东西。例如，即使您的语言不允许递归调用函数，但允许函数指针，它也被证明 - 您可以模拟递归，即使用 y-combinator。
像处理文件和硬件这样的东西通常不是语言的一部分。要完成任何编程任务，您需要的不仅仅是语言。您需要程序工作的环境。在 x86 作为语言中，您有带有单个参数的指令“int”，但是当您执行“int 21h”时，由操作系统来执行某些操作。
语言只需要某种方式与环境沟通并完成 - 然后由环境来处理它。在 x86 asm "mov ax,bx" 中写入是有效的，但执行此操作取决于您的 CPU。
以其他方式不完整 - 简单，只需定义您自己的完整性版本。即，我讨厌在没有基于类的 OOP 的情况下工作，所以让我们定义如果语言没有支持基于类的 OOP 的语言特性，它就不是 Feldman 完备的。好吧，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）和函数，那么你不能编写循环程序，没有环境和库可以帮助你。
于 2009-05-02T00:05:21.090 回答
1
答案是最肯定的。图灵完备性仅意味着图灵完备语言可用于计算任何可计算函数。一方面，它没有说明计算的复杂性。
您通常可以期望任何多项式时间算法都可以用任何其他图灵完备语言表示为多项式时间算法，但仅此而已。如果您唯一关注的是图灵完整性，那么任何实时要求（软或硬）都不会出现。
另一个重要的事情是语言的表达能力，这在很大程度上是一种主观属性，但是您可以理解，用任何机器代码编写程序都比使用 Java 更难。
至于操作系统，硬件接口是必须的，但任何语言都可以安装这样的实用程序。
[编辑] 我可能要补充的另一件事是，由于我们有限计算机的性质，没有任何编程语言的实际实现是图灵完备的。虽然 Church-Turing 论文以及相关的开创性发现（如停机问题）为我们理解计算奠定了基础，但它们很少遇到实际计算的世界。
于 2009-05-02T12:02:24.453 回答
0
不完整的可用性:)
于 2009-05-02T11:51:26.027 回答
0
当谈论语言时，通常假设语言在一些非常简单的机器上运行。因此，任何从文件读取或访问网络的概念通常不会考虑到语言的能力。
可计算性理论中经常使用不同类别的语言（每种语言都有几乎无穷无尽的修改）
- 有限自动机。这是最简单的机器类别，它们可以识别最小的语言类别，这恰好是正则表达式可以识别的确切语言，即。字符串是否以两个 'a' 开头并以 d 结尾。它们不能用于识别字符串是否包含一组平衡的括号 fx。
- 下推自动机。这本质上是具有堆栈的有限自动机的扩展。与有限状态机不同，它们可用于判断特定字符串是否包含一组平衡的括号。下推自动机可以识别的语言正是可以使用上下文无关语法描述的集合，它们通常用于解析源代码。
- 图灵机。这些是这里同类机器中功能最强大的，但这并不意味着它们可以用来回答所有问题。他们无法回答这个字符串是否描述了将永远运行的图灵机的问题？事实上，任何图灵机都无法说明任何图灵机的重要属性（赖斯定理）。
所以是的，图灵机有局限性，有些机器可以做图灵机不能做的事情，但它们（很可能）只在理论上存在，在实践中更新。
于 2009-05-02T12:21:04.347 回答
0
我认为除了图灵（或正则表达式，或下推自动机）之外的完整性定义与语言无关。但这种完整性仅适用于数字或符号计算设施。
在我看来，您提到的东西更像是运行时和环境的功能，而不是语言。有一个重要的区别，完整性的正式概念通常只适用于语言本身。
于 2011-11-05T01:41:37.227 回答