Author name cluster

Douglas Cenzer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2017 Journal Article

Random numbers as probabilities of machine behavior

George Barmpalias
Douglas Cenzer
Christopher P. Porter

A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behavior of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to several machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing degree when they are defined with respect to different universal machines.

Details DOI

TCS Journal 2002 Journal Article

Effectively closed sets and graphs of computable real functions

Douglas Cenzer
Jeffrey B. Remmel

In this paper, we compare the computability and complexity of a continuous real function F with the computability and complexity of the graph G of the function F. A similar analysis will be carried out for functions on subspaces of the real line such as the Cantor space, the Baire space and the unit interval. In particular, we define four basic types of effectively closed sets C depending on whether (i) the set of closed intervals which with nonempty intersection with C is recursively enumerable (r. e.), (ii) the set of closed intervals with empty intersection with C is r. e. , (iii) the set of open intervals which with nonempty intersection with C is r. e. , and (iv) the set of open intervals with empty intersection with C is r. e. We study the relationships between these four types of effectively closed sets in general and the relationships between these four types of effectively closed sets for closed sets which are graphs of continuous functions.

Details DOI

TCS Journal 1999 Journal Article

Index sets in computable analysis

Douglas Cenzer
Jeffrey B. Remmel

Π 0 1 classes in a space X where X equals {0, 1} ω, ω ω, [0, 1], or the real line real are given an effective enumeration P e, X and the computably continuous functions are given an effective enumeration F e, X. The notion of index sets associated with Π 0 1 classes and with computably continuous functions is developed. The complexity of various problems of analysis is determined by the complexity of the associated index set.

Details DOI

I&C Journal 1998 Journal Article

Complexity and Categoricity

Douglas Cenzer
Jeffrey B. Remmel

We define a notion of a feasible Scott family of formulas for a feasible model and give various conditions on a Scott family which imply that two models with the same family are feasibly isomorphic. For example, ifAandBpossess a common strongly p-time Scott family and both have universe {1}*, then they are p-time isomorphic. These results are applied to the study of permutation structures, linear orderings, equivalence relations, and Abelian groups. For example, conditions on two permutation structures (A, f) and (B, g) are given which imply that (A, f) and (B, g) are p-time isomorphic.

Details DOI