网站首页  英汉词典

请输入您要查询的英文单词:

 

单词 Turing degree
释义

Turing degree

中文百科

不可解度

不可解度,或图灵度,是数学逻辑的名词,尤其应用在可计算性理论中。

假设一个图灵机进程可以随意获取自然数函数g的值(即使g不可计算),且该图灵机计算自然数函数f,则定义函数f由函数g 图灵可计算,记作f\le_T g。符合以上特点的图灵机称为具备函数g的预言机。若集合B的特征函数可计算集合A,则A\le_T B

在计算机科学和数理逻辑中,自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念,在可计算理论里,自然数集合通常被看作一个判定问题,而图灵度则给出了解决与此集合相连的判定问题的困难程度。

如果两集合A,B有同一不可解度(也即两者互相图灵可计算),则称两集合为图灵等价,记作A\equiv_T B。图灵等价是一个等价关系,其等价类称作不可解度。图灵可计算关系是所有不可解度的搜集上的偏序。所有可计算集合(也即图灵等价于空集的集合)的不可解度为\mathbf{0}(零度)。

英语百科

Turing degree 不可解度

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set tells how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set.

随便看

 

英汉网英语在线翻译词典收录了3779314条英语词汇在线翻译词条,基本涵盖了全部常用英语词汇的中英文双语翻译及用法,是英语学习的有利工具。

 

Copyright © 2004-2024 encnc.com All Rights Reserved
更新时间:2025/6/17 23:50:15