La computación es la base sobre la cual se construyen casi todos los sistemas informáticos. El estudio de la teoría de la computación es un estudio de nuestra capacidad de hacer cosas.
Tomemos por ejemplo una pregunta simple. “¿Cómo voy a Delhi?”
La respuesta a esa pregunta implicaría primero saber si:
- ¿Cuáles son algunas áreas activas de investigación dentro de la combinatoria?
- Cómo obtener una sólida base matemática
- ¿Cómo programar gráficos matemáticos con python? ¿Hay algún paquete que los incluya?
- ¿Cuál es la interpretación de XOR de los enteros? ¿Hay alguna forma simple de calcular XOR en lugar de 'XOR-ing' todos los bits individuales?
- ¿Existe un algoritmo para fusionar dos árboles rojo-negros con una complejidad menor que O (n + m)?
- ¿Podemos siquiera responder a esa pregunta? [1]
- ¿Hay más de una forma de responder? [2]
- Si hay más de una forma, ¿cómo las comparo para encontrar la mejor? [3]
- ¿Puedo probar una solución a esta pregunta tan rápido como puedo resolverla? [4]
Para ser sincero, estas preguntas también se estudian en CS normal, pero en teoría computacional asumen un papel aún más importante. La premisa misma de encontrar respuestas descansa sobre los hombros de poder actuar. En otras palabras, la computación se basa en la suposición de la capacidad de computar y eso es lo que estudia la teoría de la computación.
Notas al pie
[1] Teoremas de incompletitud de Gödel – Wikipedia
[2] Algoritmos, equivalencia de
[3] Complejidad computacional asintótica – Wikipedia
[4] Problema P versus NP – Wikipedia
