O que é Computabilidade

Prévia do material em texto

O que é Computabilidade?
Quase todos os problemas podem ser resolvidos através de um algoritmo. Segundo o Wikipédia: “Computabilidade é a habilidade de resolver problemas de forma efetiva”.
Ou seja, se é possível resolver um determinado problema completamente e precisamente, mas usando uma quantidade não infinita de passos para isso.
Problemas
A Computabilidade pode ser explorada através de problemas computacionais, como veremos a seguir:
Existem dois problemas:
Problemas de Decisão: Este problema consiste em pegar um conjunto Universo(que pode conter números, strings e dentre outros), que daremos o nome de X, e, dentro deste conjunto, pegar um subconjunto, que daremos o nome de Y. Então, ao selecionarmos um número do conjunto X, a máquina deverá verificar se o mesmo pertence, ou não, ao conjunto que de Y.