著者

上原 隆平

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-131, no.11, pp.1-3, 2010-09-15

---

近年,計算幾何学の一部で 「計算折紙」 とよばれる分野が注目を集めている.その分野では,ある意味で折紙を計算のプラットフォームとみなしている.こうしたプラットフォーム上で,計算量理論的に手におえない困難な問題や,多項式時間で解ける問題がいくつか知られている.さてチューリング機械といった標準的な計算モデルにとって,決定不能な問題の存在は,その計算モデルの計算能力の高さを逆説的に示しているといえよう.それならば,計算折紙モデルでは決定不能な問題が存在するだろうか?本稿では,この疑問に対する解答を与える.具体的には,計算折紙モデルのごく自然な決定問題が決定不能であることを示す.