Funcție calculabilă
O funcție calculabilă (sau funcție recursivă ) este o funcție semicomputabilă (sau funcție recursivă parțială ) care este, de asemenea , totală , adică definită pe întregul său domeniu. Acestea sunt funcțiile calculate de o mașină Turing „terminantă”.
O funcție calculabilă nu este neapărat „calculabilă fizic”, de exemplu dacă timpul său de execuție depășește câteva miliarde de ani.
Cele mai simple exemple de funcții calculabile sunt funcții constante . O consecință a principiului treimii excluse este atunci că funcția constantă care la un număr întreg asociază 1 dacă conjectura Goldbach este adevărată și 0 dacă este falsă este calculabilă, deși nu știm astăzi dacă conjectura este adevărată. Acest lucru arată cum aplicarea acestui principiu distruge orice noțiune intuitivă de calculabilitate.
Exemple
- Programele de computer care se opresc (în timpul executării pe orice intrare) sunt funcții calculabile.
- Funcția care ia ca intrare o mașină Turing (reprezentată printr-un număr întreg) și o intrare pentru această mașină și le asociază cu 1 dacă această mașină se oprește pe această intrare, altfel nimic, este o funcție semicalculabilă. Doar o aplicație a principiului terței excluse face posibilă extinderea acestei funcții într-o funcție totală care dă 0 dacă mașina luată în considerare nu se oprește pe intrarea luată în considerare, dar această funcție nu poate fi calculată (pentru mai multe informații consultați articol Problemă de închidere ).
- Calculul unui GCD este o funcție calculabilă.
Referințe
-
Alain Prochiantz , Machine-Mind , Odile Jacob,5 ianuarie 2001( citește online ).
Vezi și tu