补充资料：Post对应问题

Post对应问题
Post correspondence problem

…氢呀挂到土蹄肇歹月因此，字 以4+Zr+l)2(4+厂+2)(4+Zr+n+2) 3(4+2)(4+3)2(4+r+2)(4+Zr+n+3)4〔为清楚起见，这里已经加了括号)是尸C尸的一个解，对于这个字态射以和h的共同值是: BS#a‘C‘D‘#’aD#a’D‘#‘adE(AS) 显然，通过下面简单的修改，由(A4)推出(AS).把B和E的边界标志加在开头和末尾;符号”由#代替;与每第二个#一样，第二步都加撇;最后为达到那个对应于(A4)的最后指标的非撇字“d加一个(从aD到a‘D‘)“空档”步. 容易看出，类似的论证在一般情况下是有效的:侮当、、属于L(G)，则尸CP有一解(见【4】，那里用详细的归纳方法证明了这个事实).其反面—即如果尸C尸有解，则w属于L(G)—的证明则多少有点困难(见【41). 如果态射g和h的值域字母表△仅由两个字母组成，用简单的编码方法能证明Post对应问题仍然是不可判定的.其定义域字母表Z仅由两个字母组成的情况下的可判定性已在汇AI]中证明.若g或h是周期的(periedic)，也就是说，它的所有值是某单个字母的幂，则特例(夕，h)组成了另一个非平凡的可判定的子类【A41.如果z由9个字母组成，则Post对应问题仍然是不可判定的.如果艺的基数是在3和8(包括3和8)之问的一个固定的数，其可判定性仍未解决. Post对应问题是与在形式语言的表示理论中十分重要的等式集(eq让llity sets)密切相关的根据定义，夕和h的等式集由所有使得g(w)二h(、叼的字w组成.显然，一个特例(g，h)有一个解，当且仅当这等式集包含一个非空字.有用的是Post对应问题.例如，当处理上下文无关语言!l寸，用停机问题作为参照点是相当困难的，然而Post对应问题却是非常合适的. Post对应问题是这样的:对两个均由n个字组成的列作出判定，是否在一个列中的某些字的毗联等干另一列中字的对应毗联(correspondi飞catenat沁n).此处“对应”是指所用的字在两个列中的位置必须完全相同.例如，如果两个列是 (aZ，b’，ab’)和(a’b，ba，b)，(AI)将这两列中的第1，2，1，3个字(依次)毗联起来，则在两列中均得到字“Zb’a’b“.这件事被说成“指标序列l，2，1，3是Post对应问题的特例(AI)的一个解(solution)”.另一方面，由两列 (a Zb，a)和(a’，b aZ)(AZ)组成的特例没有解.这能用下面的方法证明.(A2)的一个可能的解必须由指标l开始.因为第二列中的字必须“补上”缺少的b，所以指标2必须紧接着.这样就得到字aZba和aZb““.因为这两个字中的一个必须是另一个的前缀，所以断定此解中的下一个指标必定是2，结果得到字aZba’和a’b“

[1] [2]  下一页

说明：补充资料仅用于学习参考，请勿用于其它任何用途。