受界搜尋化歸是數學名詞
基本介紹
- 中文名：受界搜尋化歸
- 外文名：bounded search reducibility
受界搜尋化歸亦稱b、化歸一種可化歸性.是對T化歸限制後得到的.具體地，對自然數集A,B，若A(T13，並且存在遞歸函式f，使得在判斷“xEA}”時，計算CA<A的特徵函式)的帶外部信息源B的圖靈機向B提問的次數不超過f<x)，則稱A可受界搜尋化歸到B,記為A鎮6.,B. b:化歸在定義上非常類似wtt化歸.但wtt限制的是提問範圍(只能對Gf(二)的元提問)，而b:化歸則限制提問次數.由於圖靈機具有某種存儲性，因此可限制對每個y只提問一次，由此可看出wtt化歸強於bs化歸，即A鎮waB}A鎮6s B.此外有A蕊bsB->A錢TB.但b:化歸與wtt化歸和T化歸都不存在，若且唯若關係.事實上，存在b:完備的非wtt完備集，亦存在T完備的非b:完備集.b:化歸有一個非常特殊的性質，即b:化歸沒有可傳性.
