Teoria de la computabilitat
estudi sobre les funcions computables / From Wikipedia, the free encyclopedia
La teoria de la computabilitat és la part de la computació que estudia els problemes de decisió que poden ser resolts amb un algorisme o equivalentment amb una màquina de Turing.[1][2][3] La teoria de la computabilitat s'interessa per quatre preguntes:
- Quins problemes pot resoldre una màquina de Turing?
- Quins altres formalismes equivalen a les màquines de Turing?
- Quins problemes requereixen màquines més poderoses?
- Quins problemes requereixen màquines menys poderoses?
La teoria de la complexitat computacional classifica les funcions computables segons l'ús que fan de diversos recursos en diversos tipus de màquina.