決定不能問題ギャラリー Gallery of Undecidable Problems

決定不能問題(undecidable problem)というのは，簡単に言えばコンピューターに解けない問題のことです．

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

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

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

目次 Table of Contents

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

Turing機械の定義と停止問題

Turing Machine and the Halting Problem

PDFを読む
(289KiB, 11 pages)
停止問題 (Halting Problem) Undecidable
Input
Turing機械$M$と文字列$w$
Question
$M$は$w$を受理するか？
停止問題の変種1 (Variant of Halting Problem 1) Undecidable
Input
Turing機械$M$
Question
$M$は空文字$\varepsilon$を受理するか？
停止問題の変種2 (Variant of Halting Problem 2) Undecidable
Input
Turing機械$M$
Question
$M$に受理されるような入力文字列は存在するか？
停止問題の変種3 (Variant of Halting Problem 3) Undecidable
Input
Turing機械$M$と文字列$w$
Question
入力文字列$w$に対して$M$は停止するか？
2018/01/01

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

Turing機械の変種

Variants of Turing Machine

PDFを読む
(271KiB, 13 pages)
2018/05/20

再帰的関数

Recursive Function

PDFを読む
(231KiB, 9 pages)
原始再帰的関数の到達可能性問題 (Reachability Problem for Primitive Recursive Functions) Undecidable
Input
原始再帰的関数$f$と自然数$k$
Question
$f(x)=k$となるような$x$は存在するか？
原始再帰的関数の等価性問題 (Equality Problem for Primitive Recursive Functions) Undecidable
Input
原始再帰的関数$f,g$
Question
全ての$x$に対して$f(x)=g(x)$か？
2018/06/01

カウンター機械(レジスター機械)

Counter Machine (Register Machine)

PDFを読む
(168KiB, 7 pages)
2018/06/06

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

Postの対応問題

Post Correspondence Problem

PDFを読む
(258KiB, 10 pages)
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
2018/02/01

Wangのタイル貼り問題

Wang Tiling Problem

PDFを読む
(384KiB, 18 pages)
Wangのタイル貼り問題 (Wang Tiling Problem) Undecidable
Input
タイル(4つの辺それぞれに色が塗られた単位正方形)の有限集合$T$
Question
隣接する辺の色が等しくなるように$T$の元を並べて全平面を充填できるか？ (ただし，同じ元を何回用いてもよいが，回転・反転は禁止とする)
制約付きのWangのタイル貼り問題 (Wang Tiling Problem with Restricted Origin) Undecidable
Input
タイルの有限集合$T$とその元$t\in T$
Question
まず原点に$t$を置き，その後隣接する辺の色が等しくなるように$T$の元を並べて全平面を充填できるか？ (ただし，同じ元を何回用いてもよいが，回転・反転は禁止とする)
1次元のタイル貼り問題 (1-dimensional Tiling Problem) Decidable
3次元のタイル貼り問題 (3-dimensional Tiling Problem) Undecidable
正六角形のタイル貼り問題 (Hexagonal Tiling Problem) Undecidable
正三角形のタイル貼り問題 (Triangular Tiling Problem) Undecidable
2018/03/01

Polyomino Problem

Polyomino Problem

PDFを読む
(224KiB, 10 pages)
Polyomino Problem Undecidable
Input
ポリオミノ(有限個の単位正方形を辺で貼り合わせてできる平面図形)の有限集合$S$
Question
$S$の元を並べて全平面を充填できるか？ (ただし，同じ元を何回用いてもよく，回転・反転も可)
$k$-Polyomino Problem Undecidable($k\geq5$), Open($k\leq4$)
Input
ポリオミノの$k$元集合$S$
Question
$S$の元を並べて全平面を充填できるか？ (ただし，同じ元を何回用いてもよく，回転・反転も可)
$k$-Polyomino Translation Problem Undecidable($k\geq11$), Decidable($k=1$), Open($2\leq k\leq10$)
Input
ポリオミノの$k$元集合$S$
Question
$S$の元を並べて全平面を充填できるか？ (ただし，同じ元を何回用いてもよいが，回転・反転は禁止とする)
2018/04/01

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

半群の語の問題

Word Problem for Semigroups

PDFを読む
(132KiB, 3 pages)
半群の語の問題 (Word Problem for Semigroups) Undecidable
Input
有限表示半群$S$と語$w_1,w_2$
Question
$S$において$w_1\sim w_2$か？
$S$におけるの語の問題 (Word Problem for $S$) Undecidable
Input
語$w_1,w_2$
Question
$S$において$w_1\sim w_2$か？
2019/05/01

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

半Thue系

Semi-Thue System

PDFを読む
(176KiB, 6 pages)
到達可能性問題 (Accessibility Problem, ACP) Undecidable
Input
半Thue系(文字列の書き換え規則$u\to v$の有限集合) $S$と文字列$w_1,w_2$
Question
$w_1$に$S$の規則を何回か適用して$w_2$を導出できるか？
Thue系の到達可能性問題 (Accessibility Problem for Thue System) Undecidable
Input
Thue系(文字列の対称的な書き換え規則$u\leftrightarrow v$の有限集合) $S$と文字列$w_1,w_2$
Question
$w_1$に$S$の規則を何回か適用して$w_2$を導出できるか？
半Thue系$S,w_0$に関する個別到達可能性問題 (Individual Accessibility Problem for Semi-Thue System $S,w_0$, IAP) Undecidable
Input
文字列$w$
Question
$w$に$S$の規則を何回か適用して$w_0$を導出できるか？
半Thue系$S$に関する共通子孫問題 (Common Descendant Problem for Semi-Thue System $S$, CDP) Undecidable
Input
文字列$w_1,w_2$
Question
$w_1,w_2$のそれぞれに$S$の規則を何回か適用して共通の文字列$w$を導出できるか？
半Thue系$S$に関する停止性問題 (Termination Problem for Semi-Thue System $S$, TP) Undecidable
Input
文字列$w$
Question
$w$に$S$の規則を無限に適用し続けることはできるか？
2018/08/01

