K-1-度上半格的结构  

STRUCTURES IN THE UPPER-SEMILATTICE OF K-1-DEGREES

作　　者：黄文奇[1] 陈志祥[1] 

机构地区：[1]华中工学院计算机系

出　　处：《计算机学报》1989年第4期249-256,共8页Chinese Journal of Computers

基　　金：国家自年科学基金

摘　　要：我们在[5]中提出了K-n-度的概念,证明了∑_n^p≠∑_(n+1)~p当且仅当存在无穷多个不同的K-n-度,n≥0,对A∈NP^-,A的 K-n-度 deg_K^n(A)={B∈NP^-:K^n(B)=_m^PK^n(A)),令D_n={deg_K^n(A):A∈NP^-},对a、b∈D_n,定义a≤b,若存在A∈a、B∈b使K_n(A)≤_m^pK^n(B)。本文证明了,<D_1;≤>是上半格;任一可数分配格可嵌入<D_1;≤>;任一可数偏序集可嵌入<D_1;≤>。In[5], the definition of K-n-degrees was given, and it was proved that ∑np≠ ∑(n+1)p iff there exist infinite different K-n-degrees for any n ≥0. For A∈ NP-, the K-n-degrees of A is degKn(A) = {B∈NP-: Kn(B) = mpKn(A)}. Let Dn = {degKn(A): A∈NP-}. For a, b∈Dn, define a≤b if there exist A ∈ a and B ∈bsuch that Kn(A) ≤mpKn(B). We show in this paper that <D1;≤>s a upper-sem-ilattice and every countable distributive lattice and every-countable order set can be embedded into <D1;≤>

关 键 词：K-1-度 计算理论 递归函数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]