[科普中國]-判定器

在可計算性理論中，總是停機(jī)的機(jī)器也叫做判定器（Sipser，1996年）或全圖靈機(jī)（Kozen，1997年）是對所有輸入總是停機(jī)的圖靈機(jī)。

簡介因為判定器總是停機(jī)，這個機(jī)器有能力判定給定字符串是否是一個形式語言的成員?？捎蛇@種機(jī)器判定的語言類精確的是遞歸語言的集合。但是由于停機(jī)問題，判定任意圖靈機(jī)是否在任意輸入上停機(jī)的問題自身是不可判定的判定問題。1

全圖靈機(jī)可計算的函數(shù)在實踐中，很多有價值的函數(shù)都是用總是停機(jī)的機(jī)器可計算的。通過限制它的流控制能力就可以強(qiáng)制機(jī)器對所有輸入都停機(jī)，使得沒有程序可以導(dǎo)致機(jī)器進(jìn)入無限循環(huán)。作為平凡的例子，實現(xiàn)有限判定樹的機(jī)器將總是停機(jī)。

不要求機(jī)器完全免除循環(huán)能力來保證停機(jī)。如果我們限制循環(huán)為有可預(yù)測的有限大小，我們可以表達(dá)所有原始遞歸函數(shù)(Meyer and Ritchie, 1967)。Brainerd 和 Landweber (1974) 的玩具編程語言 PL- {GOTO} 就是這種機(jī)器的一個例子。

我們可以進(jìn)一步的定義能確保更復(fù)雜的函數(shù)總是停機(jī)的一個編程語言。例如，不是原始遞歸函數(shù)的阿克曼函數(shù)，但它是通過帶有在它的參數(shù)上的簡約排序的項重寫系統(tǒng)可計算的全可計算函數(shù)。1

與偏圖靈機(jī)的關(guān)系一般的圖靈機(jī)可以計算偏函數(shù)。有關(guān)于偏圖靈機(jī)和全圖靈機(jī)之間關(guān)系的兩個問題:

所有用偏圖靈機(jī)可計算的偏函數(shù)都可以被擴(kuò)展(就是說擴(kuò)大它的定義域)成為全可計算函數(shù)嗎?

有可能改變圖靈機(jī)的定義使得特定類的全圖靈機(jī)計算所有全可計算函數(shù)?

對這兩個問題的答案都是否定的。

下列定義證明了對總是停機(jī)的機(jī)器是可計算的函數(shù)不包括所有偏可計算函數(shù)的擴(kuò)展，這蘊涵了上述第一個問題有否定答案。這個問題密切關(guān)系于停機(jī)問題的算法上不可解。

定理。有不能擴(kuò)展成全圖靈機(jī)可計算函數(shù)的圖靈可計算偏函數(shù)。特別是偏函數(shù)f，它被定義得使f(n) =m，當(dāng)且僅當(dāng)帶有附標(biāo)n的圖靈機(jī)停機(jī)于輸入0并輸出m，它沒有到全可計算函數(shù)的擴(kuò)展。

反證法進(jìn)行證明。如果g是擴(kuò)展f的全可計算函數(shù)，則g將對某個圖靈機(jī)是可計算的；固定e作為這樣一個機(jī)器的附標(biāo)。使用Kleene遞歸定理建造一個圖靈機(jī)M，它在輸入0上模擬運行在M的一個附標(biāo)nM上的帶有附標(biāo)e的機(jī)器(因此機(jī)器M可以生成自身的一個附標(biāo)；這是遞歸定理扮演的角色)。通過假定，這個模擬將最終返回一個答案。定義M使得如果g(nM) =m則M的返回值是m + 1。因此f(nM)，M在輸入0上的真返回值將不等于g(nM)。這矛盾于g擴(kuò)展f的假定。

第二個問題在本質(zhì)上問是否有另一個合理的計算模型只計算全函數(shù)并計算所有全可計算函數(shù)。非形式的說，如果這種模型存在，則它的每個計算機(jī)都可以被一個圖靈機(jī)模擬。因此如果這個新計算模型由一序列機(jī)器 組成，則會有計算全函數(shù)的圖靈機(jī)的遞歸可枚舉序列 ，因而所有全可計算函數(shù)都對機(jī)器Ti之一是可計算的。這是不可能的，因為機(jī)器T可以被構(gòu)造的使得在輸入i上機(jī)器T返回 。那么T將是全機(jī)器，因為每個Ti是全的，并且由T可計算的函數(shù)不能出現(xiàn)在列表中。這證明了第二個問題有否定的答案。2

全圖靈機(jī)的附標(biāo)的集合有附標(biāo)e的圖靈機(jī)是否在所有輸入上停機(jī)的判定問題是不可判定的。事實上，這個問題位于算術(shù)層次的 級別。因此這個問題嚴(yán)格的比停機(jī)問題更困難，它問有附標(biāo)e的機(jī)器是否停機(jī)在輸入0上。直覺的說，在不可解決性上的這個困難在于每個“全機(jī)器”問題的實例提出無限多個停機(jī)問題的實例。2

本詞條內(nèi)容貢獻(xiàn)者為:

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所