La informática teórica en sí misma no es una subdisciplina de la lógica matemática, pero eso no significa que los dos temas no compartan una relación profunda. La propia máquina de Turing estaba destinada a responder el problema Entscheidungs, una pregunta en lógica matemática. La teoría de la computabilidad temprana (recursividad) era esencialmente una rama de la lógica, que buscaba encontrar el poder de diferentes modelos de computación en el mismo espíritu de estudiar el poder expresivo de los sistemas formales.
Se diferencian en el hecho de que TCS se preocupa por cosas que la lógica simplemente no le importa. Tome la teoría de la complejidad, por ejemplo. ¿Le importaría a un lógico qué tan rápido se puede resolver un problema? No, se harían después de saber que el problema es solucionable en primer lugar. Cabe señalar que la teoría de la complejidad y la lógica se conectan en un tema muy agradable llamado Complejidad descriptiva. Si uno está interesado en investigar esto, sugiero leer Complejidad descriptiva
- Cómo diseñar un algoritmo eficiente cuando me enfrento a un problema
- ¿Cómo puede haber una clase de una clase de objetos en la teoría de conjuntos?
- ¿Cuál es el tiempo de retorno promedio en el cubo booleano n-dimensional, si el proceso estocástico está eligiendo una coordenada al azar y volteándola?
- ¿Dónde son útiles o útiles las matrices en el desarrollo de aplicaciones del mundo real?
- ¿Es importante entender cómo se derivan los teoremas específicos, o es suficiente entender solo cómo usarlos?
