読者です 読者をやめる 読者になる 読者になる

undecidable problems

とりあえず10個かー.

授業で証明読んだもの

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

証明知らないもの

読みたいもの

DBLPから見繕う.

  • 群同型
    • en.wikipediaにあった.
    • 環同型は判定可能でNP∩coAM (Kayal and Saxena, CCC 2005). さらに, グラフ同型問題の困難性は環同型問題の困難性以下.
  • コラッツ‐角谷予想の決定不能性
  • 文脈自由言語関係
  • 正規言語でもあるの?
    • 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つらしいよ
  • π計算
  • 真理値表
    • 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)