ポストの対応問題
こういう問題
まず文字列の組のリストが与えられる
$ (\sigma_1,\tau_1),(\sigma_2,\tau_2),\cdots,(\sigma_n,\tau_n)
一つ一つの$ \sigma_mや$ \tau_mは、文字列
具体例は後述
この、組のリストに対して
$ \sigma_{i_1},\sigma_{i_2},\cdots,\sigma_{i_k}=\tau_{i_1},\tau_{i_2},\cdots,\tau_{i_k}
となるような添字の列$ (i_1,i_2,\cdots,i_k)が存在するかどうか、を答える問題
ただし、$ k\ge 1であり、重複はあってもよい
入力が組である必要はそんなくねmrsekut.icon
例
table:例
i 1 2 3
σi a abaaa ab
τi aaa ab b
この場合、添字を$ 2,1,1,3と並べればイケる
つまり、$ \sigma_2\sigma_1\sigma_1\sigma_3=\tau_2\tau_1\tau_1\tau_3=abaaaaaabとなり一致する
なので、このような組$ (\sigma_1,\tau_1),(\sigma_2,\tau_2),(\sigma_3,\tau_3)が入力として与えられた場合は、
Yesを返却する
つまり、以下のようなチューリングマシン$ Pは存在しない
チューリングマシン$ Pは、
文字列の組の任意のリスト$ (\sigma_1,\tau_1),(\sigma_2,\tau_2),(\sigma_3,\tau_3)を入力として与えた時、
必ず有限ステップでポストの対応問題の判定(Yes or No)を返却して停止する
このようなチューリングマシンが存在すると仮定すると、停止性問題が解けてしまう、というようにして証明する