下標系統

下標系統是全體部分遞歸函式的一種編碼方法。

基本介紹

• 中文名：下標系統
• 外文名：system of index

下標系統(system of index)全體部分遞歸函式的一種編碼方法.設必為從。到全體n元部分遞歸函式的一個滿射，_ 尹o InE叫，則必稱為部分遞歸函式的一個下標系.約定c＞’表示少＞,e，並稱。為樹,a的下標.若對任何n，存在a，使

公式

則稱必可參數化.{襯”，}r。‘給出了一種具有枚舉性並且可參數化的下標系，該下標系特稱為標準系一般地，若下標系滬與標準系能行可互換，即存在遞歸函式f和g，使對任何n和。，衫”’一娜^' &c.＞樹”，一翰a則稱下標系滬為可接受的.美國數學家羅傑斯Rogers , H.證明了一個下標系必為可接受的，若且唯若必同時具枚舉性和可參數化性質，也若且唯若存在遞歸置換h，使對任何‘和n,召”’一袱打.對於一個可接受的下標系必來說，相應的枚舉定理、參數定理、遞歸定理、墊襯引理都成立.從而遞歸論的基本內容也可相應地發展出來.因此，從某種意義上講，遞歸論的討論是不依賴於任何一種(可接受的)下標系統的。