Função semicomputável
Aspeto
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Fevereiro de 2015) |
Na teoria da computabilidade, uma função semicomputável é uma função parcial que pode ser aproximada tanto por cima quanto por baixo através de uma função computável.
Mais precisamente, uma função parcial é superiomente semicomputável, significando que ela pode ser aproximada por cima, se existe uma função computável , onde é parámetro desejado para e é o nível de aproximação, de modo que:
Analogamente, uma função parcial é inferiormente semicomputável se e somente se é superiomente semicomputável ou equivalentemente, se existe uma função computável de modo que:
Se uma função parcial for superior e inferiormente semicomputável, então ela passará a ser chamada de uma função computável.
Referências
[editar | editar código-fonte]- Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, pp 37–38, Springer, 1997.