Las siguientes nociones están todas relacionadas, pero no son lo mismo:
- Teorema de indefinibilidad de Tarski : los sistemas lógicos consistentes suficientemente potentes no pueden evaluar la verdad de sus propias declaraciones. Es decir, no puede formalizar “esta declaración es falsa” en ningún sistema consistente, porque no puede dividir la parte “es falsa” en operaciones lógicas.
- La paradoja del mentiroso : el lenguaje humano no tiene esta restricción, por lo que puede hacer declaraciones que parecen paradójicas. Por ejemplo: “Esta declaración es falsa” o “‘Cuando se agrega a su cita, da una declaración falsa’, cuando se agrega a su cita, da una declaración falsa”.
- El primer teorema de incompletitud de Godel : en cualquier sistema lógico consistente suficientemente potente, hay afirmaciones verdaderas que no se pueden probar como verdaderas. Es decir, “esta afirmación no se puede probar” se puede formalizar y es verdadera y no demostrable si el sistema es (omega-) consistente.
- Segundo teorema de incompletitud de Godel : los sistemas lógicos consistentes suficientemente potentes no pueden reclamar o probar su propia consistencia.
- Insolubilidad del problema de detención : no existe un programa (para una máquina suficientemente potente) que pueda determinar, para cualquier programa de entrada, si el programa de entrada se detiene o no.
- Respuesta negativa al décimo problema de Hilbert : no existe un algoritmo que pueda determinar, para cualquier ecuación entera, si es solucionable en los enteros.
- Incomputabilidad de la complejidad de Kolmogorov : en cualquier lenguaje de programación hay un programa más corto que genera una cadena dada, pero si el lenguaje de programación es razonablemente poderoso, no hay algoritmo para encontrarlo.
- Una clase infinita de otras nociones , pero no existe un algoritmo para determinar si una noción dada pertenece a la clase.
