様々な決定不能問題とその証明を掲載しています.決定不能性の証明に主眼を置いているため,決定可能であることの証明はたいていの場合は概略に留めてあります.計算量に関する結果はたいてい証明しません.

初めての方は一番上の「Turing機械の定義と停止問題」から読むことをお勧めします.それ以降はおおよそどの順番で読んでも大丈夫です.

前提知識としては,集合と写像に関する基本的な知識があれば大丈夫なはずです(もちろん問題によって必要な前提知識は異なります).細かいことに囚われず,大らかな気持ちで読んでいただければと思います.

決定不能問題のための基礎知識 (Prerequisites for Undecidable Problems)

Turing機械の定義と停止問題 (Turing Machine and the Halting Problem)

2018/01/01, 11 pages PDF


停止問題 (Halting Problem) Undecidable

Input: Turing機械$M$と文字列$w$

Question: $M$は$w$を受理するか?

停止問題の変種 (variants of Halting Problem) Undecidable

Input: Turing機械$M$

Question: $M$は空文字列$\varepsilon$を受理するか?

Input: Turing機械$M$

Question: $M$に受理されるような入力文字列は存在するか?

Input: Turing機械$M$と文字列$w$

Question: 入力文字列$w$に対して$M$は停止するか?

様々な計算モデル (Various Models of Computation)

離散数学・組合せ論・パズルにおける問題 (Problems in Discrete Mathematics, Combinatorics and Puzzles)

Postの対応問題 (Post Correspondence Problem) NEW!

2018/02/01, 10 pages PDF


Postの対応問題 (Post Correspondence Problem; PCP) Undecidable

Input: 文字列の組の有限集合$\{(u_1,v_1),(u_2,v_2),\dotsc,(u_n,v_n)\}$

Question: $u_{i_1}u_{i_2}\dotsm u_{i_k}=v_{i_1}v_{i_2}\dotsm v_{i_k}$となる添字の有限列$(i_1,i_2,\dotsc,i_k)\,(k\geq1)$は存在するか?

Modified PCP Undecidable

Input: 文字列の組の有限集合$\{(u_1,v_1),(u_2,v_2),\dotsc,(u_n,v_n)\}$

Question: $u_1u_{i_1}u_{i_2}\dotsm u_{i_k}=v_1v_{i_1}v_{i_2}\dotsm v_{i_k}$となる添字の有限列$(i_1,i_2,\dotsc,i_k)\,(k\geq0)$は存在するか?

Generalized PCP Undecidable
Marked PCP Decidable
Circular PCP Undecidable
$n$-permutation PCP Undecidable
Identity Correspondence Problem (ICP) Undecidable

Wangのタイル貼り問題 (Wang Tiling Problem, Domino Problem)

2018/03/01, 0 pages PDF


Wangのタイル貼り問題 (Wang Tiling Problem, Domino Problem) Undecidable

Input: タイル(4つの辺それぞれに色が塗られた単位正方形)の有限集合$T$

Question: 隣接する辺の色が等しくなるように$T$の元を並べて全平面を充填できるか? (ただし,同じ元を何回用いてもよいが,回転・反転は禁止とする)

制約付きのWangのタイル貼り問題 (Wang Tiling Problem with Restricted Origin) Undecidable

Input: タイルの有限集合$T$とその元$t\in T$

Question: まず原点に$t$を置き,その後隣接する辺の色が等しくなるように$T$の元を並べて全平面を充填できるか? (ただし,同じ元を何回用いてもよいが,回転・反転は禁止とする)

行列・半群に関する問題 (Problems Related to Matrices and Semigroups)

Matrix Mortality Problem

2018/mm/dd, 0 pages PDF


Matrix Mortality Problem Undecidable($n\geq 3$),Open($n=2$)

Input: 整数成分の$n$次正方行列の有限集合$F\subseteq\mathrm{M}_n(\mathbb{Z})$

Question: $F$が生成する乗法半群$\langle F\rangle$は零行列を含むか? (言い換えると,$F$の元の積によって零行列が作れるか?)

Matrix Identity Problem

2018/mm/dd, 0 pages PDF


Matrix Identity Problem Undecidable($n\geq 4$),Decidable($n\leq 2$),Open($n=3$)

Input: 整数成分の$n$次正方行列の有限集合$F\subseteq\mathrm{M}_n(\mathbb{Z})$

Question: $F$が生成する乗法半群$\langle F\rangle$は単位行列を含むか? (言い換えると,$F$の元の積によって単位行列が作れるか?)

形式言語論における問題 (Problems in Formal Language Theory)

論理学における問題 (Problems in Logic)

代数学における問題 (Problems in Algebra)

数論における問題 (Problems in Number Theory)

解析学における問題 (Problems in Analysis)

計算可能性理論における話題 (Topics in Computability Theory)

2018/01/01 公開
トップに戻る