皺鰓鯊目

[拼音]：panding wenti

[英文]：decision problem

判定所謂“大量問題”是否具有演算法解，或者是否存在能行的方法使得對該問題中的每一特例能在有限步內機械地判定它是否具有某種性質（如是否真、是否可滿足或是否有解等，隨大量問題本身的性質而定）的問題。大量問題是與單個問題相對立的，它一般由無窮多個具有某種共性的單個問題組成。

上述“是否有演算法解”，“是否存在能行的方法”的說法中的“是”，指有演算法解或有能行的方法，這是不成問題的，因為憑人們的直觀至少在理論上總可以判斷一個解或一種方法是演算法解或是能行的方法，儘管有時它很長而且很複雜；但對其中的“否”即不存在演算法解或不存在能行的方法，則問題要麻煩得多。這要求要有精確的“演算法”概念或精確的“能行性理論”概念。後兩者在30年代才建立和發展起來，併成了“遞迴論”的基礎部分。有了精確演算法概念之後，隨即發現許多長期懸而未決的大量問題不存在演算法解，或者說是演算法不可解的（根據丘奇論題，有時又說是遞迴不可解的），或者說該問題是不可判定的。其中最著名的有：

（1）狹謂詞演算（也稱一階邏輯、一階函項演算等）公式的可滿足性的判定問題（A.丘奇，1936；A.M.圖靈，1937）；

（2）群的字問題（∏.С.諾維科夫，1955；W.W.布恩，1959）；

（3）希爾伯特第10問題。

上述問題①就是希爾伯特所謂的“判定問題”。希爾伯特稱它是數理邏輯的基本問題或中心問題。如上所說，1936年已證明此問題不可解（指演算法不可解）。但全體公式類的不可解並不蘊涵其子類的不可解性。事實上狹謂詞演算公式集的許多子類是有演算法解的；當然也同樣有許多子類（特別是所謂“歸約類”）是不可解的。不妨把這方面的判定問題即由希爾伯特的“判定問題”所引伸出來的問題稱為“狹義的判定問題”，並把對於一般的大量問題的相應問題籠統地叫作“判定問題”。

狹義判定問題

狹謂詞演算公式的最簡單而且最著名的可判定子類是全體只含一目謂詞的公式類（L.勒文海姆，1915；A.T.斯科朗，1919；H.伯赫曼，1922），以及如下的兩個前束類：

（1）具有前束彐…彐凬…凬的前束公式類（P.貝爾奈斯、M.S.芬克爾，1928）；

（2）具有前束彐…彐凬凬彐…彐的前束公式類（K.哥德爾，1932；L.卡爾馬，1933；K.許特，1934）。

在討論一階邏輯的不可解公式類之前先介紹“歸約類”的概念。簡單地說，它們是這樣的一些公式類，使得全體公式的判定問題能夠能行地化歸為這些類的判定問題。這方面最早和最簡單的情形是隻包含二目謂詞變元的公式類(勒文海姆，1915)以及具有前束凬…凬彐…彐的前束公式類（斯科朗，1920）。

由丘奇和圖靈的結果推出一切歸約類均為不可判定的。圖靈的證明是十分直截了當的。他用一階邏輯中的公式對圖靈機進行編碼，由此由圖靈機停機問題的不可解性便推出一階邏輯的不可判定性。

歸約法和編碼法仍是證明一階邏輯公式類不可判定性的兩個主要方法，利用歸約法可以證明如下公式類的不可判定性：

（3）具有前束凬凬凬彐的前束公式類（J.蘇拉尼，1950）。

利用對“鋪磚問題”進行編碼可證如下公式類的不可判定性：

（4）具有前束凬彐凬的前束公式類（A.S.卡爾，E.F.莫爾和王浩，1962）。

（3）和④中的公式類都是歸約類，而且可以看出公式類③為歸約類一事可以容易地由④中公式類的歸約性推出。不僅如此，有了④後許多有趣的歸約類都能十分容易地得到。

綜合①～④，如果不考慮等詞，則有如下結果，它表明對前束公式類而言可解與不可解的問題已經完全解決。

給定任何量詞串

Q

1x1，

Q

2x2，…，

Q

kxk，由此量詞串所確定的前束類是一個關於可滿足性的歸約類，當且僅當該量詞串包含凬彐凬或凬凬凬彐作為保持順序而不一定相連結的子串。每個不是歸約類的前束類都是可判定的。

如果單考慮公式中謂詞的目數和個數，則有如下結果，它在這方面可能是最好的了。

（5）一切只含惟一的二目謂詞變元R的公式的集是歸約類（卡爾馬，1936）。

