Decidabilitate
Această intrare sau secțiune despre matematică și teorii ale computerului nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Conceptul de decidabilitate se găsește în logica matematică și în teoria calculabilității cu semnificații diferite.
Decidabilitate în teoria calculabilității
În teoria calculabilității, un subset A al mulțimii N a numerelor naturale se spune că este decisiv sau recursiv dacă există un algoritm care, primit ca intrare, orice număr natural, se termină prin returnarea 0 sau 1 ca ieșire, în funcție de numărul aparține setului A sau nu. În mod echivalent A se poate decide dacă funcția sa caracteristică este o funcție recursivă .
Decidabilitate în logica matematică
Decidabilitatea unei formule
În logica matematică, o formulă bine formată φ a unei teorii de ordinul întâi T se poate decide în T dacă fie φ, fie negația sa ¬φ sunt demonstrabile în T. În caz contrar (adică dacă nici φ și nici ¬φ nu pot fi dovedite) se spune că formula este indecidabilă în T.
Decidabilitatea afirmațiilor într-o teorie
În logica matematică, o afirmație reprezentată printr-o formulă bine formată φ a unei teorii de ordinul întâi T se spune că poate fi decisă în T dacă φ sau negația sa ¬φ sunt demonstrabile în T. Altfel (adică dacă nici φ și nici ¬φ nu pot fi dovedite) se spune că propoziția este indecidabilă în T.
Exemple clasice de afirmații indecidabile sunt date de teorema lui Goodstein pentru aritmetica lui Peano și de ipoteza continuumului pentru teoria axiomatică a mulțimilor . Aceste afirmații s-au dovedit indecidabile în ipoteza că teoriile în cauză sunt coerente . Teoremele incompletitudinii lui Gödel oferă o procedură prin care, având în vedere orice teorie consistentă T capabilă să reprezinte operații de adunare și multiplicare pe numere naturale, este posibil să se construiască propoziții indecidabile din T. Cu toate acestea, formulele asociate cu astfel de propoziții sunt atât de lungi și complexe încât scrierea lor explicită în limba de ordinul întâi este de fapt imposibilă de realizat atât de un om, cât și de un computer.
Decidabilitatea unei teorii
În logica matematică, se spune că o teorie identificată printr-un set de formule ale unui limbaj este decisă dacă acest set de formule este un set recursiv , adică există un algoritm care, dat fiind orice formulă, poate stabili în timp finit dacă aparține teoriei sau nu.
Un exemplu de teorie decisivă este logica propozițională (în acest caz algoritmul de decizie este cel identificat de tabelele de adevăr ). Exemple de teorii indecidabile sunt aritmetica lui Peano , aritmetica lui Robinson și teoria mulțimilor lui Zermelo-Fraenkel .
