图灵完备，php 和js是图灵完备的吗

本文目录一览

1，php 和js是图灵完备的吗
2，正则表达式为什么不是图灵完备
3，Minecraft 里面的红石电路是图灵完备的
4，sql算是一种语言么满足图灵完备性么
5，区块链是否能做到图灵完备
6，从PHP与Python的语言比较去了解什么是图灵完备

1，php 和js是图灵完备的吗

应该不是吧。

图灵机模型最坏的情况下是可能运行无限时间，无限空间。

php 和js是图灵完备的吗

2，正则表达式为什么不是图灵完备

说个容易理解的说法：图灵机模型最坏的情况下是可能运行无限时间，无限空间。DFA最坏情况也只要O(1)的空间（只要记录当前指针位于哪个状态），O(n)的时间（遍历整个要判别的字符串），即它只能处理这个复杂度范围的问题，所以肯定处理问题的范围肯定更小。

同问。。。

正则表达式为什么不是图灵完备

3，Minecraft 里面的红石电路是图灵完备的

是的，Notch （Minecraft 游戏创造者）自己已回答过这个问题。你可以看 Arqade 上面更详细的讨论。 Is Minecraft Turing-Complete?

红石电路可以做出2极管，而网上仿佛有人用红石电路造出了多位累加器。事实上图灵完备更多情况下是用于形容语言的电子计算机是图灵机模型的1种实现。甚么是图灵完备？而现代计算机不就是以2极管等基础元件组成的吗？红石电路可以摹拟出计算机的所有基本组成元件，自然可以造出简单的计算机，顶多就是体积太大罢了。而从理论上说这个用红石堆砌起来的怪物是与计算机等价的，同时也就与通用图灵机等价。你只要给他配上适合的程序，它可以解决1切可计算问题。所以「图灵完备」

Minecraft 里面的红石电路是图灵完备的

4，sql算是一种语言么满足图灵完备性么

不懂图灵完备性是指什么，但是个人觉得SQL本身不算语言。但是基于某一数据库的可以算，比如SQL Server的T-SQL可以算，Oracle也有一套自己的SQL。这些都是在SQL的基础上有扩充，加了一些语句和函数。

当然算是语言了, 名字都叫结构化查询语言. 我不知道如何证明是不是图灵完备的, 有读能写(对应图灵机里面的读写头),有存储系统(对应图灵机里面的纸带), 有逻辑判断功能(对映图灵机里面读写头在纸带上的按指令移动功能). 感觉SQL语言把brainfuck语言的指令功能都能实现. brainfuck是图灵完备的, 也许可以通过证明SQL语言对于brainfuck语言的等价来证明SQL语言的图灵完备性, 或不等价来证明非图灵完备. 就差一个数学大神了

sql 是结构化查询语言是一种数据库脚本代码标识符号

5，区块链是否能做到图灵完备

图灵完备原本是来自计算机的概念，是程序员编写的各种代码语言，再加上一种能在图灵机这种虚拟机中完美地运算的运算规则，因此满足这样要求的逻辑系统、装置或者编程语言就叫图灵完备。比特币虽然安全，但是在其系统上不能开发复杂的逻辑程序，这就使得早些年区块链的落地场景和应用十分少。而随着区块链的发展，这些需求不断提上议事日程，人们开始逐渐需要能够支持区块链应用开发运行的系统出现，于是区块链就引入了图灵完备的概念。在比特币之后，为了能实现更丰富的功能和使用场景，一些图灵完备的区块链系统应运而生。这是我一个在煊凌科技的朋友告诉我的，很不错很厉害

一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。一个能计算出每个图灵可计算函数（turing-computable function）的计算系统被称为图灵完备的。一个语言是图灵完备的，意味着该语言的计算能力与一个通用图灵机（universal turing machine）相当，这也是现代计算机语言所能拥有的最高能力。图灵完备是什么意思呢？在可计算理论中，当一组数据操作的规则（一组指令集，编程语言，或者元胞自动机）满足任意数据按照一定的顺序可以计算出结果，被称为图灵完备（turing complete）。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（“if” 和 “goto”语句）以及改变内存数据。如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的（c++ template就是图灵完备的），都能解决内存有限的问题。图灵完备的机器都被定义有无限内存，但是机器指令集却通常定义为只工作在特定的，有限数量的ram上。

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

