能行可加速函式

能行可加速函式(effectively speedable func-lion)一種可加速函式。指可能行地找到越來越好的算法的可計算函式.設g為二元遞歸函式,中-{}r}rE。為布魯姆測度.若對部分遞歸函式f的任何下標i,都可能行地找到f的另一個下標J,使得
能行可加速函式
由於次創造集一定是T完全的,從而一定是非遞歸的,故若f為遞歸函式,或是某個測度函式時,f一定不是能行可加速的,但它們卻可能是g可加速的.

相關詞條

熱門詞條

聯絡我們