2 The Mandelbrot Set

\(\newcommand{\footnotename}{footnote}\) \(\def \LWRfootnote {1}\) \(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\) \(\let \LWRorighspace \hspace \) \(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\) \(\newcommand {\TextOrMath }[2]{#2}\) \(\newcommand {\mathnormal }[1]{{#1}}\) \(\newcommand \ensuremath [1]{#1}\) \(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \) \(\newcommand {\setlength }[2]{}\) \(\newcommand {\addtolength }[2]{}\) \(\newcommand {\setcounter }[2]{}\) \(\newcommand {\addtocounter }[2]{}\) \(\newcommand {\arabic }[1]{}\) \(\newcommand {\number }[1]{}\) \(\newcommand {\noalign }[1]{\text {#1}\notag \\}\) \(\newcommand {\cline }[1]{}\) \(\newcommand {\directlua }[1]{\text {(directlua)}}\) \(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\) \(\newcommand {\protect }{}\) \(\def \LWRabsorbnumber #1 {}\) \(\def \LWRabsorbquotenumber "#1 {}\) \(\newcommand {\LWRabsorboption }[1][]{}\) \(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\) \(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\) \(\def \mathcode #1={\mathchar }\) \(\let \delcode \mathcode \) \(\let \delimiter \mathchar \) \(\def \oe {\unicode {x0153}}\) \(\def \OE {\unicode {x0152}}\) \(\def \ae {\unicode {x00E6}}\) \(\def \AE {\unicode {x00C6}}\) \(\def \aa {\unicode {x00E5}}\) \(\def \AA {\unicode {x00C5}}\) \(\def \o {\unicode {x00F8}}\) \(\def \O {\unicode {x00D8}}\) \(\def \l {\unicode {x0142}}\) \(\def \L {\unicode {x0141}}\) \(\def \ss {\unicode {x00DF}}\) \(\def \SS {\unicode {x1E9E}}\) \(\def \dag {\unicode {x2020}}\) \(\def \ddag {\unicode {x2021}}\) \(\def \P {\unicode {x00B6}}\) \(\def \copyright {\unicode {x00A9}}\) \(\def \pounds {\unicode {x00A3}}\) \(\let \LWRref \ref \) \(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\) \( \newcommand {\multicolumn }[3]{#3}\) \(\require {textcomp}\) \(\newcommand {\intertext }[1]{\text {#1}\notag \\}\) \(\let \Hat \hat \) \(\let \Check \check \) \(\let \Tilde \tilde \) \(\let \Acute \acute \) \(\let \Grave \grave \) \(\let \Dot \dot \) \(\let \Ddot \ddot \) \(\let \Breve \breve \) \(\let \Bar \bar \) \(\let \Vec \vec \) \(\renewcommand {\vec }{\boldsymbol }\) \(\newcommand {\Edge }{\ensuremath {\,\textemdash \,}}\) \(\newcommand \Const [1]{\text {\textsf {#1}}}\) \(\DeclareMathOperator {\lerp }{lerp}\) \(\DeclareMathOperator {\bitlen }{bitlen}\) \(\DeclareMathOperator {\sign }{sign}\) \(\newcommand {\I }{\mathrm {i}}\) \(\newcommand \AND {\mathbin {\&}}\) \(\newcommand \OR {\mathbin {|}}\) \(\newcommand \XOR {\mathbin {{}^{\wedge }}}\) \(\newcommand \shl {\ll }\) \(\newcommand \shr {\ggg }\) \(\newcommand \asr {\gg }\) \(\newcommand \NOT {\ensuremath {\mathord {\sim }}}\) \(\newcommand {\isep }{\mathrel {{.}\,{.}}}\) \(\newcommand {\Id }[1]{\mathit {#1}}\) \(\newcommand {\const }[1]{\mathsf {#1}}\) \(\newcommand {\algorithmname }[1]{\text {\textsc {#1}}}\) \(\newcommand {\bits }[1]{\text {#1}}\) \(\newcommand {\hexa }[1]{\mathtt {0x#1}}\) \(\newcommand {\num }[1]{#1}\) \(\newcommand {\qed }{\quad \square }\) \(\newcommand {\idiv }[2]{\lfloor #1/#2\rfloor }\) \(\newcommand \attribdot {\ensuremath {\mkern 1.5mu.\mkern 1.5mu}}\) \(\newcommand \attribxr [2]{#1\attribdot \text {#2}}\) \(\newcommand \attribir [2]{\Id {#1}\attribdot \text {#2}}\) \(\newcommand \attribii [2]{\Id {#1}\attribdot \Id {#2}}\) \(\newcommand \textsc [1]{#1}\) \(\require {colortbl}\) \(\let \LWRorigcolumncolor \columncolor \) \(\renewcommand {\columncolor }[2][named]{\LWRorigcolumncolor [#1]{#2}\LWRabsorbtwooptions }\) \(\let \LWRorigrowcolor \rowcolor \) \(\renewcommand {\rowcolor }[2][named]{\LWRorigrowcolor [#1]{#2}\LWRabsorbtwooptions }\) \(\let \LWRorigcellcolor \cellcolor \) \(\renewcommand {\cellcolor }[2][named]{\LWRorigcellcolor [#1]{#2}\LWRabsorbtwooptions }\) \(\newcommand {\tcbset }[1]{}\) \(\newcommand {\tcbsetforeverylayer }[1]{}\) \(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\) \(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\) \(\newcommand {\tcblower }{}\) \(\newcommand {\tcbline }{}\) \(\newcommand {\tcbtitle }{}\) \(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\) \(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\) \(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\) \(\newcommand {\toprule }[1][]{\hline }\) \(\let \midrule \toprule \) \(\let \bottomrule \toprule \) \(\def \LWRbooktabscmidruleparen (#1)#2{}\) \(\newcommand {\LWRbooktabscmidrulenoparen }[1]{}\) \(\newcommand {\cmidrule }[1][]{\ifnextchar (\LWRbooktabscmidruleparen \LWRbooktabscmidrulenoparen }\) \(\newcommand {\morecmidrules }{}\) \(\newcommand {\specialrule }[3]{\hline }\) \(\newcommand {\addlinespace }[1][]{}\) \(\newcommand {\LWRsubmultirow }[2][]{#2}\) \(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\) \(\newcommand {\multirow }[2][]{\LWRmultirow }\) \(\newcommand {\mrowcell }{}\) \(\newcommand {\mcolrowcell }{}\) \(\newcommand {\STneed }[1]{}\) \(\newcommand {\LWRldelimtwo }[1][]{\text {#1}~\LWRbigdelim }\) \(\newcommand {\LWRldelimone }[2][]{\LWRldelimtwo }\) \(\def \ldelim #1#2{\def \LWRbigdelim {#1}\LWRldelimone }\) \(\newcommand {\LWRrdelimtwo }[1][]{\LWRbigdelim ~\text {#1}}\) \(\newcommand {\LWRrdelimone }[2][]{\LWRrdelimtwo }\) \(\def \rdelim #1#2{\def \LWRbigdelim {#1}\LWRrdelimone }\) \(\let \symnormal \mathit \) \(\let \symliteral \mathrm \) \(\let \symbb \mathbb \) \(\let \symbbit \mathbb \) \(\let \symcal \mathcal \) \(\let \symscr \mathscr \) \(\let \symfrak \mathfrak \) \(\let \symsfup \mathsf \) \(\let \symsfit \mathit \) \(\let \symbfsf \mathbf \) \(\let \symbfup \mathbf \) \(\newcommand {\symbfit }[1]{\boldsymbol {#1}}\) \(\let \symbfcal \mathcal \) \(\let \symbfscr \mathscr \) \(\let \symbffrak \mathfrak \) \(\let \symbfsfup \mathbf \) \(\newcommand {\symbfsfit }[1]{\boldsymbol {#1}}\) \(\let \symup \mathrm \) \(\let \symbf \mathbf \) \(\let \symit \mathit \) \(\let \symsf \symsfit \) \(\let \symtt \mathtt \) \(\let \symbffrac \mathbffrac \) \(\newcommand {\mathfence }[1]{\mathord {#1}}\) \(\newcommand {\mathover }[1]{#1}\) \(\newcommand {\mathunder }[1]{#1}\) \(\newcommand {\mathaccent }[1]{#1}\) \(\newcommand {\mathbotaccent }[1]{#1}\) \(\newcommand {\mathalpha }[1]{\mathord {#1}}\) \(\def\Alpha{\unicode{x1D6E2}}\) \(\def\Beta{\unicode{x1D6E3}}\) \(\def\Gamma{\unicode{x1D6E4}}\) \(\def\Digamma{\mathit{\unicode{x03DC}}}\) \(\def\Delta{\unicode{x1D6E5}}\) \(\def\Epsilon{\unicode{x1D6E6}}\) \(\def\Zeta{\unicode{x1D6E7}}\) \(\def\Eta{\unicode{x1D6E8}}\) \(\def\Theta{\unicode{x1D6E9}}\) \(\def\Vartheta{\unicode{x1D6F3}}\) \(\def\Iota{\unicode{x1D6EA}}\) \(\def\Kappa{\unicode{x1D6EB}}\) \(\def\Lambda{\unicode{x1D6EC}}\) \(\def\Mu{\unicode{x1D6ED}}\) \(\def\Nu{\unicode{x1D6EE}}\) \(\def\Xi{\unicode{x1D6EF}}\) \(\def\Omicron{\unicode{x1D6F0}}\) \(\def\Pi{\unicode{x1D6F1}}\) \(\def\Rho{\unicode{x1D6F2}}\) \(\def\Sigma{\unicode{x1D6F4}}\) \(\def\Tau{\unicode{x1D6F5}}\) \(\def\Upsilon{\unicode{x1D6F6}}\) \(\def\Phi{\unicode{x1D6F7}}\) \(\def\Chi{\unicode{x1D6F8}}\) \(\def\Psi{\unicode{x1D6F9}}\) \(\def\Omega{\unicode{x1D6FA}}\) \(\def\alpha{\unicode{x1D6FC}}\) \(\def\beta{\unicode{x1D6FD}}\) \(\def\varbeta{\unicode{x03D0}}\) \(\def\gamma{\unicode{x1D6FE}}\) \(\def\digamma{\mathit{\unicode{x03DD}}}\) \(\def\delta{\unicode{x1D6FF}}\) \(\def\epsilon{\unicode{x1D716}}\) \(\def\varepsilon{\unicode{x1D700}}\) \(\def\zeta{\unicode{x1D701}}\) \(\def\eta{\unicode{x1D702}}\) \(\def\theta{\unicode{x1D703}}\) \(\def\vartheta{\unicode{x1D717}}\) \(\def\iota{\unicode{x1D704}}\) \(\def\kappa{\unicode{x1D705}}\) \(\def\varkappa{\unicode{x1D718}}\) \(\def\lambda{\unicode{x1D706}}\) \(\def\mu{\unicode{x1D707}}\) \(\def\nu{\unicode{x1D708}}\) \(\def\xi{\unicode{x1D709}}\) \(\def\omicron{\unicode{x1D70A}}\) \(\def\pi{\unicode{x1D70B}}\) \(\def\varpi{\unicode{x1D71B}}\) \(\def\rho{\unicode{x1D70C}}\) \(\def\varrho{\unicode{x1D71A}}\) \(\def\sigma{\unicode{x1D70E}}\) \(\def\varsigma{\unicode{x1D70D}}\) \(\def\tau{\unicode{x1D70F}}\) \(\def\upsilon{\unicode{x1D710}}\) \(\def\phi{\unicode{x1D719}}\) \(\def\varphi{\unicode{x1D711}}\) \(\def\chi{\unicode{x1D712}}\) \(\def\psi{\unicode{x1D713}}\) \(\def\omega{\unicode{x1D714}}\) \(\def\upAlpha{\unicode{x0391}}\) \(\def\upBeta{\unicode{x0392}}\) \(\def\upGamma{\unicode{x0393}}\) \(\def\upDigamma{\unicode{x03DC}}\) \(\def\upDelta{\unicode{x0394}}\) \(\def\upEpsilon{\unicode{x0395}}\) \(\def\upZeta{\unicode{x0396}}\) \(\def\upEta{\unicode{x0397}}\) \(\def\upTheta{\unicode{x0398}}\) \(\def\upVartheta{\unicode{x03F4}}\) \(\def\upIota{\unicode{x0399}}\) \(\def\upKappa{\unicode{x039A}}\) \(\def\upLambda{\unicode{x039B}}\) \(\def\upMu{\unicode{x039C}}\) \(\def\upNu{\unicode{x039D}}\) \(\def\upXi{\unicode{x039E}}\) \(\def\upOmicron{\unicode{x039F}}\) \(\def\upPi{\unicode{x03A0}}\) \(\def\upVarpi{\unicode{x03D6}}\) \(\def\upRho{\unicode{x03A1}}\) \(\def\upSigma{\unicode{x03A3}}\) \(\def\upTau{\unicode{x03A4}}\) \(\def\upUpsilon{\unicode{x03A5}}\) \(\def\upPhi{\unicode{x03A6}}\) \(\def\upChi{\unicode{x03A7}}\) \(\def\upPsi{\unicode{x03A8}}\) \(\def\upOmega{\unicode{x03A9}}\) \(\def\itAlpha{\unicode{x1D6E2}}\) \(\def\itBeta{\unicode{x1D6E3}}\) \(\def\itGamma{\unicode{x1D6E4}}\) \(\def\itDigamma{\mathit{\unicode{x03DC}}}\) \(\def\itDelta{\unicode{x1D6E5}}\) \(\def\itEpsilon{\unicode{x1D6E6}}\) \(\def\itZeta{\unicode{x1D6E7}}\) \(\def\itEta{\unicode{x1D6E8}}\) \(\def\itTheta{\unicode{x1D6E9}}\) \(\def\itVartheta{\unicode{x1D6F3}}\) \(\def\itIota{\unicode{x1D6EA}}\) \(\def\itKappa{\unicode{x1D6EB}}\) \(\def\itLambda{\unicode{x1D6EC}}\) \(\def\itMu{\unicode{x1D6ED}}\) \(\def\itNu{\unicode{x1D6EE}}\) \(\def\itXi{\unicode{x1D6EF}}\) \(\def\itOmicron{\unicode{x1D6F0}}\) \(\def\itPi{\unicode{x1D6F1}}\) \(\def\itRho{\unicode{x1D6F2}}\) \(\def\itSigma{\unicode{x1D6F4}}\) \(\def\itTau{\unicode{x1D6F5}}\) \(\def\itUpsilon{\unicode{x1D6F6}}\) \(\def\itPhi{\unicode{x1D6F7}}\) \(\def\itChi{\unicode{x1D6F8}}\) \(\def\itPsi{\unicode{x1D6F9}}\) \(\def\itOmega{\unicode{x1D6FA}}\) \(\def\upalpha{\unicode{x03B1}}\) \(\def\upbeta{\unicode{x03B2}}\) \(\def\upvarbeta{\unicode{x03D0}}\) \(\def\upgamma{\unicode{x03B3}}\) \(\def\updigamma{\unicode{x03DD}}\) \(\def\updelta{\unicode{x03B4}}\) \(\def\upepsilon{\unicode{x03F5}}\) \(\def\upvarepsilon{\unicode{x03B5}}\) \(\def\upzeta{\unicode{x03B6}}\) \(\def\upeta{\unicode{x03B7}}\) \(\def\uptheta{\unicode{x03B8}}\) \(\def\upvartheta{\unicode{x03D1}}\) \(\def\upiota{\unicode{x03B9}}\) \(\def\upkappa{\unicode{x03BA}}\) \(\def\upvarkappa{\unicode{x03F0}}\) \(\def\uplambda{\unicode{x03BB}}\) \(\def\upmu{\unicode{x03BC}}\) \(\def\upnu{\unicode{x03BD}}\) \(\def\upxi{\unicode{x03BE}}\) \(\def\upomicron{\unicode{x03BF}}\) \(\def\uppi{\unicode{x03C0}}\) \(\def\upvarpi{\unicode{x03D6}}\) \(\def\uprho{\unicode{x03C1}}\) \(\def\upvarrho{\unicode{x03F1}}\) \(\def\upsigma{\unicode{x03C3}}\) \(\def\upvarsigma{\unicode{x03C2}}\) \(\def\uptau{\unicode{x03C4}}\) \(\def\upupsilon{\unicode{x03C5}}\) \(\def\upphi{\unicode{x03D5}}\) \(\def\upvarphi{\unicode{x03C6}}\) \(\def\upchi{\unicode{x03C7}}\) \(\def\uppsi{\unicode{x03C8}}\) \(\def\upomega{\unicode{x03C9}}\) \(\def\italpha{\unicode{x1D6FC}}\) \(\def\itbeta{\unicode{x1D6FD}}\) \(\def\itvarbeta{\unicode{x03D0}}\) \(\def\itgamma{\unicode{x1D6FE}}\) \(\def\itdigamma{\mathit{\unicode{x03DD}}}\) \(\def\itdelta{\unicode{x1D6FF}}\) \(\def\itepsilon{\unicode{x1D716}}\) \(\def\itvarepsilon{\unicode{x1D700}}\) \(\def\itzeta{\unicode{x1D701}}\) \(\def\iteta{\unicode{x1D702}}\) \(\def\ittheta{\unicode{x1D703}}\) \(\def\itvartheta{\unicode{x1D717}}\) \(\def\itiota{\unicode{x1D704}}\) \(\def\itkappa{\unicode{x1D705}}\) \(\def\itvarkappa{\unicode{x1D718}}\) \(\def\itlambda{\unicode{x1D706}}\) \(\def\itmu{\unicode{x1D707}}\) \(\def\itnu{\unicode{x1D708}}\) \(\def\itxi{\unicode{x1D709}}\) \(\def\itomicron{\unicode{x1D70A}}\) \(\def\itpi{\unicode{x1D70B}}\) \(\def\itvarpi{\unicode{x1D71B}}\) \(\def\itrho{\unicode{x1D70C}}\) \(\def\itvarrho{\unicode{x1D71A}}\) \(\def\itsigma{\unicode{x1D70E}}\) \(\def\itvarsigma{\unicode{x1D70D}}\) \(\def\ittau{\unicode{x1D70F}}\) \(\def\itupsilon{\unicode{x1D710}}\) \(\def\itphi{\unicode{x1D719}}\) \(\def\itvarphi{\unicode{x1D711}}\) \(\def\itchi{\unicode{x1D712}}\) \(\def\itpsi{\unicode{x1D713}}\) \(\def\itomega{\unicode{x1D714}}\) \(\let \lparen (\) \(\let \rparen )\) \(\newcommand {\cuberoot }[1]{\,{}^3\!\!\sqrt {#1}}\,\) \(\newcommand {\fourthroot }[1]{\,{}^4\!\!\sqrt {#1}}\,\) \(\newcommand {\longdivision }[1]{\mathord {\unicode {x027CC}#1}}\) \(\newcommand {\mathcomma }{,}\) \(\newcommand {\mathcolon }{:}\) \(\newcommand {\mathsemicolon }{;}\) \(\newcommand {\overbracket }[1]{\mathinner {\overline {\ulcorner {#1}\urcorner }}}\) \(\newcommand {\underbracket }[1]{\mathinner {\underline {\llcorner {#1}\lrcorner }}}\) \(\newcommand {\overbar }[1]{\mathord {#1\unicode {x00305}}}\) \(\newcommand {\ovhook }[1]{\mathord {#1\unicode {x00309}}}\) \(\newcommand {\ocirc }[1]{\mathord {#1\unicode {x0030A}}}\) \(\newcommand {\candra }[1]{\mathord {#1\unicode {x00310}}}\) \(\newcommand {\oturnedcomma }[1]{\mathord {#1\unicode {x00312}}}\) \(\newcommand {\ocommatopright }[1]{\mathord {#1\unicode {x00315}}}\) \(\newcommand {\droang }[1]{\mathord {#1\unicode {x0031A}}}\) \(\newcommand {\leftharpoonaccent }[1]{\mathord {#1\unicode {x020D0}}}\) \(\newcommand {\rightharpoonaccent }[1]{\mathord {#1\unicode {x020D1}}}\) \(\newcommand {\vertoverlay }[1]{\mathord {#1\unicode {x020D2}}}\) \(\newcommand {\leftarrowaccent }[1]{\mathord {#1\unicode {x020D0}}}\) \(\newcommand {\annuity }[1]{\mathord {#1\unicode {x020E7}}}\) \(\newcommand {\widebridgeabove }[1]{\mathord {#1\unicode {x020E9}}}\) \(\newcommand {\asteraccent }[1]{\mathord {#1\unicode {x020F0}}}\) \(\newcommand {\threeunderdot }[1]{\mathord {#1\unicode {x020E8}}}\) \(\newcommand {\Bbbsum }{\mathop {\unicode {x2140}}\limits }\) \(\newcommand {\oiint }{\mathop {\unicode {x222F}}\limits }\) \(\newcommand {\oiiint }{\mathop {\unicode {x2230}}\limits }\) \(\newcommand {\intclockwise }{\mathop {\unicode {x2231}}\limits }\) \(\newcommand {\ointclockwise }{\mathop {\unicode {x2232}}\limits }\) \(\newcommand {\ointctrclockwise }{\mathop {\unicode {x2233}}\limits }\) \(\newcommand {\varointclockwise }{\mathop {\unicode {x2232}}\limits }\) \(\newcommand {\leftouterjoin }{\mathop {\unicode {x27D5}}\limits }\) \(\newcommand {\rightouterjoin }{\mathop {\unicode {x27D6}}\limits }\) \(\newcommand {\fullouterjoin }{\mathop {\unicode {x27D7}}\limits }\) \(\newcommand {\bigbot }{\mathop {\unicode {x27D8}}\limits }\) \(\newcommand {\bigtop }{\mathop {\unicode {x27D9}}\limits }\) \(\newcommand {\xsol }{\mathop {\unicode {x29F8}}\limits }\) \(\newcommand {\xbsol }{\mathop {\unicode {x29F9}}\limits }\) \(\newcommand {\bigcupdot }{\mathop {\unicode {x2A03}}\limits }\) \(\newcommand {\bigsqcap }{\mathop {\unicode {x2A05}}\limits }\) \(\newcommand {\conjquant }{\mathop {\unicode {x2A07}}\limits }\) \(\newcommand {\disjquant }{\mathop {\unicode {x2A08}}\limits }\) \(\newcommand {\bigtimes }{\mathop {\unicode {x2A09}}\limits }\) \(\newcommand {\modtwosum }{\mathop {\unicode {x2A0A}}\limits }\) \(\newcommand {\sumint }{\mathop {\unicode {x2A0B}}\limits }\) \(\newcommand {\intbar }{\mathop {\unicode {x2A0D}}\limits }\) \(\newcommand {\intBar }{\mathop {\unicode {x2A0E}}\limits }\) \(\newcommand {\fint }{\mathop {\unicode {x2A0F}}\limits }\) \(\newcommand {\cirfnint }{\mathop {\unicode {x2A10}}\limits }\) \(\newcommand {\awint }{\mathop {\unicode {x2A11}}\limits }\) \(\newcommand {\rppolint }{\mathop {\unicode {x2A12}}\limits }\) \(\newcommand {\scpolint }{\mathop {\unicode {x2A13}}\limits }\) \(\newcommand {\npolint }{\mathop {\unicode {x2A14}}\limits }\) \(\newcommand {\pointint }{\mathop {\unicode {x2A15}}\limits }\) \(\newcommand {\sqint }{\mathop {\unicode {x2A16}}\limits }\) \(\newcommand {\intlarhk }{\mathop {\unicode {x2A17}}\limits }\) \(\newcommand {\intx }{\mathop {\unicode {x2A18}}\limits }\) \(\newcommand {\intcap }{\mathop {\unicode {x2A19}}\limits }\) \(\newcommand {\intcup }{\mathop {\unicode {x2A1A}}\limits }\) \(\newcommand {\upint }{\mathop {\unicode {x2A1B}}\limits }\) \(\newcommand {\lowint }{\mathop {\unicode {x2A1C}}\limits }\) \(\newcommand {\bigtriangleleft }{\mathop {\unicode {x2A1E}}\limits }\) \(\newcommand {\zcmp }{\mathop {\unicode {x2A1F}}\limits }\) \(\newcommand {\zpipe }{\mathop {\unicode {x2A20}}\limits }\) \(\newcommand {\zproject }{\mathop {\unicode {x2A21}}\limits }\) \(\newcommand {\biginterleave }{\mathop {\unicode {x2AFC}}\limits }\) \(\newcommand {\bigtalloblong }{\mathop {\unicode {x2AFF}}\limits }\) \(\newcommand {\arabicmaj }{\mathop {\unicode {x1EEF0}}\limits }\) \(\newcommand {\arabichad }{\mathop {\unicode {x1EEF1}}\limits }\)

2.4 Problems

Drawing and Animating Julia Sets

Exercise 2.5.Julia sets are a family of fractals that are closely related to the Mandelbrot set. Both the Mandelbrot set and Julia sets are defined by repeated application of \(z\mapsto z^2+c\), but they differ in which variable is kept constant: For the Mandelbrot set, we use a fixed starting point \(z_0=0\) and study the escape time as a a function of the parameter \(c\), whereas for Julia sets we keep \(c\) constant and study the escape time as a function of the starting value \(z_0\). In contrast to the Mandelbrot set, which is unique, there are infinitely many Julia sets, one for every possible choice of \(c\); two examples are shown in Fig. 2.7.

(image) (image)

Figure 2.7 Visualization of two Julia sets. The left image corresponds to \(c=-0.411+ 0.587\I \) and the right one to \(c=-0.2+0.67015\I \).

Julia sets can be visualized by dividing a region of the complex plane into pixels, taking the center of each pixel as the starting point \(z_0\), and coloring the pixel according to the escape time of the trajectory starting at \(z_0\). Again, numbers with an infinite escape time are said to lie inside the Julia set and are usually colored black, and all other pixels are colored by mapping their escape time to a color palette.

  • a) Write a program that computes and displays Julia sets.

Since Julia sets depend on a continuous parameter \(z_0\), they can be animated by moving \(z_0\) along a line, a circle, or another smooth curve and creating a movie from the resulting images.

  • b) Extend your program to generate animations of the Julia set, for example by generating a sequence of images.

