概念,意義,
概念
枚舉化歸(enumeration reducibility)亦稱。化歸一種可化歸性概念.對自然數集A;B，若存在re集w二，使得dx仁二任AH(」二)[(x,動任w、八D} cB]](D。為以u為典則下標的有窮集)，則稱A可枚舉化歸到B，記為A蕊迢.直觀地說，A可枚舉化歸到B，是指存在一個能行的過程，以該過程接受B的枚舉作為輸人，以A的枚舉作為輸出.若將B的按另一個次序的枚舉作為輸入時，該過程的輸出仍為A，但輸出次序可能不同.這裡，輸出和輸入的枚舉都可能重複.從形式上看，e化歸可以看成是正化歸的推廣，只是將式中的uEDf}s)變為(u,x) EWz.從另一個角度看，A硯迢非常類似於A相對re於B，不過前者的概念比後者強(即A錢eB-}A re於B)，因為前者在得到A的枚舉時，只能用到B的正信息(即外部信息源只在yEB時對提問“yEB?”給出回答，且回答不一定立即給出)，而後者在得到A的枚舉時既可用到B的正信息，也能用到負信息(即外部信息源對任何提問yEB皆立即給出回答，而不論y是否屬於B>.
意義
對於枚舉化歸，任何re集可。化歸到任何其他合:反之，任何能化歸re集的集合也一定是re集.這一點是與其他化歸差別很大的.從某種意義上說，。化歸不是一種標準化歸，它已沒有相對可計算的意義.除了前面的定義外，‘化歸也能從函式出發用另一種方式來定義:若a,R為部分函式，且存在部分遞歸運算元F，使得F(戶-a，則稱a可e化歸到月，記為a毛渭.若將這種定義推廣到集合上，則該定義與前面的定義一致(即定義Ga鎮eGp`-' a鎮r月，其Ga ,G，為a,的圖).對部分函式上的‘化歸，鎮e與<T,二二在全函式上是一致的，即若a,R為全函式，則a鎮r月Ha鎮月.--. awr月.由e化歸的概念可導出。等價的概念:若A越迢八B毛滋，則稱A和B e等價，記為A=eB.。化歸的概念是弗里德格(Fried-berg , R. M.)和美國數學家羅傑斯(Rogers , H.)於1959年提出的.
