„Samræmingarverkefni Posts“: Munur á milli breytinga

Efni eytt Efni bætt við

Innfellt

Útgáfa síðunnar 12. október 2012 kl. 02:20

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 $\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

↑ Algorithms, Logic, and Complexity Icelandic-english course dictionary

[1] Algorithms, Logic, and Complexity Icelandic-english course dictionary

[1]

@@ Lína 1: / Lína 1: @@
+'''Samræmingarverkefni Posts'''<ref>[https://notendur.hi.is/hh/kennsla/rrr/h06/ordalisti.html Algorithms, Logic, and Complexity] Icelandic-english course dictionary</ref> er [[óleysanlegt vandamál|óleysanlegt]] [[ákvörðunarvandamál]] sem [[Emil Post]] lagði til árið [[1946]]. Vandamálið gengur út á að taka tvo endanlega orðalista <math>\alpha_{1}, \ldots, \alpha_{N}</math> og <math>\beta_{1}, \ldots, \beta_{N}</math> úr einhverju stafrófi <math>A</math> sem inniheldur minnst tvö tákn og skilar röð af [[vísir|vísum]] <math>(i_k)_{1 \le k \le K}</math> þar sem <math>K \ge 1</math> s <math> 1 \le i_k \le N</math> fyrir öll <math>k</math> svo að
-'''Samræmingarverkefni Posts'''<ref>[https://notendur.hi.is/hh/kennsla/rrr/h06/ordalisti.html
-Algorithms, Logic, and Complexity] Icelandic-english course dictionary</ref> er [[óleysanlegt vandamál|óleysanlegt]] [[ákvörðunarvandamál]] sem [[Emil Post]] lagði til árið [[1946]]. Vandamálið gengur út á að taka tvo endanlega orðalista <math>\alpha_{1}, \ldots, \alpha_{N}</math> og <math>\beta_{1}, \ldots, \beta_{N}</math> úr einhverju stafrófi <math>A</math> sem inniheldur minnst tvö tákn og skilar röð af [[vísir|vísum]] <math>(i_k)_{1 \le k \le K}</math> þar sem <math>K \ge 1</math> s <math> 1 \le i_k \le N</math> fyrir öll <math>k</math> svo að
 : <math>\alpha_{i_1} \ldots \alpha_{i_K} = \beta_{i_1} \ldots \beta_{i_K}.</math>
@@ Lína 13: / Lína 12: @@
 [[en:Post correspondence problem]]
 [[es:Problema de correspondencia de Post]]
-[[he:בעיית ההתאמה של פוסט]]+
+[[he:בעיית ההתאמה של פוסט]]
 [[nl:Correspondentieprobleem van Post]]
 [[pl:Problem odpowiedniości Posta]]