> For the complete documentation index, see [llms.txt](https://overleaf-pro.ayaka.space/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://overleaf-pro.ayaka.space/latex/cs/clanky-do-hloubky/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md). # LaTeX je mocnější, než si myslíte – výpočet Fibonacciho čísel a Turingova úplnost **Autor: Robert Murrish (duben 2012 (upraveno společností Overleaf v dubnu 2023))** LaTeX je mocný nástroj. Ve skutečnosti natolik mocný, že jej lze použít k mnohem více než jen k sazební úpravě dokumentů. LaTeX je [Turingovsky úplný](https://en.wikipedia.org/wiki/Turing_completeness); tedy lze jej naprogramovat tak, aby počítal téměř cokoli. Abychom demonstrovali obecné programovací schopnosti LaTeXu, podíváme se na příklad, který vypočítává první Fibonacciho čísla. I když to není důkaz Turingovy úplnosti, je to dobrý příklad kompletního algoritmu implementovaného v LaTeXu. ### Fibonacciho čísla Každé číslo ve Fibonacciho posloupnosti je součtem předchozích dvou členů posloupnosti, přičemž první dva členy jsou definovány jako 1, aby poskytly výchozí bod. Můžeme napsat nový příkaz, který tato čísla vypočítá. Začněme tím, že se rozhodneme, jak by mohlo vypadat volání našeho dosud nenapsaného příkazu: ```latex \fibonacci{10} ``` Když je tento příkaz zavolán z našeho dokumentu LaTeX, měl by vytvořit seznam `n` Fibonacciho čísel (kde `n=10` v tomto příkladu volání). Zde je kód pro příkaz `\fibonacci` (tj. makro LaTeXu). Podívejme se, jak funguje. ```latex \documentclass{article} \begin{document} \newcount\temp \newcount\fone \newcount\ftwo \newcount\fcnt \newcommand{\fibonacci}[1]{% \fcnt=#1 \fone=1 \ftwo=1 \temp=0 \the\fone, \the\ftwo \let\next=\fibloop \fibloop } \def\fibloop{, % \temp=\fone \fone=\ftwo \advance\ftwo by \temp \ifnum\fcnt=0 \let\next=\relax \else \advance\fcnt by -1 \fi \the\ftwo \next } (\fibonacci{10}) \end{document} ``` [Otevřete tento příklad v Overleafu](https://www.overleaf.com/docs?engine=pdflatex\&snip_name=Fibonacci+sequence+in+LaTeX\&snip=%5Cdocumentclass%7Barticle%7D%0A%5Cbegin%7Bdocument%7D%0A%0A%5Cnewcount%5Ctemp%0A%5Cnewcount%5Cfone%0A%5Cnewcount%5Cftwo%0A%5Cnewcount%5Cfcnt%0A%0A%5Cnewcommand%7B%5Cfibonacci%7D%5B1%5D%7B%25%0A%09%5Cfcnt%3D%231%0A%09%5Cfone%3D1%0A%09%5Cftwo%3D1%0A%09%5Ctemp%3D0%0A%09%5Cthe%5Cfone%2C+%5Cthe%5Cftwo%0A%09%5Clet%5Cnext%3D%5Cfibloop%0A%09%5Cfibloop%0A%7D%0A%0A%5Cdef%5Cfibloop%7B%2C+%25%0A%09%5Ctemp%3D%5Cfone%0A%09%5Cfone%3D%5Cftwo%0A%09%5Cadvance%5Cftwo+by+%5Ctemp%0A%09%5Cifnum%5Cfcnt%3D0%0A++++++++++++%5Clet%5Cnext%3D%5Crelax%0A++++++++%5Celse%0A++++++++++++%5Cadvance%5Cfcnt+by+-1%0A++++++++%5Cfi%0A%09%5Cthe%5Cftwo%0A%09%5Cnext%0A%7D%0A%0A%28%5Cfibonacci%7B10%7D%29%0A%5Cend%7Bdocument%7D) Nejprve nastavíme několik proměnných, které budeme později používat. Příkaz `\newcount` nám dává proměnnou, kterou můžeme použít k uložení celého čísla; zde vytváříme čtyři: `\fcnt`, `\fone`, `\ftwo` a `\temp`. Stojí za zmínku, že to nejsou nové proměnné; jsou spíše aliasy pro existující čítače. [Čítače LaTeXu](/latex/cs/formatovani/10-counters.md) lze používat přímo, například jako `\count0`, `\count1`, atd., ale přiřazení názvů nám brání zapisovat do čítače, který je už používán. Pokud jste zvědaví, nahraďte jednu z proměnných v tomto kódu za `\count0`, a čísla stránek budou po zbytek dokumentu nesprávná. Dále tu máme `\fibonacci` příkaz. Vytvoříme jej pomocí `\newcommand`, kterému předáme název, počet argumentů a TeXový kód ke zpracování jako argumenty. U tohoto příkazu přijímáme jediný argument, počet Fibonacciho čísel, která se mají vypsat. Obsah tohoto příkazu je jednoduchý: nastavíme počáteční hodnoty našich proměnných, vypíšeme první dvě Fibonacciho čísla (protože je není třeba počítat), a poté zavoláme `\fibloop`, který odvede většinu práce při našich výpočtech. Příkaz `\fibloop` je deklarován stejným způsobem, ale klíčovou součástí tohoto příkazu je způsob, jakým se opakuje. Používáme příkaz nazvaný `\next`, inicializovaný na `\fibloop` uvnitř `\fibonacci`, a používaný uvnitř `\fibloop` k řízení opakování. `\fibloop` se bude opakovat, dokud `\next` není změněn kódem uvnitř `\fibloop` samotného příkazu. Chceme se opakovat jen `n` krát, takže používáme `\ifnum` příkaz, který kontroluje hodnotu našeho čítače (`\fcnt`) a pokud ještě nedosáhl prahové hodnoty 0, `\fcnt` se při každém opakování smyčky sníží. Je-li podmínka splněna, nastavíme `\next` na `\relax`, což zabrání `\fibloop` dalšímu opakování — závěrečný `\next` příkaz nedělá nic a smyčka se ukončí. Ostatní příkazy v tomto bloku vypočítají další Fibonacciho číslo v posloupnosti a aktualizují hodnoty proměnných tak, aby byly připraveny na další průchod. Příkaz `\the\ftwo` vypíše hodnotu aktuálního Fibonacciho čísla do dokumentu a všimnete si také čárky a mezery na začátku `\fibloop` příkazu, který slouží k oddělení jednotlivých hodnot. #### Výsledek Nejjednodušší způsob, jak vidět tento kód v akci, je spustit jej v Overleafu pomocí **Otevřete tento příklad v Overleafu** odkazu ve spodní části zobrazení kódu. Fibonacciho posloupnost roste rychle, takže jakékoli `n>44` způsobí v této konkrétní implementaci přetečení celého čísla. ### Kam dál? Jako neformální důkaz, že LaTeX je Turingovsky úplný, uvádím následující kód, což je narychlo a provizorně napsaná implementace [brány NAND](https://en.wikipedia.org/wiki/NAND_gate): ```latex \newcount\nanone \newcount\nantwo \newcommand{\nand}[2]{% \nanone=#1 \nantwo=#2 \ifnum\nanone=\nantwo \ifnum\nanone=0\relax 1 \else 0 \fi \else 1 \fi } ``` Brány NAND (a také NOR) mají zajímavou vlastnost, že pomocí jediného tohoto typu brány lze vytvořit libovolnou jinou logickou bránu. Ze základních logických bran lze sestavit zámky, klopné obvody a paměť. To jsou stavební kameny univerzálního počítače. Tuto bránu NAND si můžete otestovat pro všechny její čtyři možné vstupy pomocí následujícího příkladu, který si můžete otevřít v Overleafu. ```latex \documentclass{article} \begin{document} \newcount\nanone \newcount\nantwo \newcommand{\nand}[2]{% \nanone=#1 \nantwo=#2 \ifnum\nanone=\nantwo \ifnum\nanone=0\relax 1 \else 0 \fi \else 1 \fi } \nand{0}{0} \nand{0}{1} \nand{1}{0} \nand{1}{1} \end{document} ``` [Otevřete tento příklad v Overleafu](https://www.overleaf.com/docs?engine=pdflatex\&snip_name=NAND+gate+in+LaTeX\&snip=%5Cdocumentclass%7Barticle%7D%0A%5Cbegin%7Bdocument%7D%0A%0A%5Cnewcount%5Cnanone%0A%5Cnewcount%5Cnantwo%0A%0A%5Cnewcommand%7B%5Cnand%7D%5B2%5D%7B%25%0A%5Cnanone%3D%231%0A%5Cnantwo%3D%232%0A++%5Cifnum%5Cnanone%3D%5Cnantwo%0A++++%5Cifnum%5Cnanone%3D0%5Crelax+1%0A++++++%5Celse+0%0A++++%5Cfi%0A+++%5Celse+1%0A%5Cfi%0A%7D%0A%0A%5Cnand%7B0%7D%7B0%7D%0A%5Cnand%7B0%7D%7B1%7D%0A%5Cnand%7B1%7D%7B0%7D%0A%5Cnand%7B1%7D%7B1%7D%0A%5Cend%7Bdocument%7D) Vědomí, že LaTeX je Turingovsky úplný, otevírá svět možností. Kód jako tento je v backendu LaTeXu běžný pro věci, jako je sledování čísel stránek a obrázků a rozhodování o umístění plovoucích objektů. Je to nástroj, který můžete využít ve svůj prospěch ke zjednodušení složitých rozvržení dokumentů. Na závěr tohoto příspěvku vám zanechám další čtení o příkladech programování v LaTeXu a Turingových strojích. #### Příklady programování v LaTeXu * [Mandelbrotova množina v LaTeXu](http://warp.povusers.org/MandScripts/latex.html) . Zvláštní poděkování patří tomuto; tento kód byl užitečným příkladem při psaní mého Fibonacciho příkazu. * [Turingův stroj v LaTeXu: pokračování](http://pbelmans.ncag.info/blog/2010/12/12/a-turing-machine-in-latex-follow-u/) Pozn.: Při převodu tohoto článku na jiný systém pro hostování obsahu jsme si všimli, že stránka uvedená v původním článku ( už nebyla dostupná, takže jsme tento odkaz nahradili pokračovacím článkem jiného autora. * [Wikikniha o příkazech TeX](http://en.wikibooks.org/wiki/Category:TeX) * [LaTeX v programátorské soutěži](http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html). Ovladač marsovského roveru v LaTeXu porazil příspěvky v několika běžnějších programovacích jazycích. ### Turingovy stroje na nečekaných místech * [Conwayova hra života je Turingovsky úplná](http://rendell-attic.org/gol/utm/index.htm). Zde je implementace Turingova stroje. * [Pravidlo 110](http://en.wikipedia.org/wiki/Rule_110) je jednorozměrný buněčný automat, který je Turingovsky úplný. * Minecraft (videohra) je Turingovsky úplný. Bylo vytvořeno několik příkladů, takže následující odkaz vede pouze na [stránku s relevantními výsledky vyhledávání na YouTube](http://www.youtube.com/results?search_query=minecraft+turing+machine) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://overleaf-pro.ayaka.space/latex/cs/clanky-do-hloubky/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.