Computability and Complexity of Julia Sets
Kota Hiratsuka, Yuzuru Sato, Zin Arai · IEICE Proceeding Series · 2014
Abstract: Since A. M. Turing introduced the notion of computabil-ity in 1936, various theories of real number computation have been studied [1][10][13]. Some are of interest in nonlinear and statisti-cal physics while others are extensions of the mathematical theory of computation. In this review paper, we introduce a recently de-veloped computability theory for Julia sets in complex dynamical systems by Braverman and Yampolsky [3]. 1 Computability and complexity Chaos and fractals have been studied from the viewpoint of computability in physics [6][12][1][2]. Investigation has focused on the nature of complexity aris-ing from simple nonlinear equations. Unpredictability in chaotic attractors and final state sensitivity in fractal basins are discussed in terms of computability and complexity in the theory of computation. We summarize the leading results of a recently developed computability theory for Julia sets by Braverman and Yampolsky [3]. First, we introduce the classical notions of computability introduced by Tur-ing [14], and computable real functions introduced by Pour-El [13]. Turing com-putability is defined by rather a physical model of human computation, called a Turing machine, which is an automaton which consisting of finite internal states and a head to read/write symbols on an external tape. The length of the tape is not restricted, but the number of alphabets is finite. It can manipulate individual symbols on a tape, according to a transition diagram, which tells the machine what action to undertake depending on the current internal state