In this paper we study the K-theory groups of a reduced group C*-algebra from the point of view of computability theory. More precisely, given a group presentation we construct a suitable combinatorial analog of the associated reduced group C*-algebra and of the K-theory representatives. We introduce the K-problems as, given a K-theory representative, to algorithmically decide whether it is in the trivial K-theory class.; In chapter 4 we show that the K-problems are undecidable in general. The proof makes use of the undecidability of the problem of distinguishing homology classes in group theory, and the reducibility of the this problem to the K-problem via a computable map constructed from the Chern character and the assembly map of the strong Novikov conjecture.; We also introduce unbounded Predholm modules as an analog of metric in noncommutative spaces. We show that this concept extends to matrix algebras and paths, providing us with a mathematical tool to measure the algorithmic complexity of the representatives of the K-theory classes. We also show that, up to a recursive deformation, this measure of complexity is stable under Bott periodicity. |