undecidable problems

とりあえず10個かー.

授業で証明読んだもの

• 停止問題とそのヴァリアント
• ビジービーバー
• ライスの定理
• L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2)
• PCP (Postの方)

証明知らないもの

• ヒルベルトの第10問題
• ワンのタイル

読みたいもの

DBLPから見繕う.

• 群同型
  • en.wikipediaにあった.
  • 環同型は判定可能でNP∩coAM (Kayal and Saxena, CCC 2005). さらに, グラフ同型問題の困難性は環同型問題の困難性以下.
• コラッツ‐角谷予想の決定不能性
  • Eero Lehtonen “Two undecidable variants of Collatz's problems” (TCS Vol.407, 1-3, 6, 2008, pp. 596--600)
  • http://dx.doi.org/10.1016/j.tcs.2008.08.029
• 文脈自由言語関係
  • Henning Bordihn “Context-freeness of the power of context-free languages is undecidable” (TCS Vol.314, 3, 10, 2004, pp.445--449)
  • http://dx.doi.org/10.1016/j.tcs.2003.08.005
  • いやこれは微妙か?
• 正規言語でもあるの?
  • Juhani Karhumäki, Yael Maon: A Simple Undecidable Problem: Existential Agreement of Inverses of Two Morphisms on a Regular Language. J. Comput. Syst. Sci. (JCSS) 32(3):315-322 (1986)
• 項書き換え
  • Max Dauchet: Termination of Rewriting is Undecidable in the One-Rule Case. MFCS 1988:262-270
  • ルールが1つらしいよ
• π計算
  • Vasco T. Vasconcelos and António Ravara “Communication errors in the π-calculus are undecidable ” (IPL Vol.71, 5-6, 30, pp.229--233)
  • http://dx.doi.org/10.1016/S0020-0190(99)00109-X
  • π計算の勉強がてら
• 真理値表
  • Jan Kalicki: An Undecidable Problem in the Algebra of Truth-Tables. J. Symb. Log. (JSYML) 19(3):172-176 (1954)
• 組合わせ系
  • Kevin J. Compton: An Undecidable Problem in Finite Combinatorics. J. Symb. Log. (JSYML) 49(3):842-850 (1984)
  • Stefan A. Burr: Some undecidable problems involving the edge-coloring and vertex-coloring of graphs. Discrete Mathematics (DM) 50:171-177 (1984)