计算机科学

首页 > 计算机科学

波斯特对应问题

2018-08-30 09:59:34     所属分类:计算理论

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

目录

  • 1 问题
  • 2 示例
  • 3 不可判定性证明思路
  • 4 参考文献

问题

已知字母表是包含至少两个字符的有限集合。上的一个字符串是指由中字符组成的一个有限序列。假设是由上的字符串所组成的两个相同长度的表。如果存在一个序列,且对所有都有),使得

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

示例

已知如下两个字符串表:

α1 α2 α3
a ab bba

β1 β2 β3
baa aa bb

序列 (3, 2, 3, 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))得到的序列也都是此问题的解。

但如果两个字符串表仅由组成,那此时解便不存在。这是由于 的倒数两个字符都是不同的,而则都是由相同的两个字符组成的。

不可判定性证明思路

对波斯特对应问题不可判定性的证明,一种最常见的思路是:先证明对一个图灵机及输入都能构造出波斯特对应问题的一个实例,使得匹配就是上的接受计算历史。如果能判定这个波斯特对应问题的实例是否有匹配的话,那图灵机是否接受输入的问题也就是可判定的了。由于图灵机的接受问题是个基本的不可判定问题,于是可以说明波斯特对应问题也同样是不可判定的。[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. 

上一篇:阿克曼函数
下一篇:递推关系式
相关推荐