insieme decidibile

insieme decidibile

insieme decidibile in logica, insieme per cui esiste un algoritmo di calcolo che permette di stabilire in un tempo finito se, dato un elemento a, l’elemento appartiene o non appartiene a esso. Qualora invece l’algoritmo sia in grado di identificare tutti gli elementi che appartengono all’insieme, ma non quelli che non gli appartengono, l’insieme è detto semidecidibile. Gli insiemi finiti sono decidibili, mentre un insieme infinito è decidibile se e solo se sono semidecidibili sia esso sia il suo insieme complementare. In maniera equivalente si può affermare che un insieme S è decidibile o ricorsivo se la sua funzione caratteristica ƒ(x) è una funzione ricorsiva, dove per funzione caratteristica si intende la funzione definita come segue:

Dato un predicato decidibile P, l’insieme degli elementi che lo soddisfano, cioè l’insieme K = {x : P(x)}, è un insieme decidibile.