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. |
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.