帰納プログラミング
帰納プログラミングは,不完全な形式的仕様からのプログラムやアルゴリズムの学習に関する全てのアプローチを含んでいる.帰納プログラミングシステムへの可能な入力形態としては,訓練入力と対応する出力の組の集合や出力評価関数,意図したプログラムの望ましい挙動の記述,トレースすなわち特定の出力を計算する過程を記述した行動系列,得られるプログラムの計算量を考慮した制約,種々の背景知識が挙げられる.背景知識としては,標準的なデータ型,使用する定義済み関数,データの流れや意図したプログラムを記述するプログラムの概形あるいはテンプレート,解の探索を誘導するヒューリスティクスやその他のバイアスが挙げられる.
帰納プログラミングシステムの出力は,条件分岐やループや再帰構造を含む様々なプログラミング言語や,その他のチューリング完全な表現言語の形態を取り得る.
多くの応用において,出力プログラムは例や不完全な仕様と合致することが要求される.このため,通常完全な仕様を用いる演繹的プログラム合成と対比されて,帰納プログラミングは自動プログラミングやプログラム合成の分野内において特殊な分野と考えられている.