predicato decidibile
predicato decidibile
predicato decidibile predicato P(x), riferito alla variabile x, per il quale esista una procedura che, data una qualsiasi costante a, permetta di stabilire, in un numero finito di passi, se il predicato P(a), ottenuto dalla sostituzione della costante a alla variabile x, è vero o falso (→ algoritmo). La decidibilità di un predicato, basandosi sull’esistenza di un procedimento algoritmico, è strettamente legata al tema della → calcolabilità. Per dare una definizione rigorosa di predicato decidibile è quindi necessario ricorrere al modello di calcolo formale delle → funzioni ricorsive le quali, secondo la tesi di → Church, rappresentano in maniera adeguata il concetto di procedura algoritmica e di funzione calcolabile. Si dice pertanto che un predicato P è decidibile se e solo se la sua funzione caratteristica è una funzione ricorsiva totale, cioè una funzione ricorsiva definita per ogni valore della variabile x. La funzione caratteristica di un predicato P si indica con il simbolo ƒP(x) ed è definita nel modo seguente: supponendo che la variabile x, che compare nel predicato P, possa essere interpretata come un numero naturale, allora:
• ƒP(x) è uguale a 1 se la variabile x soddisfa il predicato P, cioè se la formula P(x) è vera;
• ƒP(x) è uguale a 0 se la variabile x non soddisfa il predicato P, cioè se la formula P(x) è falsa.
Per esempio, indicando con il simbolo P(x) il predicato «x è un numero pari», la funzione caratteristica ƒP(x) assume i seguenti valori: ƒP(1) = 0; ƒP(2) = 1; ƒP(3) = 0; ƒP(4) = 1, …, cioè ƒP(x) è 1 se x è un numero pari, è 0 se x è un numero dispari. Dato che è possibile determinare in maniera effettiva se un numero intero qualsiasi è pari o dispari (basta valutarne la cifra delle unità), risulta che il predicato precedente è decidibile e quindi che la sua funzione caratteristica è una funzione ricorsiva. In alcuni casi si riesce a stabilire, con un numero finito di operazioni, se il predicato P(x) è vero mentre non esiste una procedura finita per stabilire se P(x) è falso. In questo caso si dice che il predicato P(x) è semidecidibile e la sua funzione caratteristica è una funzione ricorsiva parziale cioè è definita solo per alcuni valori della variabile x.