Samræmingarverkefni Posts

Samræmingarverkefni Posts er óleysanlegt ákvörðunarvandamál sem Emil Post lagði til árið 1946. Vandamálið gengur út á að taka tvo endanlega orðalista $\alpha_{1}, \ldots, \alpha_{N}$ og $\beta_{1}, \ldots, \beta_{N}$ úr einhverju stafrófi $A$ sem inniheldur minnst tvö tákn og skilar röð af vísum $(i_k)_{1 \le k \le K}$ þar sem $K \ge 1$ og $1 \le i_k \le N$ fyrir öll $k$ svo að

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