Samræmingarverkefni Posts

Úr Wikipediu, frjálsa alfræðiritinu

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[óvirkur tengill] Icelandic-english course dictionary