The Game of Life

Exercise 2.6. Fractals are not the only example of simple rules that give rise to complex behavior. Another example is the Game of Life, or simply Life. The game is played on a rectangular grid of cells, each of which represents a simple life form that can be either dead or alive. The Game of Life starts with an initial population of cells and simulates its evolution over multiple generations. Each cell is influenced by its eight direct neighbors

The evolution of cells over time is governed by the following rules:

  • A living cell survives if there are exactly two or three other living cells in its neighborhood.

  • A living cell dies from isolation if there fewer than two living cells in its neighborhood and from overpopulation if there are more than four living cells.

  • A dead cell becomes alive if there are exactly three living cells in its neighborhood.

Even though the evolution of individual cells in Life is governed by a few simple rules, the behavior of multiple interacting cells can be surprisingly complex. We call an arrangement of cells with interesting properties a life form. One of the simplest life forms is the blinker, which consists of three active cells in a row, and it continually alternates between a horizontal and a vertical configuration:

Another important life form is the glider, which consists of five cells that slowly move across the board:

Every four iterations the glider advances one step to the right and one step down. (Gliders that move along the three other diagonals can be obtained by rotating the initial configuration of cells.) Life forms that move on their own are called spaceships, and the glider is the smallest possible spaceship in Life.

In theory, the grid of cells extends in all directions and life forms can grow infinitely large, but when implementing the Game of Life on a computer, we need to store the game’s state in a finite amount of memory. One common approach is to simulate an infinite board by periodically repeating a finite board in all directions. With such a periodic board, a glider that crosses one edge reappears at the opposite edge.

  • a) Implement the Game of Life. Choose a data structure for representing the grid of cells and implement methods for reading and writing the state of individual cells. Make the board periodic.

  • b) Study the evolution of the life forms shown in the following image and describe their behavior.

  • c) Consider all the life forms that consist of \(n\) living cells in a row. For \(n=3\) you obtain the blinker we discussed above. Study and describe the behavior of the other life forms with \(n\) between 1 and \(10\).

One of the most important discoveries made about the Game of Life is that it is Turing-complete, which means we can construct life forms that can perform any kind of computation — at least theoretically. The derivation of this fascinating result is non-trivial, but it’s easy to see how simple logical functions can be implemented in Life. One of the main ideas is to use streams of gliders to encode and exchange information between different parts of the “computer” and use specialized life forms to operate on these gliders.

Figure 2.8 An arrangement of four gliders advancing from the top right and a so-called glider gun positioned in the lower-left corner.
  • d) Figure 2.8 shows an arrangement of four gliders that are advancing diagonally from the top-right corner, and a device called a glider gun that is placed in the lower-left corner. Study the evolution of the configuration of cells shown in Fig. 2.8 over the first few hundred generations in a sufficiently large domain. What does the Game of Life “compute” for this input?