可计算

可计算的一个中心思想是（计算性的）问题，这个问题的任务就是去探索可计算性。

主要问题有两类：

决策问题：用来修复一个S集合，它可以是一组字符串、自然数或取自某个较大集合U的其它对象。这个问题的一个特定实例就是决定U集合中的一个给定元素u，不管这个u是否在S之内。例如：我们可以假设U是自然数的集合，S是素数的集合相应的决策问题就是去做对应的素性测试。

函数问题：由一个从集合U到集合V的函数组成，这个问题的一个实例就是在U集合中计算出一个给定的元素u，对应的V集合中的元素f（u）。例如：U和V可能是所有有限的二进制字符串的集合，f可以取一个字符串并通过反转输入的数字而回到另一个字符串（f（010）=1010）。

其他类型的问题包括搜索问题和优化问题。

可计算性理论的一个研究目标是确定在每个计算模型中可以解决哪些问题或哪些类型的问题。

计算模型是对特定类型的计算过程的一种形式化描述，这种描述通常釆用抽象机器的形式，用于执行手头的任务。与图灵机等效的一般计算模型包括如下：

λ演算

计算由一个抽始的λ表达式（或者两个，如果你想把函数和它的输入分开的话）加上一个lambda项的有限序列组成，每个λ项都是由上一项通过一个β还原的应用推导出来的。

组合子逻辑

这个概念与λ-演算有许多相似之处, 但也存在重要的差别(例如: 定点组合子 Y在组合子逻辑中有范式, 但在λ-演算中没有范式)。组合子逻辑的发展雄心勃勃：了解悖论的本质、使数学运算的基础更加经济（概念上）、消除变量的概念（用以阐明它们在数学运算中的作用）。

μ递归函数

计算由一个μ-递归函数组成，即它所定义的序列，任何输入值（s）和出现在带有输入和输出的定义序列的递归函数序列。因此，如果在递归函数 f(x) 的定义序列中出现函数 g(x)和 h(x,y)，则可能出现 g(5) = 7或 h(3,2) = 10的形式项。这个序列中的每个条目都需要一个基本函数的应用程序，或者通过合成原始递归函数或μ-递归函数来遵从上面的条目，例如：如果 f(x) = h(x,g(x))，那么要使 f(5) = 3出现，上面必须出现 g(5) = 6和 h(3,6) = 3这样的项，只有当最后一项给出应用于输入的递归函数的值时，计算才会终止。

字符串重写系统

包括马尔科夫算法，它们使用类语法的规则对字符串进行操作，也叫做后规范系统。

寄存器几期

一个机算机理论上有趣的理想化，它有几种变体。在大多数寄存器中，每个寄存器可以保存一个自然数（大小不限），并且指令很简单（数量很少），例如只有递减（结合条件转移）和递增两种动作（停止）。缺乏无限的（或动态增长的）外部储存（在图灵机中可以见到）可以被理解为是哥德尔编号技术取代了它的作用，事实上，每个寄存器都保存一个自然数就代表了一种复杂情况的可能性（例如一个序列或一个矩阵等），通过一个适当的、超大的自然数，这种表示和解释的准确性借助于这种技术的数字理论基础能够得以确立。.

图灵机

它也类似于有限状态机，除了输入是在执行“磁带”上提供的，图灵机还可以从磁带上读取、写入或来回移动它的读/写“头”, 磁带可以任意增大尺寸。图灵机可以执行复杂的计算, 其计算过程可以持续任意的时间。这个模型也许是计算机科学中最重要的计算模型, 因为它能在没有预先定义资源限制的情况下进行模拟计算.

多磁带图灵机

这里，可能有不止一盘磁带；此外，每盘磁带可能有多个磁头。 令人惊讶的是，任何可以由这种机器执行的计算也可以由普通图灵机执行，尽管后者可能较慢或者需要更大的磁带总面积。: 这里可能有不止一盘磁带, 此外, 每个磁带可能带有多个磁头。令人惊讶的是任何可以由这种机器执行的计算也可以由普通的图灵机来执行, 只是后者可能更慢或者需要更大的磁带总面积。

p′′

与图灵机一样, P” 使用无限长的符号磁带(没有随机存取), 以及一组相当简单的指令, 但这些指令是非常不同的, 因此, 与图灵机不同, P” 不需要保持一个不同的状态, 因为所有“类似内存”的功能只能由磁带提供, 它不需要重写当前的符号就可以对其执行模运算增量。P” 也有一对循环指令用于检查空白符号。尽管它具有极简主义的本质, 但它己经成为了一种可执行的、且被称为极小化计算机编程语言(用于娱乐) 的亲代形式语言。

除了一般的计算模型外, 一些更简单的计算模型对于一些特殊的受限制的应用程序也是有用的。例如,正则表达式就是在许多文本中, 从办公效率软件到编程语言指定的字符串模式。另一种与正则表达式在数学上等价的一种形式是有限自动机, 电路设计和某些类型的问题求解。上下文无关语法指定了编程语言语法, 非确定性下推自动机是与上下文无关语法等价的另一种形式。

