真理値表還元可能性

ウィキペディア小見出し辞書

真理値表還元可能性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)

「再帰理論」の記事における「真理値表還元可能性」の解説

A が B に真理値表還元可能であるとは、どんなオラクルに対しても全域関数を計算するような神託機械によってA が B にチューリング還元可能である場合を指す。神託の使用回数を制限したり、神託機械に条件を課すことで、様々な変種が得られる。それらも研究されている。