目录
原始递归函数
在可计算性理论中，原始递归函数（primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。 原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。 原始递归函数的集合在计算复杂性理论中叫做PR。.
可计算函数
在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。可行可计算性和计算复杂性研究可有效计算的函数。 依据邱奇-图灵论题，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有算法的任何函数都是可计算的。 可以使用Blum公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。.
可计算性逻辑
对于是真理的形式理论的经典逻辑，Giorgi Japaridze在2003年发明的可计算性逻辑(Computability logic)是把逻辑恢复为系统的形式的可计算性理论的一个研究程序和数学框架。在这种方法下逻辑公式表示计算问题（或等价的计算资源），而它们的有效性意味着"总是可计算的"。 计算问题和资源的理解是在它们最一般的意义上的 - 交互的意义上的。它们被形式化为机器扮演的针对它的环境的游戏，而可计算性意味着存在着一个机器针对经由环境的任何可能行为赢得了游戏。定义了这种游戏扮演机器所意味的东西，可计算性逻辑在交互层面提供了邱奇-图灵论题的一般化。 真理的经典概念转变为可计算性的特殊的零交互度的情况。这使经典逻辑成为可计算性逻辑的特殊片段。作为前者的保守扩展的同时，可计算性逻辑有着一个数量级之上的表达力、创造性和计算意义。提供了对基本问题"什么是可以（如何）计算的?"的系统的回答，它有潜在的广泛的应用领域。其中包括构造性应用理论，知识库系统，计划和行动系统。 除了经典逻辑之外，线性逻辑（在不严格的意义上理解）和直觉逻辑也转变成可计算性逻辑的自然片段了。因为"直觉真理"和"线性逻辑真理"的有意义的概念可从可计算性逻辑的语义中推导出来。 正在做着语义构造，至今可计算性逻辑仍没有完全开发出证明论。为它的各种片段找到演绎系统并探索它们的性质是正在研究中的领域。.
人工智能史
人工智能的历史源远流长。在古代的神话传说中，技艺高超的工匠可以制作人造人，并为其赋予智能或意识。现代意义上的AI始于古典哲学家用机械符号处理的观点解释人类思考过程的尝试。20世纪40年代基于抽象数学推理的可编程数字计算机的发明使一批科学家开始严肃地探讨构造一个电子大脑的可能性。 1956年，在达特茅斯学院举行的一次会议上正式确立了人工智能的研究领域。会议的参加者在接下来的数十年间是AI研究的领军人物。他们中有许多人预言，经过一代人的努力，与人类具有同等智能水平的机器将会出现。同时，上千万美元被投入到AI研究中，以期实现这一目标。 研究人员发现自己大大低估了这一工程的难度，人工智慧史上共出現過好幾次低潮。由于James Lighthill爵士的批评和国会方面的压力，美国和英国政府于1973年停止向没有明确目标的人工智能研究项目拨款。七年之后受到日本政府研究规划的刺激，美国政府和企业再次在AI领域投入数十亿研究经费，但这些投资者在80年代末重新撤回了投资。AI研究领域诸如此类的高潮和低谷不断交替出现；至今仍有人对AI的前景作出异常乐观的预测。 尽管在政府官僚和风投资本家那里经历了大起大落，AI领域仍在取得进展。某些在20世纪70年代被认为不可能解决的问题今天已经获得了圆满解决并已成功应用在商业产品上。与第一代AI研究人员的乐观估计不同，具有与人类同等智能水平的机器至今仍未出现。图灵在1950年发表的一篇催生现代智能机器研究的著名论文中称，“我们只能看到眼前的一小段距离……但是，我们可以看到仍有许多工作要做”。.
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
查看 邱奇-图灵论题和图灵机
组合子逻辑
组合子逻辑是Moses Schönfinkel和哈斯凱爾·加里介入的一种符号系统，用来消除数理逻辑中对变量的需要。它最近在计算机科学中被用做计算的理论模型和设计函数式编程语言的基础。它所基于的组合子是只使用函数应用或早先定义的组合子来定义从它们的参数得出的结果的高阶函数。.
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
阿隆佐·邱奇
阿隆佐·邱奇（Alonzo Church，）是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿大学受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。 解决算法问题包括构造一个能解决某一指定集及其他相关集的算法，如果该算法无法构建，则表明该问题是不可解的。证明此种问题不可解性的定理是算法理论中的一大突破，邱奇的算法即为该类算法的首例。邱奇证明了基本几何问题的算法不可解性。同时证明了一阶逻辑中真命题全集的解法问题是不可解的。.
邱奇数
邱奇编码是把数据和运算符嵌入到lambda演算内的一种方式，最常见的形式是邱奇数，它是使用lambda符号的自然数的表示法。这种方法得名于阿隆佐·邱奇，他首先以这种方法把数据编码到lambda演算中。 在其他符号系统中通常被认定为基本的项（比如整数、布尔值、有序对、列表和tagged unions）都被映射到使用 邱奇编码的高阶函数；根据邱奇-图灵论题我们知道任何可计算的运算符（和它的运算数）都可以用邱奇编码表示。 很多学数学的学生熟悉可计算函数集合的哥德尔编号；邱奇编码是定义在lambda抽象而不是自然数上的等价运算。.
查看 邱奇-图灵论题和邱奇数
递归可枚举集合
递归可枚举集合（Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果.
递归函数
在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。 其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 所有递归函数的集合叫做R。.
查看 邱奇-图灵论题和递归函数
Λ演算
λ演算（英語：lambda calculus，λ-calculus）是一套從數學邏輯中發展，以變數綁定和替換的規則，來研究函式如何抽象化定義、函式如何被應用以及遞迴的形式系統。它由數學家阿隆佐·邱奇在20世紀30年代首次發表。Lambda演算作為一種廣泛用途的計算模型，可以清晰地定義什麼是一個可計算函式，而任何可計算函式都能以這種形式表達和求值，它能模擬單一磁帶图灵机的計算過程；儘管如此，Lambda演算強調的是變換規則的運用，而非實現它們的具體機器。 Lambda演算可比擬是最根本的編程語言，它包括了一條變換規則（變數替換）和一條將函式抽象化定義的方式。因此普遍公認是一種更接近軟體而非硬體的方式。對函數式編程語言造成很大影響，比如Lisp、ML语言和Haskell语言。在1936年邱奇利用λ演算給出了對於判定性問題（Entscheidungsproblem）的否定：關於兩個lambda運算式是否等價的命題，無法由一個「通用的演算法」判斷，這是不可判定效能夠證明的頭一個問題，甚至還在停机问题之先。 Lambda演算包括了建構lambda項，和對lambda項執行歸約的操作。在最簡單的lambda演算中，只使用以下的規則來建構lambda項： 產生了諸如：(λx.λy.(λz.(λx.zx)(λy.zy))(x y)的表達式。如果表達式是明確而沒有歧義的，則括號可以省略。對於某些應用，其中可能包括了邏輯和數學的常量以及相關操作。 本文讨论的是邱奇的“无类型lambda演算”，此后，已经研究出来了一些有类型lambda演算。.
查看 邱奇-图灵论题和Λ演算