不同的计算模型各自完成不同的任务, 衡量计算模型能力的一种方法就是研究模型可以生成的形式化语言的层级, 这就是所得语言的乔姆斯基层次结构。

其他受限制的计算模型包括:

确定性有限自动机 (DFA)

也称为有限状态机，目前存在的所有真实计算设备都可以建模为有限状态机，因为所有真实的计算机都是在有限资源上运行的。这种机器有一种状态和一组受输入流影响的状态转换，某些状态被定义为接受状态。输入流一次一个字符的输入到机器中，并将当前状态的状态转换与输入流进行比较。如果有匹配的转换，机器可能进入一个新的状态，如果在输入流的末尾机器处于接受状态，则整个输入流都被接受。

非确定性有限自动机 (NFA)

另一个简单的计算模型虽然它的处理顺序不是唯一确定的，但他可以被解读为通过有限数量的状态同时釆用多条计算路径。然而，还是有可能证明任何的NFA都可以简化为等价的DFA。

下推自动机

类似于有限状态机，只是它有一个可以执行的堆栈，允许其增长到任意大小尺寸。这种状态转换还能指定到底是向堆栈中添加符号还是从堆栈中删除符号。由于其无限内存堆栈，它比DFA更强大。尽管在任何时候都只能访问堆栈的顶部元素。

有了这些计算模型，我们可以确定它们的极限。 也就是说，也就是说它们可以接受哪些类别的语言。

3.1 有限状态机的能力

计算机科学家将有限状态机能够接受的语言称为正则语言，由于有限状态机中可能能的状态数量是有限的这一限制，要找到一种非正则语言，我们必须构造需要无限状态数量的语言。

由字母‘a'和'b'组成的所有字符串的集合就是这种语言的一个例子，其中包含相等数量的字母‘a’ 和‘b'。要了解有限状态机为什么不能识别这种语言，首先要假设存在这样一台机器M，M必须有一些状态n。现在考虑由  ‘a’后面跟着。。  ‘b’组成的字符串x.

当M读入x时，机器中一定有某个状态在它读入‘a’ 的第一个系列时重复出现，因为有  ‘a’, 并且根据鸽巢原理, 只有几个状态. 将此状态称为S，进一步令d为我们的机器读取的‘a’ 的数量，以便得到从S的第一次出现到‘a’ 序列中随后出现的一些‘a’。那么我们知道，在第二次出现S时，我们可以添加一个额外的d  ‘a’，并且我们将再次得到S状态，这意味着我们知道一个  ‘a’ 的字符串必须与   ‘a’ 字符串以相同的状态结束。这也表示如果我们的机器接受X，那么它还必须接受   ‘a’ 后面跟着的  ‘b’ 的字符串, 这并不是包含相同数量的‘a’ 和‘b’ 的字符串语言。换句话说，M不能正确的区分具有相同数量的‘a’ 和‘b’ 的字符串以及具有  ‘a’ 和  ‘b’ 的字符串。

因此，我们知道这种语言不能被任何有限状态机正确的接受，因而并不是一种正则语言，这个结果更大众化的表示形式就称为正则语言的泵引理，它可以用来表示有限状态机无法识别的众多的语言类型。

3.2 下推自动机的能力

计算机科学家定义了一种语言，它可以被下推自动机接受为上下文无关语言，也可以指定为上下文无关语法。这是一种由具有相同数量的“a” 和“b” 的字符串组成的语言，我们展示过的这种语言不是一种正则语言，可以由下推自动机决定。同样，一般来说，下推自动机可以象有限状态机一样工作，因此，它可以决定任何正则语言。因此，严格来说，这种计算模型比有限状态机更强大。

然而，也有一些语言不能由下推自动机决定，结果类似于正则表达式，这里不再赘述，存在一个上下文无关语言的泵引理。素数集合就是这种语言的一个例子。

3.3 图灵机的力量

图灵机除了不能由下推自动机决定的语言之外，可以决定任何上下文无关语言，例如由质数组成的语言。因此，严格意义上来说，它是一种更加强大的计算模型。

因为图灵机有能力“备份”它们的输入磁带，因而图灵机有可能以某种方式长时间运行，而这是前面所述的其它计算模型无法做到的。人们有可能构建一种图灵机，它永远不会在某输入上结束运行（停止）。我们说过图灵机可以决定一种语言，如果它最终停止所有输入并给出一个答案，这样决定的语言就称为递归语言。我们可以进一步描述图灵机，它最终会停止运行并对语言中的任何输入都给出一个答案，但对于非所用语言的字符串输入，它可能会永远运行，这种图灵机可以告诉我们一个给定的字符串是在语言中的，但是基于它们的行为，我们可能永远不能确定一个给定的字符串不在语言中，因为在这种情况下它可能会永远运行。被这种图灵机所接受的语言就称为递归可枚举语言。

