波斯特對應問題

波斯特對應問題是一個重要的判定問題，提出者是美籍波蘭數學家E.L.波斯特，提出時間是1944年。波斯特對應問題在形式語言理論和程式設計理論中有重要套用。

基本介紹

• 中文名：波斯特對應問題
• 提出人物：E.L.波斯特
• 提出時間：1944年
• 領域：數學
• 套用：程式設計

概念

波斯特對應問題是一種不可判定性問題。一個波斯特對應系統是由一個字母表A和A上字的序偶〈h_i，k_i〉(i=1，2，…，m)的有窮集合組成的系統.A上的一個字u稱為該系統的一個解，是指存在i₁，i₂，…，i_n，1≤i₁，i₂，…，i_n≤m，使得u=h_i1h_i2…h_in=k_i1k_i2…k_in。

波斯特對應問題是指：是否存在算法，可以對任意的波斯特對應系統判斷它是否有解。通過半圖埃系統的不可判定性，可以證明波斯特對應問題是不可解的。波斯特對應問題是波蘭-美國數理邏輯學家波斯特(Post，E.L.)於1946年提出的一個判定問題，它的重要性在於利用它可以證明許多其他問題的不可判定性。

套用

由於圖靈機的停機問題是不可判定的，可以推出波斯特對應問題也是不可判定的，即不可能找到一個算法來判定同一字元集上的任意兩個相同長度的表是否有匹配。
波斯特對應問題在形式語言理論和程式設計理論中有重要套用。由於波斯特對應問題是不可判定的，可推出形式語言理論和程式設計理論中的許多問題是不可判定的。例如，任意上下文無關語言是否有歧義，這個問題就是不可判定的。

判定性問題

在設法解決一個數學問題時，我們首先關注的是它是否真有解?如果這裡“問題”不是單個的具體問題，而是由可列個同一類型的具體問題所組成，那么“解”應理解為一種普適的能行算法。這便是判定性問題。解決一個問題的判定性包括正反兩種可能：或是給出一個具體算法或至少證明這種算法的存在性，即可判定或可解;或證明不存在合適的算法，即不可判定或不可解。

萊布尼茨的夢想之一，是製作一台理想機器，可機械地檢驗數學定理。1895年希瑞德首次嚴格地提出了形式系統的判定性問題;希爾伯特規劃地提出，更引起人們對這方面的興趣。早期的判定性結果都是指定形式的。因不可判定的結果只有當算法的概念精確化以後，才有可能證明。丘奇關於謂詞演算及一階算術理論的不可判定的結果，刺激了判定性理論的形成與發展。

討論一個數學問題的判定性時，首先必須將該問題形式化。通常可化為如下形式：給定一個有窮字母表∑及一個性質P，P確定∑中一個語言L={ω∈∑*：ω具性質P}，問∑中任一字ω是否滿足P即ω∈L?另一類邏輯問題是已經形式化的，給定L理論T，問是否有算法可判定，對任一L語句ᵠ，T。後者實際上可以歸結到前者。然後套用哥德爾編碼技巧，把L1-1對應成ω的一個子集A。因此問題便歸結為斷定A是否是遞歸集。由於丘奇論題，這第2步往往可省去。編碼又稱記數的方法不是唯一的，只要保證1-1對應是能行的。常用的一種方法是利用整數因子分解的唯一性。例如，令∑={a，b，c}，字母a，b，c分別與素數2，3，5對應。若w=abc，則w的記數為n=2·3·5。反之，對任一自然數n，可能行地判定任一自然數m是否是∑中某個字的記數，若然也易找出相應的字。已證實： 素數及命題邏輯中的恆真命題是可判定的，自然數的加法理論、初等代數與幾何以及代數閉域理論等都是可判定的; 另一方面，一階邏輯的定理系，半群與群的字問題，希爾伯特第10問題 (丟番圖方程求整數解的通用算法) 等都是不可判定的。另一個著名的不可判定例子，圖靈機關於輸入的停機問題。在代數、拓撲、組合與圖論、數理邏輯以及計算機科學中，還有大量的例子。

人物簡介

博斯特是波蘭—美國數理邏輯學家。生於波蘭奧古斯圖夫，卒於美國紐約。7歲時跟從其父母由波蘭遷居美國。曾在紐約市學院學習。1917—1920年在哥倫比亞大學深造，先後獲得文學碩士(1918)和哲學博士(1920)學位。1921年任普林斯頓大學學監。1922年任哥倫比亞大學講師。1924年受聘於康奈爾大學。1927—1935年主要在中學教書。1935年以後在紐約市學院任教。波斯特是現代證明論和現代機器計算理論的開創人之一，在數理邏輯和數學基礎方面做出了重要貢獻。在1920年的博士論文中，證明了羅素和懷特海所提出的命題演算的相容性和完備性，系統地運用了真值表法則；討論了命題邏輯多值系統的建立並引入了多值真值表。1936年，他與圖靈幾乎同時引進了一種理想的計算機器即“圖靈機”，定義了可計算函式的概念。1947年，波斯特又證明了關於半群的字問題的遞歸不可解性(該問題於1914年被提出)。此外，在分析學方面，波斯特研究並給出了與拉普拉斯變換相聯繫的反演公式。波斯特在學術界相當活躍，1918年被選為美國數學會會員，1936年成為美國符號邏輯協會的創始會員。