Undecidable Traveler

0

No comments posted yet

Comments

Slide 1

決定不能な 旅 人 k.inaba 二○一○年一○月 決定不能の会 Reading: F. Berger & R. Klein, A Traveller’s Problem Symposium on Computational Geometry, 2010 http://dx.doi.org.10.1145/1810959.1810991

Slide 2

This slide is a material for the “Kettei-Funo no Kai (Undecidable Party)”, a study-group on undecidability held in Tokyo. written by Kazuhiro Inaba ( http://www.kmonos.net ), under my own understanding of the paper. So, it may include many mistakes! For your correct understanding, please consult the original paper and/or the authors’ slide.

Slide 3

今日の決定不能問題 S 地点から G 地点に行けますか? (乗り物に乗って) G S

Slide 4

もう少し厳密に 入力 考える空間の次元 d スタートの座標 s ゴールの座標 g 有限個 (n 個) の “乗り物” 速度ベクトル v1 … vn 形と、時刻 0 での位置 C1 … Cn (convex polyhedron) 出力 時刻 T と連続関数 f : [0,T] → Rd を巧く選んで f(0)=s, f(t)は常にどれかの乗り物の上, f(T)=g とできるや否や???? Note: 論文ではさらに  ・ ゴールが速度ベクトル vgで動く  ・ 旅人は相対速度 vw で歩ける ケースまで一般化

Slide 5

convex polyhedron 凸な多角形・多面体・超多面体 無限遠まで延びてるものも含む 縮退してるものも含む

Slide 6

怪しい例 無限回 乗り換え G S

Slide 7

定理 Traveler’s Problem は 8次元以上で、決定不能

Slide 8

証明の旅路 チューリングマシンの停止問題は決定不能 ゆえに 文字列書換系の到達可能性は決定不能 ゆえに Postの対応問題 (PCP) は決定不能 ゆえに 反復関数系 (IFS) の到達可能性は決定不能 ゆえに Traveler’s Problem は決定不能

Slide 9

チューリングマシンの停止問題は決定不能 ゆえに 文字列書換系の到達可能性は決定不能 ゆえに Postの対応問題 (PCP) は決定不能 ここまでの詳細は、第一回の資料をどうぞ http://www.kmonos.net/pub/Presen/PCP.pdf 以下、簡単なおさらい

Slide 10

チューリングマシン Turing さんの考えたマシン Q×{0,1}  Q×{0,1}×{左,右,停止} の表 1 0 0 1 1 0 1 右 1 1 停止 ・・・ 1 0 1 1 1 … … … … 1 0 1 1 1 … … 停

Slide 11

停止問題 入力: チューリングマシン テープの初期状態 出力: 「停止」に行くなら yes / 永遠に動くなら no 決定不能: ↑を計算できるチューリングマシンは存在しない 証明 あったとする h(machine, tape) と 「f(x) = if h(x,x) then 無限ループ else 停止」もTMで書ける f(f) の結果が矛盾する

Slide 12

文字列書き換え系 文字列を文字列に書換える規則の集まり Semi Thue-System (cf. Turing の 0 型文法) 書き換えの例 abcabcabczz  abcabcdefzz  abcabcdefeaglkazz  abcabcxaaz abc  def f  feaglka defeaglkaz  xaa

Slide 13

到達可能性 入力:書き換え系と文字列 s1と文字列 s2 出力:s1 を s2 に書き換えられるか? 決定不能。証明: TMの状態とテープを混ぜると書換系になってる 到達可能性が解けたとすると、” 0011.. ”を が解けちゃうので停止問題が解けちゃって矛盾 0 1 右 1 1 停 ・・・ 0 1 1 停 ・・・ 停

Slide 14

Postの対応問題 (PCP) http://d.hatena.ne.jp/ku-ma-me/20100724/p1 謎の制約のある席決めゲームです。

Slide 15

PCP 入力 文字列のペアの有限リスト ps :: [(String, String)] 出力 自然数のリスト idx :: [Int] で concatMap (λi. fst (ps !! i)) idx = concatMap (λi. snd (ps !! i)) idx な物はあるか? “男女”を左寄せに寄せて全員対面できるか? (さっきのゲームでは “男-女” or “女-男” で 対面させましたが、今回の定義どおりだと、 “男-男” と “女-女” が常に並ぶようにするゲーム になります。難易度はどっちでも同じです。)

Slide 16

PCP 決定不能。証明 PCP が解けるとする 書き換え系の到達可能性問題 文字列 s1 と s2 と書き換え規則 P を以下のようにPCPに作り替え (実際はもうちょい工夫が必要) abc  def f  feaglka defeaglkaz xaa (始, 始次s1 ) (次s2終, 終 ) ( x, x ) for all x ∈ {次}∪Δ ( α, β ) for all α→β ∈ P これが解ける if and only if 到達可能問題が解ける

Slide 17

チューリングマシンの停止問題は決定不能 ゆえに 文字列書換系の到達可能性は決定不能 ゆえに Postの対応問題 (PCP) は決定不能 ゆえに 反復関数系 (IFS) の到達可能性は決定不能 ゆえに Traveler’s Problem は決定不能 次の詳細は、第四回の資料(の前半)に近い http://www.kmonos.net/pub/Presen/QFA.pdf

Slide 18

反復関数系 (IFS) 一点から始めて、 (線形)関数を適用 しまくって作れる 図形 ※ pictures are from Wikipedia

Slide 19

反復関数系 (IFS) 一点から始めて、 (線形)関数を適用 しまくって作れる 図形 f(z) = (1+i)/2*z g(z) = 1 - (1-i)/2*z f(z) = z/2 g(z) = z/2 + (1+√3i)/4 h(z) = z/2 + 1/2

Slide 20

IFS到達可能性 On undecidability bounds for matrix decision problems, TCS v.391 [Bell & Potapov, 2008] 入力 アフィン変換(線形変換+平行移動) のみからなる反復関数系 始点 p 点 q q は、p から始めて作ったIFS図形に入る?

Slide 21

IFS到達可能性 決定不能。証明: と の二文字しかない文字列のPCP問題を 考える 文字を行列にエンコード encode( ) = (1 1) encode( )-1 = (1 -0.5) (0 2) (0 0.5) encode( ) = (1 2) encode( )-1 = (1 -1) (0 2) (0 0.5) このエンコードの重要な特徴: 「文字列として結合した物が等しい if and only if 行列として掛け算した物が等しい」

Slide 22

「文字列のペア」を行列演算にエンコード encode( ( , ) ) = λX. encode( ) enc( )enc( ) X enc( )-1enc( )-1 この演算は行列 (1 x) を (1 ?) の形に移す (0 y) (0 ?)

Slide 23

論文曰く

Slide 24

PCP vs IFS まだペアを 並べてない状態    を左寄せに     並べる うまくマッチする PCPに解が存在 (1 0) (0 1) e( )e( )e( ) (1 0) e( )-1 e( )-1 (0 1) e( ほげ ) (1 0) e(ほげ)-1 (0 1) の形 (0,1)から(0,1)にIFS到達可能

Slide 25

チューリングマシンの停止問題は決定不能 ゆえに 文字列書換系の到達可能性は決定不能 ゆえに Postの対応問題 (PCP) は決定不能 ゆえに 反復関数系 (IFS) の到達可能性は決定不能 ゆえに Traveler’s Problem は決定不能

Slide 26

Traveler’s Problem S 地点から G 地点に行けますか? (乗り物に乗って) G S

Slide 27

決定不能 証明: 「乗り物」をうまく組み合わせて アフィン変換を表現できる 例として、 f(x) = ax (定数倍)の実現

Slide 28

x軸上の点 (x,0,0,0) を (ax,0,0,0) に動かす ピタゴラ装置 x軸 S

Slide 29

「xy平面全体」がy軸方向に適当な速度で動く S x軸 y軸

Slide 30

すると、直線 y=ax の 上にz軸方向に 流れる壁が! S y=ax

Slide 31

登ると z=1平面が 左に流れてます S y=ax

Slide 32

(0, as, 1) に到着 そして… S y=ax

Slide 33

四次元の世界へ! 平面 {(0,y,1,w) | y,w∈R} がw軸正方向に流れてる S y=ax → この線に 乗った人は w軸方向に 動ける

Slide 34

(0, as, 1, 0) から (0, as, 1, 1) まで四次元時空を 移動 w=1の世界

Slide 35

w=1 の世界では z=1平面は右下(速度ベクトル (1,-1))に流れてる (0, as, 1, 1) から (as, 0, 1, 1) へ

Slide 36

w=1 の世界では y=0 平面は下に流れている (0, as, 1, 1) から (as, 0, 0, 1) へ

Slide 37

実は x 軸も、4次元を移動できる乗り物 w軸負方向に動く (as, 0, 0, 1) から (as, 0, 0, 0) へ S (s, 0, 0, 0) から (as, 0, 0, 0) に移動!

Slide 38

決定不能性の証明 今の例の場合 「(s,0,0,0) から (g,0,0,0) に有限時間で移動可能」と 「s から g まで f(x)=ax を有限回適用して到達可能」 が同値 同様にして頑張ると、 任意のアフィン変換の IFS が実現可能 多くとも8次元使うと(決定不能なPCPを表現するのに必要なアフィン変換IFS)の表現に必要な「乗り物」を用意できるらしい Traveller’s Problem が解けちゃうと IFSの到達可能性も解けちゃう。ゆえに決定不能

Slide 39

まとめ PCP → IFS PCPに出てくる「文字」を 逆行列を掛けない限りは 1 に戻らない 「キリの悪い」回転行列にエンコード IFS  Traveler 「移動する乗り物」というよりも、 「一定速度で流れ続けてるベルトコンベアー  みたいな平面」を大量に配置して アフィン変換をエンコード

Slide 40

考えてみたい もっと「乗り物」っぽい設定で 決定不能性は示せるでしょうか? 「平面全体」のような 無限に広がるオブジェクトなしで

Summary: This slide was prepared for http://pira.jp/undecidable/ study group. The contents are based on MY OWN understanding on the referred paper (hence may contain a lot of mistakes). For correct information, please read the original paper!

URL: