3,094
个编辑
更改
→Rogers 同构定理（1958）
==== Rogers 同构定理（1958） ====
==== Rogers 同构定理（1958） ====
任意两个'''通用程序枚举'''（即枚举出所有可计算函数的程序编号系统，详见 [[#通用程序（解释器）|§2.2]]；下称 <math>\phi</math> 系统与 <math>\psi</math> 系统）之间，必然存在一个'''可计算同构''' <math>\rho</math>：<math>\mathbb{N} \to \mathbb{N}</math>——一部双向都可计算的"翻译词典"，把 <math>\phi</math> 系统里的每个程序号 <math>e</math> 送到 <math>\psi</math> 系统里的程序号 <math>\rho(e)</math>，并且 '''保 <math>\phi</math> 等价'''、'''保 W 等价'''。这两个"保…等价"是说：这部词典'''不改变任何行为事实'''。逐个拆开看：
任意两个'''[[通用程序枚举]]'''（即枚举出所有可计算函数的程序编号系统，详见 [[#通用程序（解释器）|§2.2]]；下称 <math>\phi</math> 系统与 <math>\psi</math> 系统）之间，必然存在一个'''可计算同构''' <math>\rho</math>：<math>\mathbb{N} \to \mathbb{N}</math>——一部双向都可计算的"翻译词典"，把 <math>\phi</math> 系统里的每个程序号 <math>e</math> 送到 <math>\psi</math> 系统里的程序号 <math>\rho(e)</math>，并且 '''保 <math>\phi</math> 等价'''、'''保 W 等价'''。这两个"保…等价"是说：这部词典'''不改变任何行为事实'''。逐个拆开看：
* '''<math>\phi</math> 等价'''：同一编号系统内，若两个程序 <math>e_1</math>、<math>e_2</math> 计算的是同一个（部分）函数（<math>\phi_{e_1} = \phi_{e_2}</math>，[[#"可计算"与"部分函数"|§2.1]]），就说它们 '''<math>\phi</math> 等价'''——编号只是程序的外衣，算出的函数才是实质。
* '''<math>\phi</math> 等价'''：同一编号系统内，若两个程序 <math>e_1</math>、<math>e_2</math> 计算的是同一个（部分）函数（<math>\phi_{e_1} \simeq \phi_{e_2}</math>，[[#"可计算"与"部分函数"|§2.1]]），就说它们 '''<math>\phi</math> 等价'''——编号只是程序的外衣，算出的函数才是实质。
* '''保 <math>\phi</math> 等价'''：要求对每个程序号 <math>e</math> 成立 <math>\phi_e = \psi_{\rho(e)}</math>：<math>e</math> 在 <math>\phi</math> 系统里算什么函数，<math>\rho(e)</math> 在 <math>\psi</math> 系统里就算同一个函数。于是"算同一函数"的程序对，翻译后依然是"算同一函数"的对。
* '''保 <math>\phi</math> 等价'''：要求对每个程序号 <math>e</math> 成立 <math>\phi_e \simeq \psi_{\rho(e)}</math>：<math>e</math> 在 <math>\phi</math> 系统里算什么函数，<math>\rho(e)</math> 在 <math>\psi</math> 系统里就算同一个函数。于是"算同一函数"的程序对，翻译后依然是"算同一函数"的对。
* '''W 等价 / 保 W 等价'''：<math>W_e</math> 是程序 <math>e</math> 的定义域——会让它停机的输入集合（[[#递归可枚举集（r.e. set）|§2.4]]）。两个程序 '''W 等价'''指 <math>W_{e_1} = W_{e_2}</math>（接受的输入一模一样）；'''保 W 等价'''指翻译也不破坏这层对应。由于词条约定 <math>W_e = \text{dom}(\phi_e)</math>，"保 <math>\phi</math>"已自动带出"保 W"；Rogers 原版把两层并列，是因为他的框架允许"函数枚举"与"r.e. 集枚举"彼此独立（[[#r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|§5.8.5]] 索引集的 <math>\mathcal{A}</math> 用的正是独立于 <math>\phi</math> 的 W 层）。
* '''W 等价 / 保 W 等价'''：<math>W_e</math> 是程序 <math>e</math> 的定义域——会让它停机的输入集合（[[#递归可枚举集（r.e. set）|§2.4]]）。两个程序 '''W 等价'''指 <math>W_{e_1} = W_{e_2}</math>（接受的输入一模一样）；'''保 W 等价'''指翻译也不破坏这层对应。由于词条约定 <math>W_e = \text{dom}(\phi_e)</math>，"保 <math>\phi</math>"已自动带出"保 W"；Rogers 原版把两层并列，是因为他的框架允许"函数枚举"与"r.e. 集枚举"彼此独立（[[#r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill|§5.8.5]] 索引集的 <math>\mathcal{A}</math> 用的正是独立于 <math>\phi</math> 的 W 层）。