Odločljivost

Iz Wikipedije, proste enciklopedije

Logični sistem je odločljiv, če in samo če obstaja algoritem, po katerem za vsako dobro napisano formulo v tem sistemu, obstaja največje končno število N korakov, po katerih (vsaj) se je algoritem sposoben odločiti, ali je dana formula veljavna ali neveljavna.