图灵完备是什么?

以下是最简单的解释:

图灵完整系统是指一个系统,在该系统中可以编写一个程序来找到答案(尽管没有关于运行时间或内存的保证)。

所以,如果有人说“我的新东西是图灵完全的”,这意味着在原则上(虽然通常不是在实践中),它可以用来解决任何计算问题。

有时候这只是个玩笑。。。一个人用虚拟仪器写了一个图灵机器模拟器,所以可以说虚拟仪器是世界上唯一需要的计算引擎。

这是最简单的解释

阿兰·图灵创造了一台机器,它可以接受一个程序,运行那个程序,并显示一些结果。但后来他不得不为不同的程序创建不同的机器。所以他创造了“通用图灵机”,可以运行任何程序。

编程语言与这些机器类似(尽管是虚拟的)。他们接受程序并运行它们。现在,一种编程语言被称为“图灵完成”,如果它可以运行任何程序(不管是哪种语言),只要有足够的时间和内存,图灵机器就可以运行。

例如:假设有一个程序,它接受10个数字并将它们相加。图灵机可以很容易地运行这个程序。但是现在想象一下,由于某种原因,您的编程语言无法执行相同的加法。这将使它“图灵不完整”(可以这么说)。另一方面,如果它可以运行通用图灵机器可以运行的任何程序,那么它就是图灵完备的。

大多数现代编程语言(如Java、JavaScript、Perl等)都是图灵完整的,因为它们都实现了运行程序所需的所有功能,如加法、乘法、if-else条件、返回语句、存储/检索/擦除数据的方法等。

"JavaScript Is Turing Complete" — Explained

非正式定义

图灵完备语言是一种可以执行任何计算的语言。这个 Church-Turing Thesis 声明任何可执行的计算都可以由图灵机完成。A. Turing machine 是一台具有无限随机访问内存和有限“程序”的机器,该程序规定何时应在该内存中读取、写入和移动,何时应以特定结果终止,以及下一步应做什么。图灵机的输入在启动前被放入内存中。

图灵机可以根据它在内存中看到的内容做出决策 -仅支持 + , - , * 和 /

-如果我们使用Java、Javascript或Python,并且删除了执行任何类型的循环、GOTO或函数调用的能力,那么它就不会是图灵完整的,因为它不能执行永远不会完成的任意计算。 Coq 是一个定理证明器,它不能表示不终止的程序,所以它不是图灵完备的。

图灵机可以使用无限内存 -一种与Java完全相似但一旦使用超过4G内存就会终止的语言就不是图灵完整的,因为图灵机器可以使用无限内存。这就是为什么我们不能 图灵机,但Java仍然是一种图灵机完整语言,因为Java 语言 没有阻止它使用无限内存的限制。这是正则表达式不是图灵完全的原因之一。

图灵机具有随机存取存储器 -一种只允许您通过 push pop 对堆栈的操作不会是图灵完成的。如果我有一种读字符串的“语言” 一旦 而且只能通过从堆栈中推和弹出来使用内存,它可以告诉我 ( ) 后来,当它看到的时候就推 当它看到的时候,会砰砰的一声 ) . 但是,它不能告诉我是否每个 有自己的 ) 过后 每一个 [ ] 稍后(注意 ([)] 符合此标准,但 ([]] () 和 [] 单独的,但是这种只有堆栈的语言不能。

图灵机可以模拟任何其他图灵机

图灵完备语言示例

如果您的语言有无限的随机访问内存、条件执行和某种形式的重复执行,那么它可能是图灵完全的。还有更多奇特的系统仍然可以实现图灵机器所能实现的一切,这使得它们也能完成图灵:

• 非类型lambda演算
• 康威的人生游戏
• 序言

从…起 wikipedia :

图灵完整性,以艾伦命名 图灵的重要性在于 计算机系统的合理设计 到目前为止先进的设备可以被模拟 通过通用图灵机 被称为 教堂图灵理论。因此 可以作为通用机器的机器 执行任何其他计算 可编程计算机能够进行编程。 让机器执行以下操作: 计算能力,或 计算。

而真正的图灵机 很可能是物理上不可能的, 因为它们需要无限的存储空间, 图灵完整性通常是松散的 归因于物理机器或 编程语言将是 如果他们有无限的 存储所有现代计算机都是计算机 图灵完全在这个意义上。

我不知道你们怎么能比这更非技术性,除了说“图灵完成意味着‘在足够的时间和空间内能够回答可计算的问题’”。

从根本上说,图灵完整性是一个简洁的要求,即无界递归。

甚至不受记忆的限制。

我独立地想到了这一点,但是 here is some discussion 对断言的解释。 My definition of LSP 提供更多上下文。

这里的其他答案并没有直接定义图灵完整性的基本本质。

Turing Machine . 这意味着任何可以由图灵机器计算的东西都可以由图灵完整系统计算。

还没有人发现一个系统比图灵机器更强大。因此,就目前而言,说一个系统是图灵完备的,就等于说这个系统和任何已知的计算系统一样强大(参见 Church-Turing Thesis ).

最简单的说,图灵完备系统可以解决任何可能的计算问题。

其中一个关键要求是草稿行大小必须是无界的,并且可以在写入草稿行之前倒带以访问。

我的理解很简单:

图灵完成:

1. 不 ,您必须使用javascript来执行添加。),因此HTML不是图灵完整的。

