predicato semidecidibile

predicato semidecidibile

predicato semidecidibile in logica, predicato P(x) per il quale si riesce a stabilire, con un numero finito di operazioni, se esso è vero, mentre non esiste una procedura finita per stabilire se esso è falso. La funzione caratteristica di un predicato semidecidibile è, quindi, definita solo per alcuni valori della variabile x ed è pertanto una funzione ricorsiva parziale (→ predicato decidibile).