波斯特对应问题

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

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

\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}

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

单词	Post correspondence problem
释义	Post correspondence problem 中文百科波斯特对应问题波斯特对应问题（英语：Post correspondence problem）是美国数学家埃米尔·波斯特（Emil Post）于1946年提出的一个不可判定问题。已知字母表 $A$ 是包含至少两个字符的有限集合。 $A$ 上的一个字符串是指由 $A$ 中字符组成的一个有限串行。假设 $\alpha_{1}, \ldots, \alpha_{N}$ 和 $\beta_{1}, \ldots, \beta_{N}$ 是由 $A$ 上的字符串所组成的两个相同长度的表。如果存在一个串行 $(i_k)_{1 \le k \le K}$ （ $K \ge 1$ ，且对所有 $k$ 都有 $1 \le i_k \le N$ ），使得 $\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}$ 成立，那幺就称 $A$ 上的这两个字符串表匹配。判定一个字母表上的任意两个长度相同的字符串表是否匹配的问题即是波斯特对应问题。英语百科 Post correspondence problem 波斯特对应问题 The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
随便看	chorionic gonadotropin,CG的意思 chorionic gonadotropin hormone的意思 Chorionic Gonadotropin,Human的意思 chorionic gonadotropin, human的意思 Chorionic gonadotropin preparation的意思 Chorionic Gonadotropin Receptor的意思 Chorionic Gonadotropin Receptors的意思 Chorionic Gonadotropins的意思 chorionic gonadotropin unit的意思 chorionic growth hormone prolactin的意思 chorionic hormone的意思 chorionic lactogen的意思 chorionic mammotropin的意思 chorionic membrane的意思 chorionic membranes的意思 chorionic mesoderm的意思 chorionic placenta的意思 chorionic plate的意思 chorionic retrograde degeneration的意思 Chorionic sac的意思 chorionic shell的意思 chorionic somatomammotropin的意思 chorionic somatomammotropin,CS的意思 Chorionic Somatomammotropin,Human的意思 Chorionic somatomammotropin measurement的意思

Post correspondence problem

波斯特对应问题

Post correspondence problem 波斯特对应问题