圖定理

圖定理(graph theorem)反映部分函式的能行性與其圖的能行性之間關係的一個重要定理.該定理斷言:設滬為部分函式，f為全函式，圖G(p)指集合{(x,必}抓x)=少.則有下列結論:

基本介紹

• 中文名：圖定理
• 外文名：graph theorem
• 所屬學科：graph theorem

1. }p為部分遞歸函式，若且唯若滬之圖G 卯為re集.

2. f為遞歸函式，若且唯若其圖G (.f)為遞歸集.

另一方面，一個部分函式獷之圖為遞歸，當且僅存在遞歸關係R，使p(x)=fyR(xy).若取We筍。，則抓x=s(xEWe,是具遞歸圖的非全的部分遞歸函式.此外，有些部分遞歸函式之圖可以不是遞歸集.