Samræmingarverkefni Posts

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita

Samræmingarverkefni Posts[1] er óleysanlegt ákvörðunarvandamál sem Emil Post lagði til árið 1946. Vandamálið gengur út á að taka tvo endanlega orðalista og úr einhverju stafrófi sem inniheldur minnst tvö tákn og skilar röð af vísum þar sem og fyrir öll svo að

Tilvísanir[breyta | breyta frumkóða]

  1. Algorithms, Logic, and Complexity Icelandic-english course dictionary