事实证明，图灵机是一种功能非常强大的自动机模型。人们试图通过修改图灵机的定义来制造更强大的机器，却意外地遭遇了失败，例如，给图灵机添加一个额外的磁带，给它一个二维（或三维或任意维）的无限表面来处理，而所有这些都能由图灵机用最基本的一维磁带来模拟执行，因此这些模型并没有更强大。事实上，丘奇——图灵理论的一个结果是，没有一个合理的计算模型可以决定图灵机无法决定的语言。

那么接下来要问的问题是，是否存在递归可枚举但又不是递归的语言？此外，有没有甚至不能递归可枚举的语言？

停顿的问题

停止问题是计算机科学中最著名的问题之一，因为它对可计算性理论以及我们在日常生活中如何使用计算机有着深远的影响。这个问题可以这表达：

给定一个图灵机及其初始输入的描述，确定程序在该输入上执行时是否曾停止（完成），另一种选择是它永远不停的运行。

这里我们问的不是一个简单的质数或回文的问题，而反而问的是一个图灵机来回答另一个图灵机的问题。可以看出，不可能构建一个在所有情况下都能回答这个问题的图灵机，也就是说，确定给定程序在所有情况下是否会在特定输入上停止的唯一通用的方法就是运行它，看看它是是否会停止。如果它确实停止了，那么就知道它停止了；可是，如果它不停止，你就可能永远不知道它最终是否会停止。由所有图灵机描述和致使图灵机终将停止的所有可能的输入流组成的语言并不是递归语言，因此，停止问题被称为不可计算或不可判定的。

停止问题的扩展称为莱斯定理，它指出，（一般来讲），一种给定语言是否具有任何特定的非平凡属性是不判定的。

超越递归可枚举语言

当给定的输入是一个图灵机本身不停止的表示，如果我们允许图灵机永久运行，停止问题很容易解决。因此，停止语言是递归可枚举的，可是，也可以构造一些甚至不能递归枚举语言。

这种语言一个简单的例子就是停止语言的补充码，这是由所有图灵机和输入字符串配对而成的语言，图灵机在它们的输入上不会停止。为了证明这种语言不是递归可枚举的，我们假设构建一个图灵机M，它能够对所有这样的图灵机给出一个确定的答案，但是它可能永远运行在终将停止的图灵机上。然后，我们再构造另外一个图灵机  来模拟这台机器的运行, 同时通过交叉执行这两个程序来直接模拟在输入中给定的机器的执行, 由于直接模拟将在它正在模拟的程序停止时也最终停止, 并且由于假设如果输入程序永远不会停止, 而M的模拟终将停止. 我们知道  将最终有一个并行版本停止, 因此,  是停止问题的决定者。然而，我们先前已经表明，停止问题是不可决定的，这就产生了矛盾，因而我们前面的假设M的存在是不正确的，而所谓的停止语言的补充码也就不是可递归枚举的了。

人们已经开发出了许多基于并发的计算模型，包括并行随机存取机和皮特里网，但这些并发计算模型仍然不能实现图灵机无法实现的任何数学功能。

丘奇——图灵理论推测，没有一种有效的计算模型能够比图灵机计算更多的数学函数。计算机科学家已经想像出了许多不同种类的超级计算机，希望未来他们们计算模型能够超越图灵机的可计算性。

5.1 无限执行

想像一下，如果一台机器的每一步计算都需要前一步的一半时间（也希望是前一步的一半能量…），如果我们将第一步需要的时间标准化为1/2的时间单位（将第一步所需要的能量标准化为1/2能量单位…），那么执行将需要

时间单位(和一个能量单位…) 去运行, 这个无穷级数收敛到1, 这意味着这个Z e n o机可以在一个时间单位内(使用一个能量单位…) 执行可数的无穷多个步骤. 该机器能够通过直接模拟所述机器的执行情况来决定停止问题. 由此引申而言, 任何收敛的无穷大(必须是可证明的无穷大) 系列都可以工作。假设无穷大系列收敛到一个值n，则Z e n o机器将在n时间单位内完成一个可数无限的执行。

5.2 甲骨文机器

所谓的甲骨文机器可以访问各种“神谕”，这些“神谕”为特定的无法确定的问题提供了解决方案。例如：图灵机可有一个“停止神谕”，它会立即回答给定的图灵机是否会在给定的输入上停止。这些机器是递归理论研究的中心课题。

5.3 超级计算的极限

甚至这些似乎代表了我们想像的自动机极限的机器，也遇到了它们自身的限制。虽然它们每个都可以解决图灵机的停止问题，但它们解决不了它们自身的停止问题。例如，甲骨文机器就不能回答一个给定的甲骨文机器是否会停止的问题。