查看“波斯特对应问题”的源代码

'''波斯特对应问题'''（{{lang-en|Post correspondence problem}}）是美国数学家[[埃米尔·波斯特]]（{{lang|en|Emil Post}}）于1946年提出的一个不可判定问题。<ref name="Post46">{{cite journal|year = 1946|author = E. L. Post| title= A variant of a recursively unsolvable problem |journal = Bull. Amer. Math. Soc| volume =  52|url=http://www.ams.org/bull/1946-52-04/S0002-9904-1946-08555-9/S0002-9904-1946-08555-9.pdf}}</ref>

== 问题 ==
已知字母表<math>A</math>是包含至少两个字符的有限[[集合]]。<math>A</math>上的一个字符串是指由<math>A</math>中字符组成的一个有限序列。假设<math>\alpha_{1}, \ldots, \alpha_{N}</math>和<math>\beta_{1}, \ldots, \beta_{N}</math>是由<math>A</math>上的字符串所组成的两个相同长度的表。如果存在一个序列<math>(i_k)_{1 \le k \le K}</math>（<math>K \ge 1</math>，且对所有<math>k</math>都有<math> 1 \le i_k \le N</math>），使得
: <math>\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}</math>
成立，那么就称<math>A</math>上的这两个字符串表匹配。判定一个字母表上的任意两个长度相同的字符串表是否匹配的问题即是波斯特对应问题。

== 示例 ==
已知如下两个字符串表：
{{col-begin|width=auto}}
{{col-break}}
{| class="wikitable" style="text-align:center;background:#55FF83;font-style:italic;"
|-style="font-weight:bold;"
|width=40 | α<sub>1</sub>
|width=40 | α<sub>2</sub>
|width=40 | α<sub>3</sub>
|-
|a
|ab
|bba
|}
{{col-break|gap=5px|align=center}}
{| class="wikitable" style="text-align:center;background:#87E6FF;font-style:italic;"
|-style="font-weight:bold;"
|width=40 | β<sub>1</sub>
|width=40 | β<sub>2</sub>
|width=40 | β<sub>3</sub>
|-
|baa
|aa
|bb
|}
{{col-end}}

序列 (3, 2, 3, 1) 是这一波斯特对应问题的一个解：
: <math>\alpha_3 \alpha_2 \alpha_3 \alpha_1 = bba + ab + bba + a = bbaabbbaa = bb + aa + bb + baa = \beta_{3} \beta_{2} \beta_{3} \beta_{1}.</math>

{{col-begin|width=auto}}
{{col-break|align=center}}
{| class="wikitable" style="font-style:italic;text-align:center;"
| bgcolor="#55FF83" width="40" | bba
|-
| bgcolor="#87E6FF" width="40" | bb
|}
''i<sub>1</sub> = 3''
{{col-break|gap=5px|align=center}}
{| class="wikitable" style="font-style:italic;text-align:center;"
| bgcolor="#55FF83" width="40" | ab
|-
| bgcolor="#87E6FF" width="40" | aa
|}
''i<sub>2</sub> = 2''
{{col-break|gap=5px|align=center}}
{| class="wikitable" style="font-style:italic;text-align:center;"
| bgcolor="#55FF83" width="40" | bba
|-
| bgcolor="#87E6FF" width="40" | bb
|}
''i<sub>3</sub> = 3''
{{col-break|gap=5px|align=center}}
{| class="wikitable" style="font-style:italic;text-align:center;"
| bgcolor="#55FF83" width="40" | a
|-
| bgcolor="#87E6FF" width="40" | baa
|}
''i<sub>4</sub> = 1''
{{col-end}}

将上述序列重复任意多次（例如：重复两次为 (3, 2, 3, 1, 3, 2, 3, 1)）得到的序列也都是此问题的解。

但如果两个字符串表仅由<math>\alpha_2, \alpha_3</math> 和 <math>\beta_{2}, \beta_{3}</math>组成，那此时解便不存在。这是由于<math>\alpha_2, \alpha_3</math> 的倒数两个字符都是不同的，而<math>\beta_{2}, \beta_{3}</math>则都是由相同的两个字符组成的。

== 不可判定性证明思路 ==
对波斯特对应问题不可判定性的证明，一种最常见的思路是：先证明对一个[[图灵机]]<math>M</math>及输入<math>\omega</math>都能构造出波斯特对应问题的一个实例，使得匹配就是<math>M</math>在<math>\omega</math>上的接受计算历史。如果能判定这个波斯特对应问题的实例是否有匹配的话，那图灵机是否接受输入的问题也就是可判定的了。由于图灵机的接受问题是个基本的不可判定问题，于是可以说明波斯特对应问题也同样是不可判定的。<ref name="sipser05">{{cite book|author = Michael Sipser | year = 2005 | title = Introduction to the Theory of Computation | edition = 2nd | publisher = Thomson Course Technology | isbn = 0-534-95097-3 | chapter = A Simple Undecidable Problem | pages = 199–205}}</ref>

== 参考文献 ==
{{reflist}}

[[Category:计算理论]]