波斯特对应问题

波斯特对应问题是一个重要的判定问题，提出者是美籍波兰数学家E.L.波斯特，提出时间是1944年。波斯特对应问题在形式语言理论和程序设计理论中有重要应用。波斯特对应问题是一种不可判定性问题。一个波斯特对应系统是由一个字母表A和A上字的序偶〈hi，ki〉(i=1，2，…，m)的有穷集合组成的系统.A上的一个字u称为该系统的一个解，是指存在i1，i2，…，in，1≤i1，i2，…，in≤m，使得u=hi1hi2…hin=ki1ki2…kin。