Arrow Research search

Author name cluster

Michael Yampolsky

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.

2 papers
1 author row

Possible papers

2

STOC Conference 2020 Conference Paper

How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non-computable

  • Cristobal Rojas
  • Michael Yampolsky

We consider the simplest non-linear discrete dynamical systems, given by the logistic maps f a ( x )= ax (1− x ) of the interval [0,1]. We show that there exist real parameters a ∈ (0,4) for which almost every orbit of f a has the same statistical distribution in [0,1], but this limiting distribution is not Turing computable. In particular, the Monte Carlo method cannot be applied to study these dynamical systems.

Details

STOC Conference 2007 Conference Paper

Constructing non-computable Julia sets

  • Mark Braverman
  • Michael Yampolsky

While most polynomial Julia sets are computable, it has been recently shown [12] that there exist non-computable Julia sets. The proof was non-constructive, and indeed there were doubts as to whether specific examples of parameters with non-computable Julia sets could be constructed. It was also unknown whether the non-computability proof can be extended to the filled Julia sets. In this paper we give an answer to both of these questions, which were the main open problems concerning the computability of polynomial Julia sets. We show how to construct a specific polynomial with a non-computable Julia set. In fact, in the case of Julia sets of quadratic polynomials we give a precise characterization of Juliasets with computable parameters. Moreover, assuming a widely believed conjecture in Complex Dynamics, we give a poly-time algorithm forcomputing a number c such that the Julia set J z 2 +c z is non-computable. In contrast with these results, we show that the filled Julia set of a polynomial is always computable.

Details