WEAK CARDINALITY THEOREMS.
Kummer's Cardinality Theorem states that a language A must be recursive if a Turing machine can exclude for any n words w, ¡, w one of the n + 1 possibilities for the cardinality of {w, ¡. w} ∩ A. There was good reason to believe that this theorem is a peculiarity of recursion theory: neither the Ca...
| Publicado en: | Journal of Symbolic Logic Vol. 70; no. 3; pp. 861 - 879 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Sep2005
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |