Computability of the Julia set. Nonrecurrent critical orbits (Q2438692): Difference between revisions

Let \(S,T\) be countable subsets of \(\mathbb{N}\). A function \(f:S\longrightarrow T\) is called computable, if there exists a Turing machine \(M\) which takes \(x\) as an input and outputs \(f(x)\). We remind that the Turing machine \(M\) is given by a quadruple \((Q,\mathcal{A},\delta,i)\), where \(Q\) is a finite set of states, \(i \in Q\) is the initial state and \(\mathcal{A}\) is the finite alphabet. We assume that \(Q\) and \(\mathcal{A}\) are disjoint sets, and \(\mathcal{A}\) always contains the special symbols \(\sqcup\) and \(\triangleright\). Finally, \(\delta\) is the transition function, which maps \(Q \times \mathcal{A}\) to \(Q\cup \{h, ``\mathrm{yes}", ``\mathrm{no}" \} \times \mathcal{A} \cup \{\leftarrow,\rightarrow, - \}\). We further assume that \(h\) (the halting state), ``yes'' (the accepting state), ``no'' (the rejecting state), and the cursor directions (\(\leftarrow\) for left, \(\rightarrow\) for right and \( - \) for stay) are not in \(Q \cup \mathcal{A}\). The function \(\delta\) is called the ``program'' of the machine \(M\). A real number \(\alpha\) is computable if there is a computable function \(\phi:\mathbb{N} \longrightarrow \mathbb{Q}\) such that for all \(n \in \mathbb{N}\) we have \(|\alpha-\phi(n)|<2^{-n}\). A function \(\psi:\mathbb{N} \longrightarrow \mathbb{D}\) is called an oracle for an element \(x \in \mathbb{R}^n\), if \(\|\psi(m)-x\|<2^{-m}\), for all \(m \in \mathbb{N}\) where \(\|\|\) is the Euclidean norm on \(\mathbb{R}^n\) and \(\mathbb{D}\) is the set of dyadic numbers given by \[ \mathbb{D}=\Big\{\frac{k}{2^l},k\in \mathbb{Z}, l \in \mathbb{D}\Big\}. \] An oracle Turing machine \(M^{\psi}\) is a Turing machine, which can query \(\psi(m)\) for any \(m \in \mathbb{N}\). A bounded set \(S \subset \mathbb{R}^2\) is computable in time \(t(n)\) if there is a Turing machine, which computes values in time \(t(n)\) of a function \(h(n,.)\) given by \(h(n,z)=1\), if \(d(z,S) \leq 2^{-n-2}\); \(h(n,z)=0\), if \(d(z,S) \geq 2\cdot 2^{-n-2}\); \(h(n,z)=0\) or 1, otherwise, where \(n \in \mathbb{N}\) and \(z=(\frac{i}{2^{n+2}},\frac{j}{2^{n+2}})\), \(i,j \in \mathbb{Z}\). We say that \(S\) is poly-time computable if \(t(n)\) is a polynomial. Let \(f\) be a rational map. Denote by \(J_f\) its Julia set. For any \(z \in \mathbb{C}\) put \[ \mathcal{O}(z)=\big\{f^n(z), n \geq 1\big\}, \] the forward orbit of \(z\). Let \(\omega(z)=\overline{\mathcal{O}(z)}\setminus\{\mathcal{O}(z)\}\) be the \(\omega\)-limit set of \(z\). The set of critical points of \(f\) which lie in \(J_f\) is denoted by \(C_f\). Put \(\Omega_f=\bigcup_{c \in C_f}\omega(c).\) In this setting, the author proves the following theorem. Theorem. Let \(f\) be a rational map. Assume that \(f\) has no parabolic periodic points and \(\Omega_f\) does not contain any critical points. Then \(J_f\) is poly-time computable by a Turing machine with an oracle for the coefficients of \(f\).