图灵完备是一个在计算机科学中经常出现的术语，它描述了一种能够模拟任何可计算问题的数据操作规则。这些规则可以是一门编程语言，也可以是一种指令集，甚至可以是一种细胞自动机。图灵完备的概念是由英国数学家和逻辑学家阿兰·图灵（Alan Turing）在1936年提出的，他设计了一种抽象的机器模型，称为图灵机（Turing Machine），来研究可计算性理论（Computability Theory）。
可计算性理论是一个探讨哪些问题可以被计算机解决，哪些问题不能被计算机解决，以及如何衡量计算机解决问题的效率的数学分支。在这个领域中，一个计算问题（Computational Problem）就是一个关于输入和输出之间关系的数学对象，比如给定一个正整数n，判断它是否是质数；给定一个字符串，判断它是否是回文；给定一个逻辑表达式，判断它是否为真等等。一个计算问题如果存在一个算法（Algorithm），可以在有限的时间和空间内对任意输入给出正确输出，那么就称这个问题是可计算的（Computable）。否则，就称这个问题是不可计算的（Uncomputable），或者说不可判定的（Undecidable）。例如，著名的停机问题（Halting Problem），就是一个不可判定的问题，它问的是给定一个程序和一个输入，判断这个程序在这个输入上是否会停止运行还是无限循环。图灵证明了不存在一个通用的算法，可以对任意程序和输入做出正确判断。
图灵机是一种理想化的计算模型，它由以下几个部分组成：
1.一条无限长的纸带（Tape），被分成许多格子（Square），每个格子上可以写上一个字符（Symbol）；
2.一个字符表（Alphabet），包含所有可能出现在纸带上的字符，其中有一个特殊的空白字符（Blank），表示没有写任何字符；
3.一个读写头（Head），可以在纸带上移动，并且可以读取或修改当前所指格子上的字符；
4.一个状态寄存器（State Register），记录着图灵机当前所处的状态（State），其中有一个特殊的停止状态（Halt），表示图灵机停止运行。
原创文章，作者：用户，如若转载，请注明出处：https://www.qklgw.cn/post/13608.html
