可计算性

可计算性是有效解决问题的能力。 它是数理逻辑中可计算性理论领域和计算机科学中计算理论领域的一个关键课题。 问题的可计算性与解决问题的算法的存在密切相关。

研究最广泛的可计算性模型是图灵可计算和 μ 递归函数，以及 lambda 演算，所有这些模型都具有等效的计算能力。 还研究了其他形式的可计算性：在自动机理论中研究了比图灵机弱的可计算性概念，而在超计算领域研究了比图灵机强的可计算性概念。

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

有两种关键类型的问题：

• 一个决策问题解决了一个集合 S，它可以是一组字符串、自然数或从某个更大的集合 U 中取出的其他对象。该问题的一个特定实例是决定，给定 U 的一个元素 u，是否 u 在 S 中。例如，设 U 为自然数集，S 为素数集。 对应的决策问题对应素数检验。
• 函数问题由从集合 U 到集合 V 的函数 f 组成。该问题的一个实例是计算给定 U 中的元素 u 和 V 中对应的元素 f(u)。例如，U 并且V可以是所有有限二进制字符串的集合，f可以取一个字符串并返回通过反转输入的数字得到的字符串（因此f（0101）= 1010）。

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

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

计算模型是对特定类型的计算过程的正式描述。 描述通常采用旨在执行手头任务的抽象机器的形式。 相当于图灵机的一般计算模型（参见 Church-Turing 论文）包括：

Lambda 演算一个计算由一个初始的 lambda 表达式（或者两个，如果你想把函数和它的输入分开）加上一个有限的 lambda 项序列组成，每个 lambda 项都是通过一个 beta 归约应用从前面的项中推导出来的。组合逻辑一个有很多概念的概念 与 λ {displaystyle lambda } -演算有相似之处，但也存在重要差异（例如，定点组合子 Y 在组合逻辑中具有范式，但在 λ {displaystyle lambda } -演算中则没有）。 组合逻辑的发展具有雄心壮志：理解悖论的本质，使数学基础更经济（概念上），消除变量的概念（从而阐明它们在数学中的作用）。μ递归函数计算由μ递归函数组成 ，即它的定义序列，任何输入值和出现在具有输入和输出的定义序列中的递归函数序列。 因此，如果在递归函数 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(5,6) = 3 之类的项必须出现在上方。 只有当最后一项给出应用于输入的递归函数的值时，计算才会终止。

字符串重写系统包括马尔可夫算法，该算法使用类似语法的规则对符号字符串进行操作； 也是后规范系统。注册机计算机的理论理想化。 有几种变体。 在大多数情况下，每个寄存器都可以容纳一个自然数（大小不受限制），并且指令简单（数量很少），例如 只有递减（结合条件跳转）和递增存在（和停止）。 缺乏无限（或动态增长）的外部存储（在图灵机上看到）可以通过用哥德尔编号技术替换它的角色来理解：每个寄存器保存一个自然数的事实允许表示复杂事物的可能性（例如 序列，或矩阵等）通过适当的巨大自然数 - 表示和解释的明确性可以通过这些技术的数论基础来建立。图灵机也类似于有限状态机，除了输入是在执行时提供的 磁带，图灵机可以读取、写入或在其读/写头上来回移动。 允许磁带增长到任意大小。