  We ask, and answer, the question of what's computable by Turing machines
equipped with time travel into the past: that is, closed timelike curves or
CTCs (with no bound on their size). We focus on a model for CTCs due to
Deutsch, which imposes a probabilistic consistency condition to avoid
grandfather paradoxes. Our main result is that computers with CTCs can solve
exactly the problems that are Turing-reducible to the halting problem, and that
this is true whether we consider classical or quantum computers. Previous work,
by Aaronson and Watrous, studied CTC computers with a polynomial size
restriction, and showed that they solve exactly the problems in PSPACE, again
in both the classical and quantum cases.
  Compared to the complexity setting, the main novelty of the computability
setting is that not all CTCs have fixed-points, even probabilistically. Despite
this, we show that the CTCs that do have fixed-points suffice to solve the
halting problem, by considering fixed-point distributions involving infinite
geometric series. The tricky part is to show that even quantum computers with
CTCs can be simulated using a Halt oracle. For that, we need the Riesz
representation theorem from functional analysis, among other tools.
  We also study an alternative model of CTCs, due to Lloyd et al., which uses
postselection to "simulate" a consistency condition, and which yields BPP_path
in the classical case or PP in the quantum case when subject to a polynomial
size restriction. With no size limit, we show that postselected CTCs yield only
the computable languages if we impose a certain finiteness condition, or all
languages nonadaptively reducible to the halting problem if we don't.
