Clasificación de Programas

• Computables: el dominio del programa es total.
• Parcialmente computables: el dominio del programa no es total.
• No computables: no existe forma de poder computar el programa. Probado por reducciones o diagonalización.

Clasificación de Lenguajes

• Computables: el predicado característico es computable.
• Computablemente enumerables: el predicado devuelve 1 si es computable, indefinido sino.
• No computables: el predicado característico no es computable.

Propiedades

• Reducción: A reduce a B si se puede computar A utilizando el programa B a través de un programa f que utilice B y sea computable.

  

• La computabilidad es cerrada por el complemento: A es computable si solo si A complemento es computable.

• A es computable si solo si A es computablemente enumerable y A complemento es computablemente enumerable.