プログラミング == プランニング問題
| プログラム | プランニング |
|---|---|
| 入力 | 初期状態 $s_0= \{ p_0, p_1\ldots \} $ |
| オブジェクト | 命題 $p$ |
| X86 命令セット | アクションスキーマ $A= \{ a_0, a_1, \ldots \}$ |
| X86 命令 | アクション $ a : s_i \mapsto s_j $ |
| レジスタ・メモリ | 状態 $s = \{ p_0, p_1\ldots \} $ |
| 出力 | ゴール条件 $s^* =\{ p_0, p_1\ldots \} $ |
| プログラム | プラン $P=(a_0, a_1, \ldots)$ |
前提条件・追加効果・削除効果
アクションには前提条件・追加効果・削除効果がある。
Destination=5, Source=7
のときに ADD 命令
Destination = Destination + Source;
を実行すると、
Destination=12, Source=7
となる。これを命題論理で表すと、
(when (and (is destination five)
(is source seven))
(add (is destination twelve))
(delete (is destination five)))
と表現できる。
こういった命令=アクションを組み合わせて目的状態を達成するプランを探索する問題のことを、古典プランニング問題(ないしSTRIPSプランニング)と呼ぶ。
プランニングの計算複雑性クラスはPSPACE-Hard.
削除効果がない = NP-Hard
ここで、プランニング問題のうち、削除効果 (delete effect) がないが無いものを非削除(delete free)プランニング問題と呼ぶ。delete-free プランニング問題はナップサック問題と相互に変換でき、ナップサック問題はNP完全なので、delete-free プランニングはNP完全。
PSPACE-Hard から NP-Complete に 計算複雑性クラスが下がる、すなわち、delete-free プランニング は古典プランニングより簡単。
破壊代入がない = 削除効果がない
プログラムを書く作業は、目的を達成するプログラムを探索することだから、本質的にプランニングと同じ。ここで、破壊代入がない == 操作によってfalseになる命題がないということ。従って、破壊的代入のない世界ではプログラミングがより簡単になる。