图灵机概念
图灵机（Turing Machine）是图灵在1936年发表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。既然是数学模型，它就并非一个实体概念，而是架空的一个想法。在文章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。
图灵机的结构包括以下几个部分：
- 一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。（无限存储能力，storage）
- 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。（逻辑循环能力）
- 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。（读写能力）
- 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机里的状态。（状态控制）
在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：
- 当前所处位置
- 当前格子内容
来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符的序列（比如类似“...011001...”）便作为输出，由人来解码为自然语言。
图灵证明了，只要一个系统满足以下三个条件,就具有图灵完备性,可以计算任何可计算的函数:
- 逻辑循环能力
- 无限存储能力
- 读写能力
解决哪些问题
在文章中，图灵所做的事是证明了，假设上述模型里所说的功能都能被以某种形式物理实现，那么任意可计算问题都可以被解决。这里所说的可计算问题，涉及到计算理论（Computation Theory）的概念。这个领域的概念很繁杂，先简单梳理一下。
在计算机领域，或者说自动机领域，我们研究的一切问题都是计算问题（Computational Problem）。它泛指一切与计算相关的问题。
图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。
如今主流的编程语言（C++，Java，Python等等）都是图灵完备的语言。关于语言优劣之争也只是在其封装、优化等方面，以及因为这些区别而产生的“不同语言适用于不同情况”的争执。如果我们回到最底层，就会发现它们可以实现的功能其实完全一样，并且本质上就是一个图灵机。
一个图灵完备的计算系统必须满足以下条件：
- 通用的命令式计算：系统必须支持基本的算术运算（加法、减法、乘法、除法等）和逻辑操作（与、或、非等）。
命令式计算是一种计算模型，它通过一系列明确的计算步骤（指令或命令）来描述计算过程。在命令式计算中，计算机执行指令的顺序非常重要，每条指令都会明确告诉计算机应该做什么，以及如何完成计算任务。
在命令式计算中，通常有一个程序计数器（Program Counter），它指向当前执行的指令位置。计算机从程序计数器指向的指令开始执行，然后逐步执行程序中的每一条指令，直到程序结束或者遇到特定的终止条件。
命令式计算模型通常采用顺序结构、条件分支和循环结构来组织程序。主要的编程语言，如C、C++、Java和Python，都是命令式编程语言。这些语言中，程序员需要明确地编写每一条指令，控制计算机的执行流程，从而实现所需的计算任务。
与之相对的是声明式计算，它更侧重于描述问题的本质和条件，而不是明确指定计算步骤。函数式编程和逻辑编程就属于声明式编程范畴。在声明式编程中，程序员描述了问题的规则和约束，而不必关心具体的计算步骤。然后，计算机会自行推断如何根据这些规则得出答案。
总的来说，命令式计算强调具体的计算步骤和控制流程，而声明式计算强调问题的描述和规则。两种计算模型在不同的情况下都有其优势和应用场景。
- 条件控制：系统必须能够根据条件执行不同的操作，例如if-else语句或类似的条件控制结构。
- 循环控制：系统必须支持循环结构，使得程序可以重复执行一段代码，例如for循环、while循环等。
- 存储能力：系统必须具有存储和读取数据的能力，可以使用变量或存储器来保存和检索信息。