图灵完备

“图灵完备”一词来源于被称为计算机科学之父的英国数学家阿兰·图灵。1936 年，图灵创建了一个数学模型之上的计算机，这个计算机包含操作符号的状态机，可以从连续的内存（例如无限长度的磁带）中读取和写入这些数据。在这个构想之下，图灵进一步探索关于通用可计算性这个问题的数学基础，这也就意味着求证是否任何问题都可解（图灵的研究试图给出否定答案）。图灵证明了有一类问题是不可解的，特别是著名的停机问题（即给定任意程序和输入，试图证明程序最终是否会停止运行）是不可解的。