a遞歸集(a-recursive set)特徵函式為a遞歸函式的集合一集合CCa為a遞歸的，是指C與a-C均為a-r。集.換句話說，C二a為a遞歸，若且唯若C是L。上的。:集，這一點與經典遞歸論中的性質相似.
a遞歸集(a-recursive set)特徵函式為a遞歸函式的集合一集合CCa為a遞歸的,是指C與a-C均為a-r。集.換句話說,C二a為a遞歸,若且唯若C是L。上的。:集,這...
遞歸集是遞歸論用語。令A⊆Nn,如果A的特徵函式CA(x1,…,xn)是μ-遞歸函式,則稱A為遞歸集。 遞歸論又稱“遞歸函式論”、“能行性理論”,指主要用數學方法...
如果A是遞歸集合,則A的補集是遞歸集合。 如果A和B是遞歸集合,則A∩B、A∪B...遞歸可枚舉集,又稱部分遞歸集。在能行性理論中,基本概念是遞歸函式,它可刻畫...
a遞歸論(a-recursion theory)一種遞歸理論.是經典遞歸論(研究。上函式與集合的能行性問題)將論域擴展到可允許序數上以後所形成的一種理論. 將經典遞歸論推廣到...
遞歸可枚舉集,又稱部分遞歸集。在能行性理論中,基本概念是遞歸函式,它可刻畫為:任給x,只要它在x處有定義必可在有限步驟內求出其值。因此遞歸全函式(即處處有...
相對a遞歸性(relative a-recursiveness ) a遞歸性的推廣.設A,Bca. B稱為相對A是a遞歸,是指存在a-r。集We,使得對一切Y: 直觀上說,B相對A a遞歸,是指對...
超限遞歸定理 對於每一個公式γ(x,y)有下述定理:設(A,<)為良序集,且對任何f有唯一的y使γ(f,y)成立,則存在唯一以A為定義域的函式F,使得對於A中的所有t...
a遞歸可枚舉集(a-recursively enumerable set)亦稱a-re集.a遞歸函式的定義域.集合C互a稱為a遞歸可枚舉(簡稱a-re ),是指C為一個部分a遞歸函式的定義域.換句...
a遞歸函式(a-recursive function) a遞歸論中能行性概念的表述.對可允許序數a,一個函式f;a->a稱為部分a遞歸函式,是指其圖象在L。上y可定義.作為a遞歸論中...
a有窮集(a-finite set)有窮集概念在a遞歸論中的推廣.1.。中的元素稱為a有窮集.作為對普通遞歸論的推廣,a遞歸論所考慮的“計算步數”及“讀寫的信息數量...
回溯集(retraceable set)是一種回歸集。德克爾(Dekker,J.)和邁希爾(Myhill,J.)證明了:若A為遞歸集,則A為回溯集。反之,若A為回溯集,則A必為遞歸或禁集。...
產生集(productive set)是一種非re集。若集合A不是re的,則A的任何re子集We一定是A的真子集,從而有a∈A-We 。若這種a可以由e能行地求出,即若存在遞歸...
創造集(creative set)亦稱能行非遞歸集,是余集為產生集的re集。設a為re集,若ā是產生集,則稱a為創造集。例如K={x|φx(x)↓}就是一個創造集。關於創造...
1.無窮公理,即無條件承認有一非空集a,對於a的每一元x,必有a的元y,使得x...2.存在一個遞歸集S:∃S(∅∈S∧(∀X∈S)[X∪{X}∈S]).遞歸集是...
其中c1 (M)表示M的哥德爾閉包,稱Def (x)為x的可定義冪集.對任意序數a,遞歸定義集合L(a)如下,L(0)=O;L(a+1)=Def(L(a));當a為極限序數時,...
下標集((index set)由一些下標構成的遞歸函式集.設{}e } }" E。為部分遞歸函式的能行枚舉,若存在一個部分遞歸函式集了,使A= {xE叫p E=-}}}則稱A為...
極大集是余集為內聚集的c.e.集。若A為c.e.集,而A的補集是內聚集,則A稱為極大集。...... 如果自然數 A 是無窮的,且不能被任何遞歸可枚舉集分成兩個無...
稱re集A為s脫殊集,是指存在A的遞歸枚舉{As}s∈ω,使得對任何原始遞歸集C⊆2,如果C沿{As}s∈ω稠密,則存在τ∈C,使τ⊆CA(以上CA為A的特徵函式)....