Função semicomputável – Wikipédia, a enciclopédia livre
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.