307
个编辑
更改
跳到导航
跳到搜索
第270行：
第270行： + 第275行：
第276行： − Rice 证明了对于每一个非平凡的类 c (它包含一些但不是全部的 r.e。集)的索引集 e = { e: the eth r.e。集 w < sub > e </sub > 在 c }中具有停机问题或其补是多一可约 e 的性质，也就是说，可以使用多一可约 e 映射(详见赖斯定理)。但是，这些索引集中的许多甚至比停机问题更加复杂。这些类型的集合可以使用算数阶层分类法进行分类。例如，所有有限集类的指数集 FIN 在 σ < sub > 2 </sub > 水平上，所有递归集类的指数集 REC 在 σ < sub > 3 </sub > 水平上，所有余有限集的指数集 COFIN 也在 σ < sub > 3 </sub > 水平上，所有图灵完备集类的指数集 COMP < sub > 4 </sub > 水平上。这些层次级别是归纳定义的，σ < sub > n + 1 </sub > 只包含相对于 σ < sub > n </sub > 的递归可枚举集; σ < sub > 1 </sub > 包含递归可枚举集。这里给出的索引集对于它们的级别甚至是完整的，也就是说，这些级别中的所有集合可以是多个的——一个减少到给定的索引集。+ − −
→Rice's theorem and the arithmetical hierarchy
===Rice's theorem and the arithmetical hierarchy===
===Rice's theorem and the arithmetical hierarchy===
赖斯定理和算数层次
Rice showed that for every nontrivial class ''C'' (which contains some but not all r.e. sets) the index set ''E'' = {''e'': the ''e''th r.e. set ''W<sub>e</sub>'' is in ''C''} has the property that either the [[halting problem]] or its complement is many-one reducible to ''E'', that is, can be mapped using a [[many-one reduction]] to ''E'' (see [[Rice's theorem]] for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the [[arithmetical hierarchy]]. For example, the index set FIN of class of all finite sets is on the level Σ<sub>2</sub>, the index set REC of the class of all recursive sets is on the level Σ<sub>3</sub>, the index set COFIN of all cofinite sets is also on the level Σ<sub>3</sub> and the index set COMP of the class of all Turing-complete sets Σ<sub>4</sub>. These hierarchy levels are defined inductively, Σ<sub>''n''+1</sub> contains just all sets which are recursively enumerable relative to Σ<sub>''n''</sub>; Σ<sub>1</sub> contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
Rice showed that for every nontrivial class ''C'' (which contains some but not all r.e. sets) the index set ''E'' = {''e'': the ''e''th r.e. set ''W<sub>e</sub>'' is in ''C''} has the property that either the [[halting problem]] or its complement is many-one reducible to ''E'', that is, can be mapped using a [[many-one reduction]] to ''E'' (see [[Rice's theorem]] for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the [[arithmetical hierarchy]]. For example, the index set FIN of class of all finite sets is on the level Σ<sub>2</sub>, the index set REC of the class of all recursive sets is on the level Σ<sub>3</sub>, the index set COFIN of all cofinite sets is also on the level Σ<sub>3</sub> and the index set COMP of the class of all Turing-complete sets Σ<sub>4</sub>. These hierarchy levels are defined inductively, Σ<sub>''n''+1</sub> contains just all sets which are recursively enumerable relative to Σ<sub>''n''</sub>; Σ<sub>1</sub> contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
Rice showed that for every nontrivial class C (which contains some but not all r.e. sets) the index set E = {e: the eth r.e. set W<sub>e</sub> is in C} has the property that either the halting problem or its complement is many-one reducible to E, that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the arithmetical hierarchy. For example, the index set FIN of class of all finite sets is on the level Σ<sub>2</sub>, the index set REC of the class of all recursive sets is on the level Σ<sub>3</sub>, the index set COFIN of all cofinite sets is also on the level Σ<sub>3</sub> and the index set COMP of the class of all Turing-complete sets Σ<sub>4</sub>. These hierarchy levels are defined inductively, Σ<sub>n+1</sub> contains just all sets which are recursively enumerable relative to Σ<sub>n</sub>; Σ<sub>1</sub> contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
Rice showed that for every nontrivial class C (which contains some but not all r.e. sets) the index set E = {e: the eth r.e. set W<sub>e</sub> is in C} has the property that either the halting problem or its complement is many-one reducible to E, that is, can be mapped using a many-one reduction to E (see Rice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using the arithmetical hierarchy. For example, the index set FIN of class of all finite sets is on the level Σ<sub>2</sub>, the index set REC of the class of all recursive sets is on the level Σ<sub>3</sub>, the index set COFIN of all cofinite sets is also on the level Σ<sub>3</sub> and the index set COMP of the class of all Turing-complete sets Σ<sub>4</sub>. These hierarchy levels are defined inductively, Σ<sub>n+1</sub> contains just all sets which are recursively enumerable relative to Σ<sub>n</sub>; Σ<sub>1</sub> contains the recursively enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
赖斯证明了对于每一个非平凡的类 c (包含一些但不是全部的 r.e.集)的索引集 e = {''e'': 第 ''e''个r.e. 集 ''W<sub>e</sub>'' 在 ''C''中} 具有停机问题或其补问题是多一可约到 e 的性质，也就是说，可以使用多一可约映射到 e (详见赖斯定理)。但是，这些索引集中的许多甚至比停机问题更加复杂。这些类型的集合可以使用算数层次分类法进行分类。例如，所有有限集类的指数集 FIN 在Σ<sub>2</sub>水平上，所有递归集类的指数集 REC 在Σ<sub>3</sub>水平上，所有余有限集的指数集 COFIN 也在Σ<sub>3</sub> 水平上，所有图灵完备集类的指数集 COMP Σ<sub>4</sub>水平上。这些层次级别是归纳定义的，Σ<sub>n+1</sub>只包含相对于 Σ<sub>n</sub>的递归可枚举集;Σ<sub>1</sub>包含递归可枚举集。这里给出的索引集对于它们的级别是完整的，也就是说，这些级别中的所有集合可以是多一可约到给定的索引集。
===Reverse mathematics===
===Reverse mathematics===