問題・個例

計算機科学の発展は、問題の定義とその解法の探索から始まる。問題は本質的に、解を求めるべき抽象的な課題であり、個例はその具体的な実践に他ならない。この関係は、アラン・チューリングの業績に代表されるように、計算の理論を構築する基礎となった。

チューリングは $1936$ 年に「計算可能性」に関する論文¹を発表し、問題を形式的に定義する重要性を強調した。ここで彼は、任意の計算可能な問題を解くための「チューリング機械」という抽象的なモデルを提案した。このモデルは、あらゆる問題の解決に用いることができ、計算の枠組みを整える重要な役割を果たした。

問題 (problem) は通常、以下のように定義される：

\[\text{P}{\scriptsize\text{ROBLEM}}=(I,O,f)\]

ここで、$I$ は入力の集合、$O$ は出力の集合、$f: I \to O$ は入力から出力への対応を示す函数である。個例 (instance) は、この問題における特定の入力 $i~(\forall i\in I)$ であり、実際の解決に必要な具体的な条件を持つ。

例えば、十進法で整数が与えられたときに、それが素数であるか答えよ、というのは一つの問題である。個々の $5417$ のごとき 整数は「問題」ではなく、個例と呼ぶ。問題を解いたというには、すべての個例に対して正しく答えなければならない。

このように、問題と個例は密接に関連し、計算機科学の枠組みの中で、理論的な構造を形成する。個例は、問題を実現可能な形に落とし込み、実際の計算においてどのように問題が解決されるかを示す鍵となる。

1. Turing, A. M. “On Computable Numbers, with an Application to the Entscheidungsproblem”. (1936) ↩︎