Decision problem

決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合 { 0 , 1 } ∗ {\displaystyle \{0,1\}^{*}} 、あるいは { 0 , 1 } ∗ {\displaystyle

theory with a trans-exponential (rapid growth) function? Lachlan's decision problem Does a finitely presented homogeneous structure for a finite relational

McCloskey, 1991) 政治的意思決定 (Political decision making) (Voss, Wolfe, Lawrence & Engle, 1991) 管理の問題解決 (Managerial problem solving) (Wagner, 1991) 弁護士の推論 (Lawyers'

1976年にチューリング賞を授与された。受賞理由は次の通り。 「彼らの共作論文 "Finite Automata and Their Decision Problem"（有限状態機械とその決定性問題）に対して。その論文は非決定性マシンという非常に貴重な概念を導入した。この古典的論文はこの分野の後続の

年まで講師として勤務。1959年にはプリンストンでの同僚マイケル・ラビンと共同で Finite Automata and Their Decision Problem という論文を発表し、非決定性有限オートマトンのアイデアを明らかにした。これが計算複雑性理論の基礎概念となったことから、ラビンと共にチューリング賞を受賞した。