![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Bundesarchiv_Bild_183-S1024-016%252C_VEB_Robotron_Elektronik_Dresden%252C_Computer_EC_1040.jpg/640px-Bundesarchiv_Bild_183-S1024-016%252C_VEB_Robotron_Elektronik_Dresden%252C_Computer_EC_1040.jpg&w=640&q=50)
Teoría da computabilidade
From Wikipedia, the free encyclopedia
A teoría da computabilidade é a parte da computación que estuda os problemas de decisión que poden ser resoltos cun algoritmo ou equivalentemente coa chamada máquina de Turing. A teoría da computabilidade interésase por catro preguntas:
- Que problemas pode resolver unha máquina de Turing?
- Que outros formalismos equivalen ás máquinas de Turing?
- Que problemas requiren máquinas máis poderosas?
- Que problemas requiren máquinas menos poderosas?
Este artigo contén varias ligazóns externas e/ou bibliografía ao fin da páxina, mais poucas ou ningunha referencia no corpo do texto. Por favor, mellora o artigo introducindo notas ao pé, citando as fontes. Podes ver exemplos de como se fai nestes artigos. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Bundesarchiv_Bild_183-S1024-016%2C_VEB_Robotron_Elektronik_Dresden%2C_Computer_EC_1040.jpg/640px-Bundesarchiv_Bild_183-S1024-016%2C_VEB_Robotron_Elektronik_Dresden%2C_Computer_EC_1040.jpg)
A teoría da complexidade computacional clasifica as funcións computables segundo o uso que fan de diversos recursos en diversos tipos de máquina.