決定不能性・決定可能性に関する問題について勉強する会です。
毎回テーマを定めて、決定不能性や決定可能性に関する問題についてメンバーの一人が発表します。 発表しないメンバーも、その会のテーマについて予習をすることが求められます。 みんなで決定不能になりましょう。
証明自体は単純なので、紹介は1時間もとらないと思います。 ただ、論文の問題設定自体がちょっとフリーダムすぎる気がしていて、 自分の趣味としてはちょっと制約を加えたいのですが、 加えると少なくともそのままでは決定不能性の証明が成り立たなくなるため、 時間があったら「みんなでどうなるか考えてみようタイム」を設けて考えてみたいところです。 ※ 具体的には、「物体はすべて有界であるとする」という制約を入れるとどうなるかなーと
有楽町線の護国寺駅の、正しい出口から出れば徒歩1分くらいです。
参考文献:
(主に) An Introduction to the Theory of Computation 4.7節
http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html
(参考として原論文)
Emil L. Post (1946). "A variant of a recursively unsolvable problem".
Bull. Amer. Math. Soc 52.
http://www.ams.org/bull/1946-52-04/S0002-9904-1946-08555-9/S0002-9904-1946-08555-9.pdf
参考文献は Yuri V. Matiyasevich "Hilbert's Tenth Problem" (MIT Press 1993) のCh.1-5です。 以下の大学図書館には所蔵されています。 http://webcat.nii.ac.jp/cgi-bin/shsproc?id=BA21148397
Google グループにて自己紹介を添えて参加申し込みをしてください。
そろそろ priority argument を始めようぜという話が出ています.