決定不能の会

決定不能性・決定可能性に関する問題について勉強する会です。

内容

毎回テーマを定めて、決定不能性や決定可能性に関する問題についてメンバーの一人が発表します。 発表しないメンバーも、その会のテーマについて予習をすることが求められます。 みんなで決定不能になりましょう。

日程

第8回

• 日時: 2010/10/31 13:30-17:00
• 場所: 本郷．理学部7号館, USTREAM
• 内容予測
• (kinaba) これが気になっています。 http://portal.acm.org/citation.cfm?id=1810991 ８次元空間の川をどんぶらこどんぶらこと流れている超多面体の上を 渡って向こう岸に渡れるかどうかは決定不能だそうです。 スライド

  証明自体は単純なので、紹介は1時間もとらないと思います。
  
  ただ、論文の問題設定自体がちょっとフリーダムすぎる気がしていて、
  自分の趣味としてはちょっと制約を加えたいのですが、
  加えると少なくともそのままでは決定不能性の証明が成り立たなくなるため、
  時間があったら「みんなでどうなるか考えてみようタイム」を設けて考えてみたいところです。
  
  ※ 具体的には、「物体はすべて有界であるとする」という制約を入れるとどうなるかなーと
  

• (kanoyk) ヒルベルト第十問題のべき乗のところ
• (pira) 中間次数の話 (予習いらない) スライド

第7回

• 日時：2010/05/29 15:00-17:30
• 場所：本郷．理学部7号館214
• 内容
• お題：Domino problemの決定不能性
• 文献：Berger, Robert (1966), "The undecidability of the Domino Problem", Memoirs of the American Mathematical Society 66.
• スライド (間違い多し/このままだとチューリングマシンが動きません)

第6回

• 2010/03/20
• 一般コラッツ予想とかFRACTRAN (xagawa)

第5回

• 2010/02/20
• S5×S5×S5 (pira)

第4回

• 2010/01/16
• Riceの定理

第3回

• 2009/12/19
• 群のword problem (pira)
• PCPを使ってIO付オートマトンの[to be filled] (ksuenaga)

第2回

• 日時：2009/11/22 13:00-18:00
• 場所：アカデミー音羽 会議室A

有楽町線の護国寺駅の、正しい出口から出れば徒歩1分くらいです。

• 内容
• ヒルベルト第10問題 (xagawa) （文献は前回と同じ）
• Word problem (pira) （文献は TBA）

第1回

• 日時：2009/10/10 13:00-18:00
• 場所：東京大学理学部7号館214教室
• 内容
• ポストの対応問題 (kinaba)

  参考文献:
   (主に) 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
  

• ヒルベルト第10問題 (xagawa)

  参考文献は
  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 を始めようぜという話が出ています．