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\leq k\leq K}$ þar sem $K\geq 1$ s $1\leq i_{k}\leq N$ fyrir öll $k$ svo að

$\alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.$

Tilvísanir

+