波斯特对应问题

波斯特对应问题（英語：Post correspondence problem）是美国数学家埃米尔·波斯特（Emil Post）于1946年提出的一个不可判定问题。^[1]

问题

已知字母表${\displaystyle A}$ 是包含至少两个字符的有限集合。${\displaystyle A}$ 上的一个字符串是指由${\displaystyle A}$ 中字符组成的一个有限序列。假设${\displaystyle \alpha _{1},\ldots ,\alpha _{N}}$ 和${\displaystyle \beta _{1},\ldots ,\beta _{N}}$ 是由${\displaystyle A}$ 上的字符串所组成的两个相同长度的表。如果存在一个序列${\displaystyle (i_{k})_{1\leq k\leq K}}$ （${\displaystyle K\geq 1}$ ，且对所有${\displaystyle k}$ 都有${\displaystyle 1\leq i_{k}\leq N}$ ），使得

${\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}}$ 

成立，那么就称${\displaystyle A}$ 上的这两个字符串表匹配。判定一个字母表上的任意两个长度相同的字符串表是否匹配的问题即是波斯特对应问题。

示例

已知如下两个字符串表：

α1 α2 α3 a ab bba

β1 β2 β3 baa aa bb

序列 (3, 2, 3, 1) 是这一波斯特对应问题的一个解：

${\displaystyle \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}.}$ 

bba bb i1 = 3

ab aa i2 = 2

bba bb i3 = 3

a baa i4 = 1

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

但如果两个字符串表仅由${\displaystyle \alpha _{2},\alpha _{3}}$  和 ${\displaystyle \beta _{2},\beta _{3}}$ 组成，那此时解便不存在。这是由于${\displaystyle \alpha _{2},\alpha _{3}}$  的倒数两个字符都是不同的，而${\displaystyle \beta _{2},\beta _{3}}$ 则都是由相同的两个字符组成的。

不可判定性证明思路

对波斯特对应问题不可判定性的证明，一种最常见的思路是：先证明对一个图灵机${\displaystyle M}$ 及输入${\displaystyle \omega }$ 都能构造出波斯特对应问题的一个实例，使得匹配就是${\displaystyle M}$ 在${\displaystyle \omega }$ 上的接受计算历史。如果能判定这个波斯特对应问题的实例是否有匹配的话，那图灵机是否接受输入的问题也就是可判定的了。由于图灵机的接受问题是个基本的不可判定问题，于是可以说明波斯特对应问题也同样是不可判定的。^[2]

参考文献

1. E. L. Post. A variant of a recursively unsolvable problem (PDF). Bull. Amer. Math. Soc. 1946, 52. 
2. Michael Sipser. A Simple Undecidable Problem. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2005: 199–205. ISBN 0-534-95097-3.