The computable dimension of trees of infinite height
Miller, Russell
J. Symbolic Logic, Tome 70 (2005) no. 1, p. 111-141 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.
Publié le : 2005-03-14
Classification:  
@article{1107298513,
     author = {Miller, Russell},
     title = {The computable dimension of trees of infinite height},
     journal = {J. Symbolic Logic},
     volume = {70},
     number = {1},
     year = {2005},
     pages = { 111-141},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1107298513}
}

Miller, Russell. The computable dimension of trees of infinite height. J. Symbolic Logic, Tome 70 (2005) no. 1, pp.  111-141. http://gdmltest.u-ga.fr/item/1107298513/