T度

T度(T-degree)亦稱圖靈度.遞歸論的基本概念之一它是由圖靈可化歸關係導出的度.集合A所在的圖靈度定義為:deg抓A)一{}}A=z}}.由於T可化歸關係很好地刻畫了直觀的可化歸概念,因此,用T度來刻畫一個集合(函式)的複雜程度是合適的,所以通常不可解度指的就是T度,而不可解度理論就是以T度作為主要研究對象的一門分支學科.雖然圖靈度的概念是用圖靈可化歸性定義,但圖靈度概念的明確定義則是由波蘭一美國數理邏輯學家波斯特(Post , E. I,.)於1944年給出的.因此,按通常的說法,關於不可解度的研究是由波斯特開創的.

相關詞條

熱門詞條

聯絡我們