从PHP与Python的语言比较去了解什么是图灵完备

一切可计算的问题都能计算
服务器君一共花费了240.370 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

先从一个问题开始。从语言的区别看,有什么功能python能实现,php不能实现的呢?

从非常严格的理论角度来说,答案是:没有。因为PHP和Python都是图灵完备(Turing complete)的语言,所以理论上你找不到一个Python能做到而PHP做不到的事情。

那么,什么是图灵完备呢?

图灵完备

来自维基的解释:

可图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾倫·图灵(Alan Turing)。

虽然图灵机会受到存储能力的物理限制,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。

简单来说,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。

图灵等价 Turing equivalence 和图灵完备 Turing completeness

经常在讲编程语言的书或文章里面看到图灵等价(Turing equivalence)和图灵完备(Turing completeness),但却不知道这两个词的精确含义和区别。尤其是很多书或文章经常对这两个词进行混用,我就很疑惑这两个词是不是就是一个意思。我用Google搜索了一下,很遗憾的是中文结果基本没用,只有一篇百度空间里面转载的一个外国人写的文章,还是全英文的,简单看了下感觉写得不怎么清楚,就查了下英文维基百科。言归正传,下面先看看维基百科的两段话:

In computability theory, a system of data-manipulation rules (such as an instruction set, a programming language, or a cellular automaton) is said to beTuring complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle anycomputer.

在可计算理论里,一个数据操作规则的系统(比如:指令集、编程语言、细胞自动机)被称作图灵完备或者通用计算的,当且仅当它可以被用来模拟单带图灵机。

In computability theory, there is a closely related concept known as Turing equivalence. Two computers P and Q are called Turing equivalent if P can simulate Q and Q can simulate P. Thus, a Turing-complete system is one that can simulate a Turing machine, but the term is most often used to mean Turing equivalent to a Turing machine. 

在可计算理论里,有一个很相关的概念叫图灵等价。当计算机 P 和计算机 Q 是图灵等价的,当P可以模拟Q而且Q也可以模拟P。因此,一个图灵完备的系统可以模拟图灵机,但是这个术语(即图灵等价)常常被用来指与图灵机等价。

然后我们再来看看在可计算理论中,这两个词的正式定义:

Turing completeness:A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

翻译过来就是:图灵完备:一个可以计算所有图灵机可计算的计算系统被称为图灵完备的。换句话说就是一个可以模拟通用图灵机的系统。

Turing equivalence:A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesis.)

图灵等价:一个图灵完备的系统被称为图灵等价的,如果任何它可以计算的函数也是图灵可计算的。也就是它可计算的函数和图灵机可计算的函数是完全相同的。换句话说,就是图灵等价的系统就是能模拟通用图灵机同时也能也被通用图灵机模拟的系统。(所有已知的图灵完备的系统都是图灵等价的,这增加了对丘奇-图灵论题的支持)

通过上面的分析,我们就可以清楚的知道这两个词的意思和关系了。图灵等价有两个意思,一个是指两个计算系统在可计算性上计算能力相同;另一个,也是常用的一个就是指一个系统的计算能力与通用图灵机计算能力相同(在可计算性的意义上)。而图灵完备是指能够模拟通用图灵机的计算系统。而所有已知的图灵完备的系统都是图灵等价的,这也增加了对丘奇-图灵论题的支持。因此,在现有的计算机系统(编程语言、指令集等)上,使用图灵等价和图灵完备是一个意思。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1856,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1856

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程珠玑(第2版)》 Jon Bentley (作者), 黄倩 (译者), 钱丽艳 (译者)

《编程珠玑(第2版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。

更多计算机宝库...