Teoría de la computabilidá
From Wikipedia, the free encyclopedia
La Teoría de la computabilidad ye la parte de la computación qu'estudia los problemes de decisión que pueden ser resueltos con un algoritmu o equivalentemente cola llamada máquina de Turing. La teoría de la computabilidad interesar por cuatro preguntes:
- ¿Qué problemes puede resolver una máquina de Turing?
- ¿Qué otros formalismos equivalen a les máquines de Turing?
- ¿Qué problemes riquen máquines más poderoses?
- ¿Qué problemes riquen máquines menos poderoses?
La teoría de la complexidá computacional clasifica les funciones computables según l'usu que faen de diversos recursos en diversos tipos de máquina.