Accions

Indecibilitat

De Wikisofia

La revisió el 00:57, 5 feb 2015 per Sofibot (discussió | contribucions) (Es crea la pàgina amb «{{ConcepteWiki}} Un sistema formal és indecidible si no disposa d'un algorisme o procediment de decisió...».)
(dif.) ← Versió més antiga | Versió actual (dif.) | Versió més nova → (dif.)

Un sistema formal és indecidible si no disposa d'un algorisme o procediment de decisió per determinar, en un nombre finit de passos, si un enunciat o fórmula d'aquest sistema és un teorema del mateix. La lògica d'enunciats és decidible, atès que disposa d'un medi mecànic, les taules de veritat, per poder determinar, per a qualsevol fórmula donada, si és o no una veritat lògica, una contradicció o una contingència. La lògica de predicats de primer ordre, en canvi, no ho és, segons el teorema de Church (1936).