<p>Could any (computational) function be expressed in terms of a Julia set?</p>
<p>Is the space of all possible computational functions (which I think is defined by Turing completeness) translatable to the space of all possible Julia sets?</p>

CC BY-SA 4.0
2020-10-05T16:37:27.077Z
(i) Aren't Julia sets as normally defined uncountable subsets of the plane?  But computable functions (defined via standard Turing model), by definition, map countable sets to countable sets.  So what precisely do you mean by "expressed" or "translatable"?  (ii) The paper ["The Complexity of the Real Line is a Fractal"](https://doi.org/10.1109/SCT.1989.41820) by Cai and Hartmanis at least makes some connection between computational complexity and fractals.
Neal Young
CC BY-SA 4.0
2020-10-05T17:36:59.960Z
I think you're likely aware of it, but following up on Neal's bibliographic comment, the obvious first place to look would be "Computability of Julia Sets" by Braverman and Yampolsky: https://www.springer.com/gp/book/9783540685463.
Huck Bennett
CC BY-SA 4.0
2020-10-05T19:53:03.783Z
After more research, I now believe it is technically impossible, but might still be practically possible to compose a turning-complete language in terms of Julia sets. My reasoning relies on proof of the halting problem. If you could write any program to be expressed as a Julia set, you would know if it halts or not because the Mandelbrot set is a map of Julia sets, and the shape of the MB set is determined by a function's ability to halt (converge). Of course, all this is cursory & my logic is probably flawed but to me this indicates that there is not a 1-1 correspondence in the state spaces.
MetaStack
<universal-turing-machines>
Are Julia sets (theoretically) Turing-complete?
MetaStack
# Are Julia sets (theoretically) Turing-complete?

(Asked by: username_0 on 2020-10-04)

Could any (computational) function be expressed in terms of a Julia set?

Is the space of all possible computational functions (which I think is defined by Turing completeness) translatable to the space of all possible Julia sets?

**Tags:** universal-turing-machines

> **Comments:**
> **username_1**: (i) Aren't Julia sets as normally defined uncountable subsets of the plane?  But computable functions (defined via standard Turing model), by definition, map countable sets to countable sets.  So what precisely do you mean by "expressed" or "translatable"?  (ii) The paper ["The Complexity of the Real Line is a Fractal"](https://doi.org/10.1109/SCT.1989.41820) by Cai and Hartmanis at least makes some connection between computational complexity and fractals.  
> **username_2**: I think you're likely aware of it, but following up on Neal's bibliographic comment, the obvious first place to look would be "Computability of Julia Sets" by Braverman and Yampolsky: https://www.springer.com/gp/book/9783540685463.  
> **username_0**: After more research, I now believe it is technically impossible, but might still be practically possible to compose a turning-complete language in terms of Julia sets. My reasoning relies on proof of the halting problem. If you could write any program to be expressed as a Julia set, you would know if it halts or not because the Mandelbrot set is a map of Julia sets, and the shape of the MB set is determined by a function's ability to halt (converge). Of course, all this is cursory & my logic is probably flawed but to me this indicates that there is not a 1-1 correspondence in the state spaces.  

---

## 0 answers

