圖靈可計算函式

圖靈可計算函式(Turing computable function)簡稱T可計算函式.可用圖靈機來計算的一類函式.設滬為一個(部分)數論函式，如果M為圖靈機，並且對任何自然數n，若以紙帶上連續的n+1個1(記為n或1.}+ i)作為M的輸人後，M會停機，若且唯若抓n)有定義，而且當M停機時的輸出中恰好有n)個“1".則稱M計算筍一般地，若滬為k元函式，則M計算滬時，要以形如xl}x.Z...13xk的串作為與(二，}x2,"..}x.k)相應的輸人，此時，其輸出(若有的話)中的1的個數恰好為}p(x,，二:，…，二走).若存在一個圖靈機來計算滬，則稱滬為圖靈機可計算的.設}M}.}PE},為全體靈機的一種能行枚舉，若從所計算的n元(部分)函式記為襯}}e，則{}<n> }eE。便是全體元T可計算函式的一種能行枚舉.此時，。稱為可·，的下標，在許多場合，襯n>常可簡寫成}p}. T可計算的函式一定是直觀能行可計算的，而依丘奇論題，直觀能行可計算函式恰好是全體T可計算函式.從這個意義上說，T可計算函式給出了直觀能行可計算函式這個概念的一個精確刻畫.