弱真值表可化歸性是一種一種可化歸性概念。
基本介紹
- 中文名：弱真值表可化歸性
- 外文名：weak truth-table re-ducibility
弱真值表可化歸性(weak truth-table re-ducibility)一種可化歸性概念.若一自然數集合B的特徵函式可由一帶外部信息源A的圖靈機計算，並且存在一遞歸函式f，使得對任意二，該機器在計算CB(二)(B的特徵函式)時，只使用A卜f(二)中的信息，即只對小於f(二)的，提問“n E A?"，則稱B可弱真值表化歸到A，記為B鎮},}, A，有時亦記為“B鎮},A".弱真值表化歸也稱為受界圖靈化歸，並用“B鎮bTA”表示.
對於tt化歸，若B鎮}}A，則存在遞歸函式f，得在判斷‘`x E B?”時，只用到A卜f(二)中的信息.因此，wtt化歸弱於tt化歸，這也是其名稱的由來.
wtt化歸的概念是由弗里德貝格(Friedberg,R.M.)和美國數學家羅傑斯(Rogers , H.)於1959年提出的.由wtt可化歸性導出的度稱為wtt度·wtt度的很多性質與tt度相似.肖爾(Shore , R. A.)於1982年證明了必、，(妻0`)與少a(妻0'IL)同構.
