307
个编辑
更改
跳到导航
跳到搜索
第137行：
第137行： − 图灵归约 图灵度 第144行：
第143行： − 传统上，数理逻辑的可计算性理论专注于相对可计算性，这是图灵可计算性的一种泛化，使用 oracle Turing machines 定义，由 Turing (1939)介绍。甲骨文图灵机是一种假想的设备，它除了能够执行普通图灵机的操作之外，还能够向甲骨文提问，甲骨文是一组特定的自然数。甲骨文机器只能提出“ n 在甲骨文集合中吗? ”这样的问题。每个问题将立即得到正确答案，即使预言集是不可计算的。因此，一台具有不可计算预言机的预言机将能够计算集，而没有预言机的图灵机则不能。+ 第213行：
第212行： − −
→Relative computability and the Turing degrees
{{Main|Turing reduction|Turing degree}}
{{Main|Turing reduction|Turing degree}}
Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an oracle, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot.
Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an oracle, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that a Turing machine without an oracle cannot.
图灵(1939)介绍，传统上，使用'''<font color="#ff8000">预言图灵机 oracle Turing machine</font>'''定义，数理逻辑的可计算性理论专注于相对可计算性，这是图灵可计算性的一种泛化。预言图灵机是一种假想的设备，它除了能够执行普通图灵机的操作之外，还能够向''预言''提问，''预言''是一组特定的自然数。预言机只能提出“ n 在预言集合中吗? ”这样的问题。即使预言集是不可计算的，每个问题也都将立即得到正确答案。因此，一台具有不可计算预言的预言机将能够计算集合，而没有预言的图灵机则不能。
最近很多关于图灵度的研究都集中在图灵度集的总体结构和包含递归可枚举集的图灵度集上。Shore 和 Slaman (1999)的一个深刻定理指出，映射 x 度到其 Turing 跳度的函数可以按照 Turing 度的偏序定义。Ambos-Spies 和 Fejer (2006)最近的一项调查给出了这项研究及其历史进展的概述。
最近很多关于图灵度的研究都集中在图灵度集的总体结构和包含递归可枚举集的图灵度集上。Shore 和 Slaman (1999)的一个深刻定理指出，映射 x 度到其 Turing 跳度的函数可以按照 Turing 度的偏序定义。Ambos-Spies 和 Fejer (2006)最近的一项调查给出了这项研究及其历史进展的概述。
===Other reducibilities===
===Other reducibilities===