Teoría de la computabilidad

Carta Común · N.º 258045

La teoría de la computabilidad o teoría de la recursión es la parte de la computación que estudia los problemas de decisión que se pueden resolver con un algoritmo o equivalentemente con una máquina de Turing. Las preguntas fundamentales de la teoría de la computabilidad son: ¿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? La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

Leer en Wikipedia · Imagen Ulrich Haessler, CC BY-SA 3.0 de