La
Teoría de la computabilidad es la parte de la
computación que estudia los
problemas de decisión que pueden ser resueltos con un
algoritmo o equivalentemente con una
máquina de Turing. La teoría de la computabilidad se interesa por cuatro preguntas:
- ¿Qué problemas puede resolver una máquina de Turing?
- ¿Qué otros formalismos equivalen a las máquinas de Turing?
- ¿Qué problemas requieren máquinas más poderosas?
- ¿Qué problemas requieren máquinas menos poderosas?