关于可表示的可计算性：第三部分：关于自然数上不可命名函数的探讨 弗拉基米尔·A·库柳金

《Computers》：On Signifiable Computability: Part III: A Note on Unnameable Functions on Natural Numbers Vladimir A. Kulyukin

形式语言与计算理论中，存在无法通过任何文字系统命名的自然数函数。论文构建了可计算性层级：可计算函数严格弱于部分可计算函数，后者严格弱于可命名函数，而可命名函数严格弱于所有自然数函数构成的集合F。该结论揭示了形式系统命名能力的局限性。

　　

摘要

一种基于字母表 $\backslash mi\{A\}$ 的书写系统是一个元组 $(\backslash mi\{R\},\; \backslash mi\{M\})$，其中 $\backslash mi\{R\}$ 是一组有限的文本生成规则，$\backslash mi\{M\}$ 是一个用于在字母表 $\mi{A}$ 上生成文本的规则应用机制。自然的书写系统（如使用天城文书写梵文）能够生成自然语言文本；而人工设计的书写系统（如使用 Unicode 书写 Lisp 代码）则生成形式化语言文本。 设 $\math{N} = \{0, 1, 2, \ldots\}$ 为自然数集。一个定义在自然数集上的函数 $f: \math{N}^k \to \math{N}$ 被某个字母表上的书写系统所“命名”，当且仅当该系统能够生成一个以该字母表表示函数 $f$ 的文本，并且不能生成其他任何函数的文本。我们证明了存在一些自然数上的函数原则上无法被任何字母表上的书写系统所命名。我们的研究结果揭示了自然数上函数的可计算性层次结构：$\text{可计算} \subset \text{部分可计算} \subset \text{可命名} \subset \text{F}$，其中 $\text{F}$ 表示所有定义在自然数集 $\math{N}$ 上的函数集合。