图灵完备性
德国数学家大卫·希尔伯特在1900年的第二届国际数学家大会上作了题为《数学问题》的演讲，他提出了23个重要的数学问题1。其中第十个问题的主要表述为：是否所有的问题都是数学可判定的？也就是说是否每个命题都能有明确的算法(algorithm)，可以在有限时间内给出这个命题的真假2。 但是对于算法本身，实际上早在古希腊时期就已经形成了关于其最朴素的概念，比如古希腊人会通过辗转相除法计算两个自然数的最大公约数3,但是对于什么是可计算的、一个问题的可解性与比可解性究竟是什么意思并未形成精确的概念。
由于数学知识的匮乏，本文仅对部分可陈述的图灵完备性史话做陈述，不进行原理性科普。
对于算法和计算本身，在古希腊时期就已经形成了关于其最朴素的概念，比如古希腊人会通过辗转相除法计算两个自然数的最大公约数3。这种可计算性更多地是一种直觉上的概念，比如加法运算，当我们给定两个确定的输入时，当然会有一个确定的、准确的结果。可是对于到底什么是可以被算出来的这个问题直 到1936年才有了较为系统性的表述。