狹義判定問題還有許多問題沒有論及。主要是未討論前束公式的母式的真值函式形式以及出現在原子子公式中的個體變元的順序等。

關於狹義判定問題的另一個重要結果，是由Б.Α.特拉赫堅布羅特於1950年證明的，即一階邏輯中公式是否在一有窮個體域上可滿足是不可判定的。

一般大量問題的判定問題

又分為一階(或初等)理論的判定問題和其他數學判定問題。前者是指給了一個形式理論，要求判定屬於相應語言的任一語句σ能否由該理論推出，或等價地，σ是否在該理論的一切模型上為真。例如，G.皮亞諾算術理論

P

A

和公理集合論中的ZF系統都是不可判定的一階理論的例子，而實閉有序域或代數封閉域的一階理論則是可判定的一階理論的兩個例子。後者的例子也很多，如群的字問題（M.德肯，1911），丟番圖方程可解性的判定問題（希爾伯特第10問題，1900）等。

可判定理論的例子

以下對一數學結構或模型ц0，令Th(ц)表一切在ц上真的語句組成的完備理論。

（1）Th(＜ω，≤＞)（C.H.蘭福德，1927；其中ω表全部自然數的集合）；

（2）Th(＜

Q

，≤＞)（蘭福德，1927；其中

Q

表全體有理數的集合）；

（3）Th(＜ω，+＞)，（M.普雷斯伯格，1929）；

（4）Th(＜R，0，1，+，·，≤，＞)（A.塔爾斯基，1948;其中R表一切實數的集合）；

（5）代數封閉域的初等理論（塔爾斯基，1948）；

（6）交換群的初等理論（W.什米萊夫，1954）；

（7）布林代數的初等理論（塔爾斯基，1940）。

以上諸理論的可判定性均可用消去量詞方法得到，而①～⑤情形的可判定性亦可用模型論方法得到。用模型論方法可證明其可判定性的理論還有：

（8）

P

進位域的初等理論（J.阿克斯和 S.B.科琴，1965～1966）；

（9）有限域的初等理論（阿克斯，1968）；

（10）線性（全）序集的初等理論（A.埃倫託伊希特，1959）。

情形（8）否定了長期懸而未決的如下猜想：除實閉域和代數封閉域外，沒有其他可判定的無限域。

證明理論的可判定性的方法除上面提到的消去量詞和模型論方法外還有解釋方法。情形（3）的可判定性就可用解釋方法證明。不過用解釋方法證明為可判定的理論大都是二階的。

不可判定的理論

丘奇1936年用哥德爾1931年證明不完備性定理的想法首先證明了皮亞諾算術理論

P

A

（及其若干子理論）為不可判定的。J.B.羅塞同年證明

P

A

的任何無矛盾擴張均為不可判定的。塔爾斯基稱這樣的理論為本質不可判定理論。這種證明不可判定性的方法叫做直接方法。用直接方法能證明其不可判定性的理論應當充分強，使得數論的推理工具能在其中發展。還有一種間接方法，即歸約方法，其要點在於，把一理論T1的判定問題歸約到一不可判定的理論T2，由此證明T1亦為不可判定的。這裡又分兩種情形：

（1）證明T1由T2刪去有限條公理而得，丘奇正是用這一方法於1936年證明一階邏輯為不可判定的。

（2）證明某一本質不可判定理論T2可以在T1中解釋。採用

P

A

作為本質不可判定理論T2，可證明各種公理集合論系統為不可判定的。

上述間接方法的適用範圍仍是有限的。還有一種廣義間接方法，它把上一方法中的兩種情形①、②的某些特點結合起來。這就是說，為了證明理論T1不可判定，只須把一有窮可公理化的本質不可判定理論T2在T1的某一無矛盾擴張中解釋即可。此種理論T2自然不能沿用

P

A

，因後者是不可有窮公理化的。下面的魯賓孫系統

Q

適合一切要求，其公理只有7條

用這種廣義間接方法已證明：群、環、域和格的初等理論均是不可判定的。還可證明，各種型別的群、環、域和格的初等理論的不可判定性。R.M.魯賓孫還用這些方法證明了許多特殊環R的完備初等理論Th(R)為不可判定的。此種環稱為不可判定的環。

不可解的問題

大批不可解的問題屬於組合判定問題，其中較有意義的是半群的字問題(A.圖埃，1914)和群的字問題。前一問題已證明為不可解的（E.L.波斯特，1947；Α.Α.馬爾可夫，1949）。群的字問題則要困難得多。如前面所說它的不可解性已由諾維科夫和布恩在50年代相互獨立地證明。值得指出的是G.希格曼1961年證明了如下定理。