从非常严格的理论角度来说，答案是：没有。因为PHP和Python都是图灵完备(Turing complete)的语言，所以理论上你找不到一个Python能做到而PHP做不到的事情。可图灵指在可计算性理论中，编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之，此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾伦·图灵（Alan Turing）。虽然图灵机会受到存储能力的物理限制，图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。简单来说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。图灵等价02Turing equivalence02和图灵完备02Turing completeness经常在讲编程语言的书或文章里面看到图灵等价（Turing equivalence）和图灵完备(Turing completeness)，但却不知道这两个词的精确含义和区别。尤其是很多书或文章经常对这两个词进行混用，我就很疑惑这两个词是不是就是一个意思。我用Google搜索了一下，很遗憾的是中文结果基本没用，只有一篇百度空间里面转载的一个外国人写的文章，还是全英文的，简单看了下感觉写得不怎么清楚，就查了下英文维基百科。言归正传，下面先看看维基百科的两段话：In02computability theory, a system of data-manipulation rules (such as an02instruction set, a02programming language, or a02cellular automaton) is said to beTuring complete02or02computationally universal02if and only if02it can be used to simulate any single-taped02Turing machine02and 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.02在可计算理论里，有一个很相关的概念叫图灵等价。当计算机 P 和计算机 Q 是图灵等价的，当P可以模拟Q而且Q也可以模拟P。因此，一个图灵完备的系统可以模拟图灵机，但是这个术语（即图灵等价）常常被用来指与图灵机等价。然后我们再来看看在可计算理论中，这两个词的正式定义：Turing completeness：A computational system that can compute every Turing-computable function02is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a02universal 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 do02Turing 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 the02Church–Turing thesis.)图灵等价：一个图灵完备的系统被称为图灵等价的，如果任何它可以计算的函数也是图灵可计算的。也就是它可计算的函数和图灵机可计算的函数是完全相同的。换句话说，就是图灵等价的系统就是能模拟通用图灵机同时也能也被通用图灵机模拟的系统。（所有已知的图灵完备的系统都是图灵等价的，这增加了对丘奇-图灵论题的支持）通过上面的分析，我们就可以清楚的知道这两个词的意思和关系了。图灵等价有两个意思，一个是指两个计算系统在可计算性上计算能力相同；另一个，也是常用的一个就是指一个系统的计算能力与通用图灵机计算能力相同（在可计算性的意义上）。而图灵完备是指能够模拟通用图灵机的计算系统。而所有已知的图灵完备的系统都是图灵等价的，这也增加了对丘奇-图灵论题的支持。因此，在现有的计算机系统（编程语言、指令集等）上，使用图灵等价和图灵完备是一个意思。

基于以下三个原因，我们选择python作为实现机器学习算法的编程语言：(1) python的语法清晰；(2) 易于操作纯文本文件；(3) 使用广泛，存在大量的开发文档。可执行伪代码python具有清晰的语法结构，大家也把它称作可执行伪代码（executable pseudo-code）。默认安装的python开发环境已经附带了很多高级数据类型，如列表、元组、字典、集合、队列等，无需进一步编程就可以使用这些数据类型的操作。使用这些数据类型使得实现抽象的数学概念非常简单。此外，读者还可以使用自己熟悉的编程风格，如面向对象编程、面向过程编程、或者函数式编程。不熟悉python的读者可以参阅附录a，该附录详细介绍了python语言、python使用的数据类型以及安装指南。python语言处理和操作文本文件非常简单，非常易于处理非数值型数据。python语言提供了丰富的正则表达式函数以及很多访问web页面的函数库，使得从html中提取数据变得非常简单直观。python比较流行python语言使用广泛，代码范例也很多，便于读者快速学习和掌握。此外，在开发实际应用程序时，也可以利用丰富的模块库缩短开发周期。在科学和金融领域，python语言得到了广泛应用。scipy和numpy等许多科学函数库都实现了向量和矩阵操作，这些函数库增加了代码的可读性，学过线性代数的人都可以看懂代码的实际功能。另外，科学函数库scipy和numpy使用底层语言（c和fortran）编写，提高了相关应用程序的计算性能。本书将大量使用python的numpy。