2. 像java、C++、python、javascript、EthUM的坚固性等语言是图灵完成的,因为你可以使用类似的语言来增加两个数字。

希望这有帮助。

@马克,我认为你所解释的是通用图灵机和图灵机的混合描述。

在实际意义上,图灵完备的东西将是一台机器/过程/计算,能够被编写并表示为一个程序,由一台通用机器(台式计算机)执行。虽然它没有考虑到时间或存储,正如其他人提到的。

Brasilford教授在这篇文章中解释的超级简短摘要 video .

图灵完成——做图灵机器能做的任何事情。

1. 它有 (即“如果声明”)。此外,还意味着“转到”,因此允许循环。

2. 任意内存量

我们称一种语言为图灵完备当且仅当(1)它可由图灵机器判定,但(2)不可由比图灵机器能力差的任何东西判定。例如,字母表{a,b}上的回文语言可以由图灵机器判断,也可以由下推自动机判断;所以,这种语言不是图灵完备的。真正的图灵完全语言——需要图灵机器的全部计算能力的语言——非常罕见。可能是字符串x.y.z的语言,其中x是一个数字,y是一个图灵机,z是一个初始磁带配置,y在z上停留的时间小于x!步骤-可能符合条件(尽管需要显示!)

一个常见的不精确用法混淆了图灵完整性和图灵等价性。图灵机等价是指一个计算系统的特性,它可以模拟图灵机,也可以被图灵机模拟。例如,我们可以说Java是一种图灵等价的编程语言,因为您可以用Java编写图灵机器模拟器,还因为您可以定义一个模拟Java程序执行的图灵机器。根据丘奇图灵理论,图灵机器可以执行任何有效的计算,因此图灵等价意味着一个系统尽可能有能力(如果丘奇图灵理论是真的!)

图灵等价是一个更为主流的问题,即真正的图灵完备性;这一点以及“完整”比“等效”短的事实可以解释为什么“图灵完整”经常被误用为图灵等效,但我离题了。

在大多数程序员熟悉的实际语言术语中,检测图灵完整性的通常方法是,如果语言允许或允许模拟嵌套的无界while语句(与Pascal风格的语句相反,具有固定的上界)。

图灵机要求任何程序 可以执行条件测试。这是根本。

考虑一个球员钢琴卷。弹钢琴的人会弹钢琴 但是在这个过程中从来没有任何条件逻辑 不 图灵完成。

条件逻辑既是力量也是力量 图灵完成的机器存在危险。

钢琴声保证每次都停止。 对于TM没有这样的保证。这 这就是所谓的停顿问题。

像 Waylon Flinn said :

图灵完成意味着它至少和图灵机器一样强大。

我认为这是错误的,一个系统是图灵完备的,如果它和图灵机器一样强大,也就是说,机器完成的每一个计算都可以由系统完成,但系统完成的每一个计算都可以由图灵机器完成。

但是C++可以做到,并且可以做任何问题。事实就是这样。