307
个编辑
更改
跳到导航
跳到搜索
第301行：
第301行： + 第306行：
第307行： − 有关进一步的解释，请参阅文章图灵度中 Post 的问题和优先级方法一节。+ 第314行：
第315行： − Post 的问题通过一个叫做优先级方法的方法得到了解决; 使用这个方法的证明称为优先级参数。此方法主要用于构造具有特定属性的递归可枚举集。要使用这种方法，需要构造的集合的期望属性被分解成一个无限的目标列表，称为需求，因此满足所有需求将使构造的集合具有期望的属性。每个需求被分配给一个自然数，代表需求的优先级; 因此0被分配给最重要的优先级，1被分配给第二重要的优先级，依此类推。然后集合被分阶段构建，每个阶段都试图通过向集合中添加数字或者禁止集合中的数字来满足更多的需求中的一个，以便最终集合满足这个需求。满足一个需求可能会导致另一个需求得不到满足; 优先级顺序用于决定在此类事件中要做什么。+ − + − − Priority arguments have been employed to solve many problems in recursion theory, and have been classified into a hierarchy based on their complexity (Soare 1987). Because complex priority arguments can be technical and difficult to follow, it has − − 优先级论证在21可计算性理论被用来解决许多问题，并且已经根据其复杂性被分类为一个层次结构(Soare 1987)。因为复杂的优先级争论可能是技术性的而且难以遵循，所以它有 − − traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. − − − − 传统上被认为是可取的结果证明没有优先论点，或看看结果证明与优先论点是否也可以证明没有他们。 − − For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method. − − − − 例如，Kummer 发表了一篇论文，证明了在不使用优先级方法的情况下 Friedberg 数值的存在性。 + +
→The priority method
===The priority method===
===The priority method===
优先级方法
:''For further explanation, see the section ''[[Turing degree#Post's problem and the priority method|Post's problem and the priority method]]'' in the article ''[[Turing degree]].
:''For further explanation, see the section ''[[Turing degree#Post's problem and the priority method|Post's problem and the priority method]]'' in the article ''[[Turing degree]].
For further explanation, see the section Post's problem and the priority method in the article Turing degree.
For further explanation, see the section Post's problem and the priority method in the article Turing degree.
有关进一步的解释，请参阅文章'''<font color="#ff8000">图灵度 Turing degree</font>'''中'''<font color="#ff8000">波斯特问题 Post's problem</font>'''和'''<font color="#ff8000">优先级方法 the priority method</font>'''一节。
Post's problem was solved with a method called the priority method; a proof using this method is called a priority argument. This method is primarily used to construct recursively enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as requirements, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.
Post's problem was solved with a method called the priority method; a proof using this method is called a priority argument. This method is primarily used to construct recursively enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known as requirements, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.
波斯特问题通过优先级方法得到了解决; 使用这个方法的证明称为优先级参数。此方法主要用于构造具有特定属性的递归可枚举集。使用这种方法，要构造的集合的期望属性被分解成一个无限的目标列表，称为需求，因此满足所有需求将使所构造的集合具有所需的属性。每个需求被分配给一个自然数，代表需求的优先级; 因此0被分配给最重要的优先级，1被分配给第二重要的优先级，依此类推。然后集合被分阶段构建，每个阶段都试图通过向集合中添加数字或者禁止集合中的数字来满足更多的需求中的一个，以便最终集合满足这个需求。满足一个需求可能会导致另一个需求得不到满足; 优先级顺序用于决定在此类事件中要做什么。
Priority arguments have been employed to solve many problems in recursion theory, and have been classified into a hierarchy based on their complexity (Soare 1987). Because complex priority arguments can be technical and difficult to follow, it has
Priority arguments have been employed to solve many problems in recursion theory, and have been classified into a hierarchy based on their complexity (Soare 1987). Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method.
traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them.
For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method.
Priority arguments have been employed to solve many problems in recursion theory, and have been classified into a hierarchy based on their complexity (Soare 1987). Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method.
优先级参数被用来解决递归理论中的许多问题，并根据其复杂性被划分为一个层次结构(Soare 1987)。因为复杂的优先权论证可能是技术性的，很难遵循，所以传统上认为最好证明没有优先级参数的结果，或者去看用优先级参数证明的结果是否也可以在没有优先级参数的情况下得到证明。例如，库默发表了一篇论文，证明了在不使用优先级方法的情况下弗里德伯格数值的存在性。
===The lattice of recursively enumerable sets===
===The lattice of recursively enumerable sets===