标签：#可計算性理論

編號 (可計算性理論)

可計算性理論裡，編號（英語：numbering、indexing等）是將一個集合的元素（如函數、有理數、圖、或形式語言的字串）編上自然數號碼。可計算性以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。 常見例子有一階邏輯的哥德爾編號以及偏可計算函數的。 定義和例子 集合S的一個編號是由\mathbb{N}到S的，滿的偏函數。編號\nu在數字i的取值（若有定義）一般以\nu_i表示（而不是常見的函數表…