更改

'''[[可计算的]]（computable / effective / recursive）'''：一个函数是"可计算的"，意思是存在一套'''固定的、有穷的指令'''（程序），使得对任何输入，只要机械地按指令执行有穷多步，就能得到输出。"可计算的"（computable）、"有效的"（effective）、"递归的"（recursive）在本文中是同义词——这是历史造成的术语冗余，三个词来自 Church、Turing、Gödel–Kleene 三条等价的技术路线<ref name="kleene1938" />。

'''[[可计算的]]（computable / effective / recursive）'''：一个函数是"可计算的"，意思是存在一套'''固定的、有穷的指令'''（程序），使得对任何输入，只要机械地按指令执行有穷多步，就能得到输出。"可计算的"（computable）、"有效的"（effective）、"递归的"（recursive）在本文中是同义词——这是历史造成的术语冗余，三个词来自 Church、Turing、Gödel–Kleene 三条等价的技术路线<ref name="kleene1938" />。

'''[[部分函数]]（partial function）'''：一台机器在某些输入上可能'''永远不停机'''（死循环），这时它在这些输入上'''没有输出'''。我们把"在部分输入上有定义、在其余输入上无定义"的函数称为部分函数；在所有输入上都有定义的称为'''[[全函数]]（total function）'''。程序天然对应部分函数，而不是数学课本里那种"处处有值"的函数——这是可计算性理论与普通数学的第一个思维差异。

'''[[部分函数]]（partial function）'''：一台机器在某些输入上可能'''永远不停机'''（死循环），这时它在这些输入上'''没有输出'''。我们把"在部分输入上有定义、在其余输入上无定义"的函数称为[[部分函数]]；在所有输入上都有定义的称为'''[[全函数]]（total function）'''。程序天然对应部分函数，而不是数学课本里那种"处处有值"的函数——这是[[可计算性理论]]与普通数学的第一个思维差异。

'''记号 <math>\phi_e</math>'''：把全体程序（的所有可计算部分函数）排成一个序列，用自然数 0, 1, 2, <math>\ldots</math> 编号，'''<math>\phi_e</math> 表示"编号为 e 的程序所计算的那个部分函数"'''。这个编号也叫'''[[哥德尔配数]]（Gödel number）'''：关键思想是"程序本身也是一个有限符号串，可以编码成一个自然数"，于是'''程序即数据'''——程序可以作为另一个程序的输入被处理。<math>\phi_e(x)</math> 表示"编号 <math>e</math> 的程序在输入 <math>x</math> 上的输出"（可能无定义）。本文中 <math>p \downarrow</math> 表示"程序 <math>p</math> 停机（有输出）"，<math>p \uparrow</math> 表示"不停机（无输出）"。

'''记号 <math>\phi_e</math>'''：把全体程序（的所有可计算部分函数）排成一个序列，用自然数 0, 1, 2, <math>\ldots</math> 编号，'''<math>\phi_e</math> 表示"编号为 e 的程序所计算的那个部分函数"'''。这个编号也叫'''[[哥德尔配数]]（Gödel number）'''：关键思想是"程序本身也是一个有限符号串，可以编码成一个自然数"，于是'''程序即数据'''——程序可以作为另一个程序的输入被处理。<math>\phi_e(x)</math> 表示"编号 <math>e</math> 的程序在输入 <math>x</math> 上的输出"（可能无定义）。本文中 <math>p \downarrow</math> 表示"程序 <math>p</math> 停机（有输出）"，<math>p \uparrow</math> 表示"不停机（无输出）"。