拋丸機

[拼音]：Bosite duiying wenti

[英文]：Post correspondence problem

美籍波蘭數學家E.L.波斯特於1944年提出的一個重要的判定問題。字符集A是字元的非空有限集合，A中字元的有限序列稱為A上的字串。設u1，u2，…，um是A上的字串，用u1u2…um表示把這字串中的m個字元連線在一起所得到的字串。A上的表是A上的字串的有限序列，序列的長度稱為表的長度。例如，ab，∧，aa是字符集｛a，b｝上的長度為3的表，其中∧表示不含任何字元的空字串。

設l1，l2，…，lk和m1，m2，…，mk是同一字符集A上的兩個相同長度的表，如果存在小於或等於k的正整數i1，i2，…，in使l彲l彸…l拠＝m彲m彸…m拠，則稱表l1，l2，…，lk和m1，m2，…，mk有匹配。例如，A＝｛0，1｝，l1＝1，l2＝10111，l3＝10，m1＝111，m2＝10，m3＝0，因l2l1l1l3＝m2m1m1m3＝101111110，因此，l1，l2，l3和m1，m2，m3有匹配。判定同一字符集上的任意兩個相同長度的表有沒有匹配的問題稱為波斯特對應問題。

由於圖靈機的停機問題是不可判定的，可以推出波斯特對應問題也是不可判定的，即不可能找到一個演算法來判定同一字符集上的任意兩個相同長度的表是否有匹配。

波斯特對應問題在形式語言理論和程式設計理論中有重要應用。由於波斯特對應問題是不可判定的，可推出形式語言理論和程式設計理論中的許多問題是不可判定的。例如，任意上下文無關語言是否有歧義，這個問題就是不可判定的。

參考書目

J. Hopcroft and J. Ullman， Introduction to Automata Theory， Languages， and Computation，Addison-Wesleg，Reading，Mass，1979.