非決定性プログラミング

非決定性プログラミング言語は、プログラム内の特定のポイント(「選択ポイント」と呼ばれる) で、プログラム フローのさまざまな選択肢を指定できる言語です。if -then ステートメントとは異なり、これらの選択肢の選択方法はプログラマーによって直接指定されません。プログラムは、すべての選択ポイントに適用される一般的な方法を使用して、実行時に選択肢を決定する必要があります。プログラマーは限られた数の選択肢を指定しますが、プログラムは後でそれらの中から選択する必要があります (「選択」は、実際には非決定性演算子の一般的な名前です)。選択ポイントの階層が形成され、高レベルの選択肢が、その中に低レベルの選択肢を含む分岐につながる場合があります。

選択方法の 1 つは、バックトラッキングシステム (Amb ^[1]やPrologのユニフィケーションなど) に具体化されています。バックトラッキング システムでは、一部の選択肢が「失敗」し、プログラムがバックトラックして他の選択肢を試すことがあります。特定の選択ポイントですべての選択肢が失敗すると、分岐全体が失敗し、プログラムはさらにバックトラックして、古い選択ポイントに戻ります。1 つの複雑な点は、選択は暫定的で再実行される可能性があるため、最終的に失敗した分岐を部分的に実行することによって発生した副作用を元に戻すことで、システムが古いプログラム状態を復元できる必要があることです。

もう一つの選択方法は、Alispなどのシステムに具体化されている強化学習です。 ^[2]このようなシステムでは、バックトラッキングではなく、システムは成功の尺度を追跡し、どの選択が成功につながることが多いか、どのような状況で成功するかを学習します（内部プログラム状態と環境入力の両方が選択に影響を与える可能性があります）。これらのシステムは、バックトラッキングが動的環境で実行されたアクションを元に戻す試みを伴うロボット工学やその他の分野への応用に適していますが、これは困難または非現実的な場合があります。

• 非決定論（曖昧さ回避）
• カテゴリ: 非決定性プログラミング言語
• 天使の非決定論
• 悪魔的な非決定論