[1] Emil L. Post, "A Variant of a Recursively Unsolvable Problem"
    Bulletin of the American Mathematical Society, 1946, 52, 264-269

　　定番問題１。PCP。今まで証明を調べたことがなかったので。


[2] ヒルベルトの第10問題

　　定番問題２。これも今まで証明を調べたことがなかったので。


[3] Stuart A. Kurtz & Janos Simon "The Undecidability of the Generalized Collatz Problem"
     Theory and Applications of Models of Computation, 2007, 542-553

　　定番問題３？ Collatz予想は、一般化するとundecidableなことが証明できてるらしい。


[3] Sheila Greibach, "A Note on Undecidable Properties of Formal Languages"
    Mathematical Systems Theory, 1968, 2, 1-6

　　昔流し読みしてちゃんと証明追ってないものその１。
　　なんとかんとかんとかとあれとそれに関して閉じてる言語族に関して
　　それとこれとどれのような性質は決定不能だよみたいな定理が色々。


[4] Zoltán Fülöp & Pál Gyenizse, "On Injectivity of Deterministic Top-Down Tree Transducers"
    Information Processing Letters, 1993, 48, 183-188

　　昔流し読みしてちゃんと証明追ってないものその２。
　　１ステートのツリートランスデューサーがinjectiveかどうかはundecidable。


[5] N Immerman et al., "The Boundary Between Decidability and Undecidability for Transitive-Closure Logics"
    Computer Science Logic, 2004, 160-174

　　仕事で必要。
　　ツリーとかに構造を制限したら一階述語論理のsatisfiabilityはdecidableになるけど、
　　それにtransitive closureを入れるとダメ。どのくらいの強さのtcを入れるとundecidableになるのか。


[7] Jakub Kozik, "Undecidable Problems Concerning Densities of Languages"
    Computational Logic and Applications (CLA), 2005

　　趣味１。
　　極限 lim_{n->inf} #{x in L | |x|=n} / #\Sigma^n が定義されるかどうかはCFLについては決定不能。


[8] V. D. Blondel et al., "Decidable and Undecidable Problems about Quantum Automata",
    SIAM Journal on Computing, 2005, 34, 1464-1473 

　　趣味２。
　　（それが何かすら知らないけど）量子オートマトンのemptinessはundecidable。
　　確率オートマトンとは違うらしいよ。量子オートマトンとやらの勉強をかねる。


[9] Ralph Loader, "Higher Order β Matching is Undecidable",
    Logic Journal of IGPL, 2003, 11, 51-68

　　高階βマッチング（ユニフィケーションの片方にだけ変数があるもの。"β-equivalence
　　のみ考慮"）は undecidable。βηマッチングは最近の結果によると decidable らしい。


[10] Jeffrey Kegler, "Perl Cannot Be Parsed: A Formal Proof"
　　http://www.perlmonks.org/?node_id=663393

　　ネタ。Perlの構文解析は決定不能。