因為網(wǎng)友十酒三的文章,突然對丟番圖集產(chǎn)生了興趣。
加上之前看《永恒的圖靈》時也看到過相關(guān)的討論,所以這里就記錄一些關(guān)于丟番圖集與遞歸可枚舉集的想法。
關(guān)于圖靈機
要理解遞歸可枚舉集,先要理解圖靈機。
圖靈機的定義,大家可以去查維基百科。
就個人而言,我比較喜歡這樣的定義,雖然并不是必須的:
- 有限非空離散集
被稱為底空間;
- 有限非空離散集
被稱為狀態(tài)空間;
-
圖靈空間 g 是
的元素,每個點都有一個位置對應(yīng)
中元素與一個狀態(tài)為
中元素;
-
圖靈點 x 是
的一個元素,其取值被稱為內(nèi)稟狀態(tài);
- 偏函數(shù)
被稱為轉(zhuǎn)移規(guī)則,它的功能是:
- 先將圖靈點當(dāng)前所處位置的狀態(tài)轉(zhuǎn)變?yōu)樾聽顟B(tài)
- 再將圖靈點的位置轉(zhuǎn)變?yōu)樾挛恢?/li>
- 最后將圖靈點的內(nèi)稟狀態(tài)轉(zhuǎn)變?yōu)樾聽顟B(tài)
- 如果
無定義,則計算停止并拒絕
-
中存在一個特殊的位置
,如果
產(chǎn)生該位置,則計算停止并接受
-
被稱為一臺圖靈機
很顯然, 的作用就是 description,而
的作用就是 configuration。前者描述了“紙帶”,后者描述了當(dāng)前圖靈機的狀態(tài)。
因此,圖靈機的運作過程,可以認(rèn)為是將一個圖靈點放在一個初始狀態(tài)的圖靈空間的給定初始位置、并讓它再轉(zhuǎn)移規(guī)則的作用下“自由運動”所產(chǎn)生的“世界線”,且最后有三種可能:
- 世界線在某處造成轉(zhuǎn)移規(guī)則無定義,此時稱初始狀態(tài)為“被拒絕的”;
- 世界線最終終止于特殊位置
,此時稱初始狀態(tài)為“被接受的”;
- 世界線永遠(yuǎn)不達(dá)到特殊位置
,此時稱初始狀態(tài)為“永不停止的”。
當(dāng)然,這么個說法其實沒多大意義,只不過看起來比較“絢”而已。
如果圖靈機最終被接受(當(dāng)然也就停機了),那么此時它的圖靈空間 被稱為是“輸出結(jié)果”,相應(yīng)的,一開始的圖靈空間
被稱為“輸入?yún)?shù)”。
因此,我們?nèi)绻豢粗匾活^一尾兩個狀態(tài)的畫,那圖靈機就是這樣的:,也即,它是將輸入?yún)?shù)映射到輸出結(jié)果的偏函數(shù),這是一句廢話。
我們?nèi)绻麑D靈空間中的狀態(tài)限定為有限非空符號集 的冪集
,那圖靈機顯然可以看作是能將有限個
映射到另一組有限個
的偏函數(shù),即:
這里 ,是所有圖靈機
可接受的輸入狀態(tài)的集合。而如果一個輸入狀態(tài)不在
,那圖靈機可能拒絕并停機,也可能永不停機。
這里,圖靈機 的可接受輸入狀態(tài)集
被稱為是一個“遍歷可枚舉集”。
同樣的,如果一個集合 被稱為是“遍歷可枚舉的”,那就表示存在一個圖靈機
,使得
恰好就是
的所有可接受輸入狀態(tài)構(gòu)成的集合。
停機不可判定問題告訴我們:我們永遠(yuǎn)不可能找到一個通用圖靈機 ,使得它能告訴我們?nèi)我庖粋€圖靈機
在給定輸入狀態(tài)下是否可以停機。
這也就是說,我們不可能找到一個通用圖靈機 ,使得它能判斷任意輸入狀態(tài)是不是某個圖靈機
的可接受輸入狀態(tài)。
從而,這就等于是說,不存在一個通用圖靈機能幫助我們來判斷一個集合是否是遍歷可枚舉的。
另一方面,讓我們來看一下丟番圖集。
所有形如 的方程被稱為“丟番圖方程”,如果其中系數(shù)
、
和
都是整數(shù)的話。比如說,我們最常見的一元二次方程
就是一個丟番圖方程;費馬方程
也是一個丟番圖方程,且我們知道當(dāng)
時該方程沒有整數(shù)解。
丟番圖方程 的整數(shù)根的存在性是一個非常有趣且艱深的問題,比如費馬方程在
時就沒有整數(shù)根。
因此,是否存在一個算法,能自動判斷任意輸入的丟番圖方程是否有整數(shù)解,就是一個很有趣的問題,如果存在的話,那包括費馬大定理在內(nèi)的很多問題就很容易解了。
現(xiàn)在,我們將一個丟番圖方程 中所有的系數(shù)提取出來:
,總共有
個參數(shù)。
接下來,我們將這 個參數(shù)中的一部分固定(也可以都不固定),另一部分為可變參數(shù)(只能取整數(shù)),一組這樣的可變參數(shù)就被稱為一個“參數(shù)組”。所有能讓該丟番圖方程有整數(shù)解的參數(shù)組構(gòu)成的集合,就被稱為該丟番圖方程的“丟番圖集合”。
也就是說,丟番圖集中的任意一個元素,都能確保對應(yīng)的丟番圖方程(包含那些被固定下來的整數(shù)參數(shù))必然有整數(shù)解,反之則該丟番圖方程沒有整數(shù)解。
這里,丟番圖集中的元素只是原來丟番圖方程所有參數(shù)中的一部分,所以我們既可以說丟番圖集對應(yīng)了一個丟番圖方程及其部分確定的參數(shù),這么一個確定的二元體,也可以說丟番圖集合對應(yīng)了一個丟番圖方程,丟番圖集中的每個元素都存在一組整數(shù)來補充那些“固定”的參數(shù),讓這個丟番圖方程有整數(shù)解。
如果丟番圖集和遍歷可枚舉集是一一對應(yīng)的,那由于遍歷可枚舉集是不可判定的,所以也就是說至少存在一個丟番圖集是無法通過圖靈機來判定的,這就等于說,至少有一個丟番圖方程(所有參數(shù)都固定),它是否有整數(shù)解是無法用圖靈機來判定的。
這等于就是說:希爾伯特的第十個問題的答案是否定的。
為了證明(及證偽)希爾伯特的第十個問題,人們努力了很久。戴維斯、普特南及美國首位入選國家科學(xué)院的女?dāng)?shù)學(xué)家茱莉婭·羅賓遜一起努力了很久,最后證明到這樣的程度:
- 所有丟番圖集必然是遍歷可枚舉的;
- 所有遍歷可枚舉集都是指數(shù)丟番圖集;
- 猜測所有指數(shù)丟番圖集都是丟番圖集(即存在“金發(fā)姑娘方程JR”,該猜想被稱為羅賓遜猜想)。
完成最后這個猜想的證明、也即證明存在JR的,是俄羅斯數(shù)學(xué)家尤里·馬基雅謝維奇。
于是,四個人聯(lián)合起來就證明了:丟番圖集金額遍歷可枚舉集是等價的。
這被稱為MRDP定理,也叫馬基雅謝維奇定理。
歷史介紹完了,下面說一下個人的想法。
這個定理很有趣,它告訴我們這么兩件事:
- 任何能讓一臺圖靈機接受并停機的輸入?yún)?shù),都能讓至少一個丟番圖方程有整數(shù)解;
- 任何能讓一個丟番圖方程有整數(shù)解的參數(shù)組,都能讓至少一臺圖靈機接受并停機。
發(fā)現(xiàn)沒有?
這里有趣的地方在于:丟番圖方程顯然是連續(xù)可微的(雖然丟番圖集與方程對應(yīng)函數(shù)的自變量無關(guān)),而圖靈機則是非常顯然的離散客體,這兩個乍看起來全然不同的東西,居然有如此奇妙的內(nèi)在聯(lián)系。
而且,更關(guān)鍵的是,我們印象里,方程與函數(shù)能做的事,圖靈機都能做;但圖靈機能做的事,方程與函數(shù)似乎未必都能做到。這樣的兩個“功能不對等”的東西,對于輸入?yún)?shù)居然有相同的要求,似乎很讓人驚訝。
但,轉(zhuǎn)念想想又感覺似乎有一種必然,畢竟丟番圖方程的數(shù)量和圖靈機的數(shù)量,是一樣多的,都是阿列夫0,因此存在這樣的映射關(guān)系似乎很正常。
事實上,之所以用丟番圖函數(shù)的參數(shù)而非輸入變量來和圖靈機的輸入狀態(tài)做對應(yīng),就是因為對于丟番圖函數(shù)這類多項式函數(shù)而言,只要輸入的變量不是無窮,那總是可以給出整數(shù)輸出的;但系數(shù)如果不恰當(dāng)?shù)脑?,那方程就很可能找不到整?shù)解。所以用參數(shù)而非變量來做對應(yīng),就看起來很合理了——我們甚至可以“猜想”那些整數(shù)解可能在某種程度上對用了相應(yīng)類型圖靈機的內(nèi)部狀態(tài),甚至是輸出,誰知道呢。
我之前甚至猜想,對于任意一個將 A 個輸入數(shù)據(jù)映射到 B 個輸出數(shù)據(jù)的圖靈機,在任意編碼規(guī)則(將數(shù)據(jù)映射到自然數(shù))下,都可以找到至少一組丟番圖函數(shù)(整系數(shù)多項式)與之一一對應(yīng),這組丟番圖函數(shù)有 B 個,每個都要有 A 個獨立輸入變量。
但隨后想想這樣的同構(gòu)映射應(yīng)該是不存在的,因為首先任意這樣的丟番圖函數(shù)組必然都可以映射到一類圖靈機,而這類丟番圖函數(shù)的特點是對于任意輸入的整數(shù),都可以唯一確定地輸出一個整數(shù),那就是說每一這樣的丟番圖函數(shù)組對應(yīng)的圖靈機對于任意輸入都必然能停機于接受狀態(tài)——但這顯然不是任意圖靈機都能滿足的情況,所以必然存在圖靈機無法被這樣的丟番圖函數(shù)組描述。
所以這里就再次體現(xiàn)出了用丟番圖函數(shù)的參數(shù)來對應(yīng)圖靈機輸入的好處了。
好了, 不執(zhí)著于這種內(nèi)在聯(lián)系帶來的詫異感,讓我們來考慮這么一個問題:
這兩個集合,還能不能拓展?
尤其,在丟番圖逼近中,我們已經(jīng)不要求一個丟番圖方程的參數(shù)必須是整數(shù)了,而可以是任意實數(shù)。這樣,所有能讓一個丟番圖方程有整數(shù)解的實系數(shù)的子集構(gòu)成的集,就是該丟番圖方程的“拓展丟番圖集”。
比如說, 這個丟番圖方程的丟番圖集為:
而它的拓展丟番圖集則可以是:
明顯大了很多,前者只是后者的一個子集。
但,這樣的拓展似乎還不夠“狂野”,讓我們來看下面這個:
它是一個泛函,稱為“丟番圖泛函”,其中函數(shù) 和
被稱為“參數(shù)函數(shù)”,函數(shù)
則是測試函數(shù)且要求
,
是實數(shù)的任意子集,被稱為“限制域”,而
為實數(shù)的另一個任意子集,被稱為“活動域”。假定,存在
及
使方程
成立,那么二元組
被稱為是“丟番圖問題組”
的一個“泛參數(shù)組”。
的所有泛參數(shù)組構(gòu)成的集合,就是這個丟番圖泛函的“泛丟番圖集”。
注意,這里函數(shù) 、
、
都不要求光滑,甚至都不要求連續(xù),所以完全可以是分段函數(shù)。而活動域
與限制域
也沒有任何要求,可以是可數(shù)集,也可以是離散集(這兩種情況下,積分就變成了求和),同樣也可以是豪斯道夫集。我們一般可以固定活動域與限制域來討論泛丟番圖集。
顯然,當(dāng)取 、
時,泛丟番圖集是上述拓展丟番圖集與丟番圖集的超集。
或者,更形式化的寫法是:
現(xiàn)在對丟番圖集的拓展算是很奔放地完成了,那么對遍歷可枚舉集的拓展呢?
或者,這里可以更準(zhǔn)確地問,是對圖靈機的拓展可以怎么玩。
在前面關(guān)于圖靈機的定義中,有幾個離散集:
- 有限非空離散集
被稱為底空間
- 有限非空離散集
被稱為狀態(tài)空間
如果將這兩個集合推廣呢?
比如這樣:
取任意空間 為底空間,底空間上任意元素上都直積一個內(nèi)稟空間(不要求離散與有限),稱為“外狀態(tài)空間”。而后,
上有一個“粒子”
,它對應(yīng)到
中的一個元素,稱為“位置”。
還有一個“內(nèi)稟狀態(tài)”,取值在“內(nèi)狀態(tài)空間”中。
現(xiàn)在,底空間、外狀態(tài)空間與內(nèi)狀態(tài)空間都不要求離散或有限,可以是任意集合。
事實上,這樣就有點纖維叢的意思了,但并不一樣。
轉(zhuǎn)移規(guī)則依然和前面所說的一樣,先改變粒子所處位置的外狀態(tài),然后改變粒子的內(nèi)狀態(tài),接著移動粒子到新的位置。它的作用有點像微分幾何中的聯(lián)絡(luò)——但我們并不要求這種移動只能在鄰近位置上移動,所以這可以說是添加了“蟲洞”結(jié)構(gòu)的纖維叢上的運動學(xué)問題了。當(dāng)然,我們也可以和標(biāo)準(zhǔn)圖靈機中讀寫頭只能局限在左右移動一格一樣,將這里對位置的改動限定在只能在當(dāng)前點的鄰域內(nèi)移動,那這樣看起來就更像是運動學(xué)問題了,于此同時對內(nèi)狀態(tài)和外狀態(tài)的改變看起來也更像是主從聯(lián)絡(luò)與底流形聯(lián)絡(luò)所干的事了。
一旦粒子的世界線進(jìn)入“無定義”的區(qū)域,就被拒絕并停止——可以類比掉入黑洞的奇點。
也可能粒子運動到了底流形上的特定區(qū)域,從而被接受并停止——可以類比閉合宇宙到達(dá)命運終結(jié)。
還有可能,粒子的世界線永遠(yuǎn)不會停止,一直在某個區(qū)域里打轉(zhuǎn)——可以類比開放宇宙永不終結(jié)。
而這種超圖靈機的初始狀態(tài),也就是底流形的初始狀態(tài),可以類比為宇宙在大爆炸時的狀態(tài)。
好了,類比歸類比,時空當(dāng)然不是這種定義下的超圖靈機了——大概不是吧。
現(xiàn)在,這種超圖靈機的輸入狀態(tài)(以及輸出狀態(tài))都不是離散集了。
如果 是連續(xù)空間,比如一個微分流形,那么輸入狀態(tài)就可以是
上的一條曲線,或者曲面。在這條曲線或曲面之外的點上的外狀態(tài)都為 0,而在這條曲線或曲面上的點的外狀態(tài)就構(gòu)成了輸入狀態(tài)。
因此,很顯然理論上泛丟番圖集與這里的可接受輸入狀態(tài)之間,是可以做對應(yīng)的。
于是,問題來了:
是否,任意上述拓展的超圖靈機的可接受初始狀態(tài),與某個泛丟番圖集,總能一一對應(yīng)?
開個腦洞的話,就是這樣的:
是否,任意物理規(guī)則下的閉合宇宙初始狀態(tài),與泛丟番圖集,總能一一對應(yīng)?
這個腦洞就比較奔放了——雖然更多只是好看,并無實際意義。
玩笑歸玩笑,問題還是在的。
我們對丟番圖集和圖靈機分別做了拓展,盡可能地將它們“連續(xù)化”,然后提出了相應(yīng)的泛丟番圖集與超圖靈可識別集之間,是否也存在如丟番圖集與圖靈可識別集之間那樣的一一對應(yīng)關(guān)系,這么一個問題。
當(dāng)然,這個問題本身我當(dāng)然現(xiàn)在是回答不了的。
我們來看下別的東西。
比如,可壓縮性。
在圖靈機領(lǐng)域,可壓縮性與算法復(fù)雜度相關(guān),具體來說是這樣的:
這里我們故意將圖靈機 與它的輸入?yún)?shù)
分開。任意字符串 s 的 K 氏復(fù)雜度的定義由上面給出,它如果小于
,那么就說 s 是可壓縮的。
現(xiàn)在,我們試著將問題移植到超圖靈機(記為 HTM)上。
我們將函數(shù) 稱為超圖靈機的一個狀態(tài)函數(shù)。在開始運作之前的狀態(tài)函數(shù)
被稱初態(tài),它是超圖靈機接受的輸入狀態(tài),而
上的一個元素被稱為“初始位置”,代表讀寫頭的“粒子”將從初始位置開始運動。如果粒子最終運動到指定的“終點位置”,則表示這臺超圖靈機停機于接受狀態(tài),此時的狀態(tài)函數(shù)
被稱為末態(tài)。
因此,停機于接受的超圖靈機就是映射:。
下面,我們可以定義一個能量函數(shù) ,從而可以定義一個狀態(tài)的能量:
另一方面,轉(zhuǎn)移函數(shù) 本身也可以被編碼,雖然我們目前不清楚到底應(yīng)該如何編碼,但可以形式化地記為
,從而一樣可以計算它的能量:
我們可以將一臺超圖靈機的轉(zhuǎn)移規(guī)則的能量作為這臺超圖靈機的能量,從而就可以形式化地定義“算法復(fù)雜度”了:
如果 ,那我們就說狀態(tài)函數(shù)
是可壓縮的。
從類比的角度來看,可壓縮狀態(tài)意味著能量可以進(jìn)一步降低的狀態(tài),事實上也就對應(yīng)了熵可以進(jìn)一步增高的狀態(tài),所以在這個系統(tǒng)中,“熱力學(xué)熵”和超圖靈機的信息熵應(yīng)該是等價的,不可壓縮狀態(tài)也就意味著“黑體輻射”。
當(dāng)然,還是那句話,這種類比只適合開腦洞,沒多大實際意義。
或者,我們也可以和十酒三的思路一樣,從代數(shù)的角度來看不可壓縮性:
給定函數(shù)集 ,若對于集合
有如下關(guān)系成立,則稱
在
上是可壓縮的:
也即,存在至少一個函數(shù),能讓任意一項數(shù)據(jù)可以通過給定集合中的別的數(shù)據(jù)導(dǎo)出。我們將這個關(guān)系記為 。
這種形式的數(shù)據(jù)其實很常見,比如讓我們選擇一個 D 維矢量空間,函數(shù)集里只有一個矢量加法,而數(shù)據(jù)集我們?nèi)∵@個 D 維矢量空間的 D 個基矢,由于它們顯然彼此是線性無關(guān)的,所以這個數(shù)據(jù)集無法在矢量加法集上被壓縮。
而可壓縮集當(dāng)然也很多,比如現(xiàn)在我們將上面這個粒子中的函數(shù)集替換為矢量加法與矢量外乘,那我們只需要兩個基矢就足夠了,第三個基矢可以通過這兩個基矢的外乘來得到,從而可以被壓縮掉。
當(dāng)然,問題可以變得更加復(fù)雜——假定數(shù)據(jù)集 在函數(shù)集
上不可壓縮,但如果加上數(shù)據(jù)集
之后,集合
就能在
上壓縮了,那這樣的情況就很有趣了。
我們可以構(gòu)造這樣的函數(shù):
因此,如果 在
上可壓縮,那
。
同樣的,我們也可以構(gòu)造 是
的一個子集,可以通過
與函數(shù)
構(gòu)造出
中的所有的元素。我們記
為數(shù)據(jù)集
通過函數(shù)
生成的數(shù)據(jù)集,所以顯然有
。這樣我們就可以定義另一個函數(shù):
因此,這個函數(shù)體現(xiàn)了數(shù)據(jù)集的不可壓縮的部分,假如 則
。
這兩個函數(shù)可以在一定程度上刻畫 與
的很多特性。
但,這樣的性質(zhì)如何和圖靈機對應(yīng)上,看起來還有點撲朔迷離——如果我們將這里的函數(shù)集替換成所有可能的圖靈機,那顯然我們可以將任意一個整數(shù)集都給壓縮得渣都不剩,所以對于圖靈機的情況而言,我們會要求加上圖靈機本身的“長度”。
但在函數(shù)的問題中,函數(shù)的“長度”是我們不知道的東西。我們當(dāng)然可以和上一部分所提的一樣,將函數(shù)給編碼,然后用編碼長度來表達(dá)函數(shù)的“長度”,但這樣的做法下可壓縮性的表述就又會顯得很不純粹。
拉拉雜雜地寫了很多看丟番圖集與遞歸可枚舉集的對應(yīng)關(guān)系時的想法,基本都是腦洞為主。
這塊感覺很有趣,可惜一直沒時間系統(tǒng)地看下,挺可惜的。
本文遵守創(chuàng)作共享CC BY-NC-SA 4.0協(xié)議
通過本協(xié)議,您可以分享并修改本文內(nèi)容,只要你遵守以下授權(quán)條款規(guī)定:姓名標(biāo)示 、非商業(yè)性、相同方式分享。
具體內(nèi)容請查閱上述協(xié)議聲明。
紙媒與網(wǎng)絡(luò)平臺如需轉(zhuǎn)載必須與本人聯(lián)系確認(rèn)。