圖靈機可化歸性

圖靈機可化歸性(Turing reducibility)一種可化歸性概念.它是由英國數學家圖靈(Turing, A.M.)於1939年引進的.具體地,對自然數集A和B,A可T化歸到,'B(記為A鎮TB),是指A相對於B可計算,即A的特徵函式可由一帶外部信息源B的圖靈機計算.由於用圖靈機可以很好地刻畫直觀可計算性概念(參見“丘奇論題”),因此,可以說圖靈可化歸性已很好地刻畫了直觀可化歸概念(參見“可化歸性”),也就是說,A是直觀上可化歸到B,若且唯若A鎮TB.當然,同能行可計算性一樣,T可化歸性的概念也有許多種等價的刻畫.

相關詞條

熱門詞條

聯絡我們