弱真值表可化歸性

弱真值表可化歸性(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)同構.

相關詞條

熱門詞條

聯絡我們