We initiate the study of computable presentations of real and complex C*-algebras under the program of effective metric structure theory. With the group situation as a model, we develop corresponding notions of recursive presentations and word problems for C*-algebras, and show some analogous results hold in this setting. Famously, every finitely generated group with a computable presentation is computably categorical, but we provide a counterexample in the case of C*-algebras. On the other hand, we show every finite-dimensional C*-algebra is computably categorical.

A Turing degree d is the degree of categoricity of a computable structure ${\cal S}$ if d is the least degree capable of computing isomorphisms among arbitrary computable copies of ${\cal S}$. A degree d is the strong degree of categoricity of ${\cal S}$ if d is the degree of categoricity of ${\cal S}$, and there are computable copies ${\cal A}$ and ${\cal B}$ of ${\cal S}$ such that every isomorphism from ${\cal A}$ onto ${\cal B}$ computes d. In this paper, we build a c.e. degree d and a computable rigid structure ${\cal M}$ such that d is the degree of categoricity of ${\cal M}$, but d is not the strong degree of categoricity of ${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].

For a computable structure ${\cal S}$, we introduce the notion of the spectral dimension of ${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of ${\cal S}$. We prove that for a nonzero natural number N, there is a computable rigid structure ${\cal M}$ such that $0\prime$ is the degree of categoricity of ${\cal M}$, and the spectral dimension of ${\cal M}$ is equal to N.

We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we characterize which of these linear orders are computably categorical.

We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.