La capacidad de cero errores de los canales discretos sin memoria (DMC), introducida por Shannon, es un concepto fundamental en la teoría de la información con una relevancia operativa significativa, particularmente en entornos donde incluso un solo error de transmisión es inaceptable. A pesar de su importancia, no se conoce ninguna expresión o algoritmo general en forma cerrada para calcular esta capacidad. En este trabajo, investigamos los límites teóricos de la computabilidad de la capacidad de cero errores y establecemos varias limitaciones fundamentales. Nuestro resultado principal muestra que la capacidad de cero errores de los canales ruidosos no es computable en el sentido de Banach-Mazur y, por lo tanto, tampoco es computable en el sentido de Borel-Turing. Esto proporciona una fuerte forma de no computabilidad que va más allá de la indecidibilidad clásica, capturando la discontinuidad inherente de la función de capacidad. Como una contribución adicional, analizamos las profundas conexiones entre (i) la capacidad de cero errores de los DMC, (ii) la capacidad de Shannon de los grafos, y (iii) la caracterización operativa de Ahlswede a través de la capacidad de error máximo de los canales (AVC) que varían arbitrariamente de 0-1. Demostramos que las preguntas clave de semi-decidibilidad son equivalentes para las tres capacidades, unificando así estos problemas en un marco algorítmico común. Si bien el estado de computabilidad de la capacidad de Shannon de los grafos sigue sin resolverse, nuestro resultado de equivalencia aclara qué hace que este problema sea tan desafiante e identifica las barreras lógicas que deben superarse para resolverlo. Juntos, estos resultados trazan el paisaje computacional de la teoría de la información de cero errores y proporcionan una base para futuras investigaciones sobre la intractabilidad algorítmica de los cálculos de capacidad exactos.