文脈自由言語の普遍性判定問題

Universality Problem for Context-Free Languages

PDFを読む
(245KiB, 10 pages)
文脈自由言語の所属判定問題 (Membership Problem for Context-Free Languages) Decidable
Input
文脈自由言語$L$と文字列$w$
Question
$w\in L$か？
文脈自由言語の空性判定問題 (Emptiness Problem for Context-Free Languages) Decidable
Input
文脈自由言語$L$
Question
$L=\emptyset$か？
文脈自由言語の普遍性判定問題 (Universality Problem for Context-Free Languages) Undecidable
Input
文脈自由言語$L$
Question
$L=\Sigma^*$か？ ($L$は文字列全体の集合に一致するか？)
文脈自由言語の等価性判定問題 (Equality Problem for Context-Free Languages) Undecidable
Input
文脈自由言語$L_1,L_2$
Question
$L_1=L_2$か？
文脈自由言語の包含判定問題 (Inclusion Problem for Context-Free Languages) Undecidable
Input
文脈自由言語$L_1,L_2$
Question
$L_1\subseteq L_2$か？
2018/09/03

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

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

Fraction Gameと一般化Collatz問題

Fraction Game and Generalized Collatz Problem

PDFを読む
(162KiB, 6 pages)
Vector Game Undecidable
Input
正整数$d$，非負整数$n$，整数成分の有限個の$d$次元ベクトルのリスト$v_1,v_2,\dotsc,v_k$
Question
$v=(n,0,\dotsc,0)$に対し「$v+v_i$の全て成分が非負になるような最初の$v_i$を$v$に加える」という操作を無限に繰り返すことはできるか？
Fraction Game (Rational Game) Undecidable
Input
正整数$n$，有限個の正の有理数のリスト$q_1,q_2,\dotsc,q_k$
Question
$n$に対し「$q_in$が整数になるような最初の$q_i$を$n$にかける」という操作を無限に繰り返すことはできるか？
一般化Collatz問題 (Generalized Collatz Problem) Undecidable
Input
正整数$m$と有理数$a_0,a_1,\dotsc,a_{m-1},b_0,b_1,\dotsc,b_{m-1}$であって，$n\equiv r\pmod{m}$ならば$a_rn+b_r$が整数になるようなもの
Question
全ての正整数$n$に対し「$n\equiv r\pmod{m}$ならば$a_rn+b_r$を改めて$n$とおく」という操作を繰り返すといずれ$1$に到達するか？
2018/07/04

Hilbertの第10問題

Hilbert's Tenth Problem

PDFを読む
(546KiB, 51 pages)
Hilbertの第10問題 (Hilbert's Tenth Problem) Undecidable
Input
整数係数の多変数多項式$f(x_1,\dotsc,x_n)\in\mathbb{Z}[x_1,x_2,\dotsc]$
Question
Diophantus方程式$f(x_1,\dotsc,x_n)=0$は整数解$(x_1,\dotsc,x_n)\in\mathbb{Z}^n$を持つか？
$\mathbb{N}$に関するHilbertの第10問題 (Hilbert's Tenth Problem for $\mathbb{N}$) Undecidable
Input
整数係数の多変数多項式$f(x_1,\dotsc,x_n)\in\mathbb{Z}[x_1,x_2,\dotsc]$
Question
Diophantus方程式$f(x_1,\dotsc,x_n)=0$は自然数解$(x_1,\dotsc,x_n)\in\mathbb{N}^n$を持つか？
$\mathbb{Q}$に関するHilbertの第10問題 (Hilbert's Tenth Problem for $\mathbb{Q}$) Open
Input
整数係数の多変数多項式$f(x_1,\dotsc,x_n)\in\mathbb{Z}[x_1,x_2,\dotsc]$
Question
Diophantus方程式$f(x_1,\dotsc,x_n)=0$は有理数解$(x_1,\dotsc,x_n)\in\mathbb{Q}^n$を持つか？
2018/12/20

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

幾何学における問題 Problems in Geometry

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

正弦関数を含む式の求根問題

Root-Finding Problem for Expressions with the Sine Function

PDFを読む
(187KiB, 9 pages)
正弦関数を含む式の求根問題 (Root-Finding Problem for Expressions with the Sine Function) Undecidable
Input
変数・定数から四則演算と$\sin$によって組み立てられた式$t(x_1,\dotsc,x_n)$
Question
$t(x_1,\dotsc,x_n)=0$となるような$x_1,\dotsc,x_n\in\mathbb{R}$は存在するか？
正弦関数を含む1変数の式の求根問題 (Root-Finding Problem for Unary Expressions with the Sine Function) Undecidable
Input
変数・定数から四則演算と$\sin$によって組み立てられた式$t(x)$
Question
$t(x)=0$となるような$x\in\mathbb{R}$は存在するか？
2019/01/02

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

2018/01/01 公開