Abstract We study presentations of $C(X)$ that are evaluative over a presentation of $X$ in that $(f,p) \mapsto f(p)$ is computable. We prove existence–uniqueness theorems for such presentations. We use our methods to prove an effective Banach–Stone Theorem for unital commutative $C^{*}$ algebras. We also apply our results to the computable categoricity of $C^{*}$ algebras and compact Polish spaces.

Abstract Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

Abstract We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n -tuples of a binary tree are colored.

Abstract We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable subsets of 2ω and Kolmogorov complexity play a major role in the proof.

Abstract. Call a set A n-correctable if every set Turing reducible to A via a Turing machine that on any input makes at most n queries is Turing reducible to A via a Turing machine that on any input makes at most n-queries and on any input halts no matter what answers are given to its queries. We show that if a c.e. set A is n-correctable for some n ≥ 2, then it is n-correctable for all n. We show that this is the optimal such result by constructing a c.e. set that is 1-correctable but not 2-correctable. The former result is obtained by examining the logical closure properties of c.e. sets that are 2-correctable.

Abstract For a fixed set A. the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: and, for m > 2, where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA: • ODDnA can be decided with n parallel queries to A, but not with n − 1. • ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1. • MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1. • MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1. The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, Q(n, A) = {S: S can be decided with n sequential queries to A}. Q∥ (n, A) = {S : S can be decided with n parallel queries to A}. We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: • Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ … Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ … The same is true if A is a jump.

Abstract We study the following classes: ● Q* (r1A1…..rkAk) which is defined to be the collection of all sets that can be computed by a Turing machine that on any input makes a total of ri, queries to Ai, for all i ∈ {1..… k}. ● Q(r1A1…..rkAk) which is defined like Q* (r1A1….. rkAk) except that queries to Ai, must be made before queries to Ai+1 for all i ∈ {1….. k – 1}. ● QC(r1A1….. rkAk) which is defined like Q{r1A1….. rkAk) except that the Turing machine must halt even if given incorrect answers to some of its queries. We show that if A1 ….. Ak are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r1…..rkAk). This extends a result of Beigel's [1]. Since the second class is not affected by permutations, we say that these sets commute with each other. We also show that jumps that are too close together may not commute. We also characterize the commutative sequences of sets obtained by iterating the jump operation through an ordinal notation.