完全產生集

產生集.若存在遞歸函式f,使y.z(f(.z> EAE-"f(.z>任W二),則稱A為完全產生集.完全產生集是產生集概念的一種形式加強.實際上,邁希爾(Myhill , J.於1955年證明了A為完全產生集,若且唯若A是產生集.另外,如果A為re集,而A是完全產生集時,德克爾(Dekker,J.)稱之為能行非遞歸集.從而據邁希爾的結果,A為能行非遞歸的,若且唯若A為m完全集.

相關詞條

熱門詞條

聯絡我們