圖靈機接受字的集合.設M為以J獷為字母表的圖靈機，在M的內部狀態集Q中指定一個子集Y里Q，Y中的內部狀態q:為接受狀態.對J獷上的任何字。，若M在輸入。後會在有窮步內停機，並且停機時最終的內部狀態是一個接受狀態(此時也稱停機於接受狀態)，則稱M接受。，否則便稱M拒絕。.如果M是確定型圖靈機，則M接受。的計算過程是惟一的.相反，當M為非確定型圖靈機時，輸入。之後，它可能有好幾種計算過程.此時，只要其中有一條計算路徑會停機於接受狀態，就稱M接受。.實際上，還可能有此計算路徑並不停機或即使停機也不停機於接受狀態的.這是確定型與非確定型圖靈機之間的重大差別.注意到當M接受字。時，總可在有窮步內能行地判定，但當M拒絕。的情形，未必有一個能行的方法在有窮步內加以驗證.因此，M是否接受字。是一個半可判定的問題，而圖靈機M接受的語言是一個遞歸可枚舉集合.
基本介紹
- 中文名：圖靈機接受語言
- 所屬學科：數學
圖靈機接受字的集合.設M為以J獷為字母表的圖靈機，在M的內部狀態集Q中指定一個子集Y里Q，Y中的內部狀態q:為接受狀態.對J獷上的任何字。，若M在輸入。後會在有窮步內停機，並且停機時最終的內部狀態是一個接受狀態(此時也稱停機於接受狀態)，則稱M接受。，否則便稱M拒絕。.如果M是確定型圖靈機，則M接受。的計算過程是惟一的.相反，當M為非確定型圖靈機時，輸入。之後，它可能有好幾種計算過程.此時，只要其中有一條計算路徑會停機於接受狀態，就稱M接受。.實際上，還可能有此計算路徑並不停機或即使停機也不停機於接受狀態的.這是確定型與非確定型圖靈機之間的重大差別.注意到當M接受字。時，總可在有窮步內能行地判定，但當M拒絕。的情形，未必有一個能行的方法在有窮步內加以驗證.因此，M是否接受字。是一個半可判定的問題，而圖靈機M接受的語言是一個遞歸可枚舉集合.
