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,\dots ,{\alpha }_N$ og ${\beta }_1,\dots ,{\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}\dots {\alpha }_{i_K}={\beta }_{i_1}\dots {\beta }_{i_K}.$