
We introduce the notion of feedback computable functions from $2^\omega$ to
$2^\omega$, extending feedback Turing computation in analogy with the standard
notion of computability for functions from $2^\omega$ to $2^\omega$. We then
show that the feedback computable functions are precisely the effectively Borel
functions. With this as motivation we define the notion of a feedback
computable function on a structure, independent of any coding of the structure
as a real. We show that this notion is absolute, and as an example characterize
those functions that are computable from a Gandy ordinal with some finite
subset distinguished.

We investigate the relative computability of exchangeable binary relational
data when presented in terms of the distribution of an invariant measure on
graphs, or as a graphon in either $L^1$ or the cut distance. We establish basic
computable equivalences, and show that $L^1$ representations contain
fundamentally more computable information than the other representations, but
that $0'$ suffices to move between computable such representations. We show
that $0'$ is necessary in general, but that in the case of randomfree
graphons, no oracle is necessary. We also provide an example of an
$L^1$computable randomfree graphon that is not weakly isomorphic to any
graphon with an a.e. continuous version.

We show that the disintegration operator on a complete separable metric space
along a projection map, restricted to measures for which there is a unique
continuous disintegration, is strongly Weihrauch equivalent to the limit
operator Lim. When a measure does not have a unique continuous disintegration,
we may still obtain a disintegration when some basis of continuity sets has the
Vitali covering property with respect to the measure; the disintegration,
however, may depend on the choice of sets. We show that, when the basis is
computable, the resulting disintegration is strongly Weihrauch reducible to
Lim, and further exhibit a single distribution realizing this upper bound.

The problem of replicating the flexibility of human commonsense reasoning
has captured the imagination of computer scientists since the early days of
Alan Turing's foundational work on computation and the philosophy of artificial
intelligence. In the intervening years, the idea of cognition as computation
has emerged as a fundamental tenet of Artificial Intelligence (AI) and
cognitive science. But what kind of computation is cognition?
We describe a computational formalism centered around a probabilistic Turing
machine called QUERY, which captures the operation of probabilistic
conditioning via conditional simulation. Through several examples and analyses,
we demonstrate how the QUERY abstraction can be used to cast commonsense
reasoning as probabilistic inference in a statistical model of our observations
and the uncertain structure of the world that generated that experience. This
formulation is a recent synthesis of several research programs in AI and
cognitive science, but it also represents a surprising convergence of several
of Turing's pioneering insights in AI, the foundations of computation, and
statistics.

We obtain a nonimplication result in the Medvedev degrees by studying
sequences that are close to MartinL\"of random in asymptotic Hamming distance.
Our result is that the class of stochastically biimmune sets is not Medvedev
reducible to the class of sets having complex packing dimension 1.

We prove a computable version of de Finetti's theorem on exchangeable
sequences of real random variables. As a consequence, exchangeable stochastic
processes expressed in probabilistic functional programming languages can be
automatically rewritten as procedures that do not modify nonlocal state. Along
the way, we prove that a distribution on the unit interval is computable if and
only if its moments are uniformly computable.

As inductive inference and machine learning methods in computer science see
continued success, researchers are aiming to describe ever more complex
probabilistic models and inference algorithms. It is natural to ask whether
there is a universal computational procedure for probabilistic inference. We
investigate the computability of conditional probability, a fundamental notion
in probability theory and a cornerstone of Bayesian statistics. We show that
there are computable joint distributions with noncomputable conditional
distributions, ruling out the prospect of general inference algorithms, even
inefficient ones. Specifically, we construct a pair of computable random
variables in the unit interval such that the conditional distribution of the
first variable given the second encodes the halting problem. Nevertheless,
probabilistic inference is possible in many common modeling settings, and we
prove several results giving broadly applicable conditions under which
conditional distributions are computable. In particular, conditional
distributions become computable when measurements are corrupted by independent
computable noise with a sufficiently smooth bounded density.