> 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/uk/dokladni-statti/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md). # LaTeX потужніший, ніж ви думаєте — обчислення чисел Фібоначчі та повнота за Тюрінгом **Автор: Роберт Мурріш (квітень 2012 (відредаговано Overleaf у квітні 2023))** LaTeX — потужний інструмент. Насправді настільки потужний, що його можна використовувати для значно більшого, ніж розмітка документів. LaTeX — [Тюрінг-повний](https://en.wikipedia.org/wiki/Turing_completeness); тобто його можна запрограмувати так, щоб обчислювати майже що завгодно. Щоб продемонструвати універсальні можливості програмування LaTeX, розглянемо приклад, який обчислює перші числа Фібоначчі. Хоча це й не є доказом Тюрінг-повноти, це добрий приклад повного алгоритму, реалізованого в LaTeX. ### Числа Фібоначчі Кожне число у послідовності Фібоначчі є сумою двох попередніх членів послідовності, причому перші два члени визначено як 1, щоб задати початкову точку. Ми можемо написати нову команду для обчислення цих чисел. Почнімо з того, що вирішимо, як може виглядати виклик нашої ще не написаної команди: ```latex \fibonacci{10} ``` Коли цю команду викликають із нашого документа LaTeX, вона має вивести список `n` чисел Фібоначчі (де `n=10` у прикладі виклику тут). Ось код `\fibonacci` команди (тобто макроса LaTeX). Розгляньмо, як вона працює. ```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} ``` [Відкрити цей приклад в Overleaf](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) Спершу ми налаштовуємо кілька змінних, які використаємо пізніше. Команда `\newcount` надає нам змінну, яку можна використовувати для зберігання цілого числа; тут ми створюємо чотири: `\fcnt`, `\fone`, `\ftwo` та `\temp`. Варто зазначити, що це не нові змінні; радше це псевдоніми для наявних лічильників. [Лічильники LaTeX](/latex/uk/formatuvannya/10-counters.md) можна використовувати безпосередньо, як у `\count0`, `\count1`, тощо. Але надання їм імен запобігає запису в лічильник, який уже використовується. Якщо вам цікаво, замініть одну зі змінних у цьому коді на `\count0`, і номери сторінок будуть неправильними до кінця документа. Далі в нас є `\fibonacci` команда. Ми створюємо її за допомогою `\newcommand`, якій передаємо назву, кількість аргументів і код TeX, що оброблятиметься як аргументи. Для цієї команди ми приймаємо один аргумент — кількість чисел Фібоначчі, які треба вивести. Тіло цієї команди просте: ми задаємо початкові значення для наших змінних, виводимо перші два числа Фібоначчі (оскільки їх не потрібно обчислювати), а потім викликаємо `\fibloop`, яка виконає основну роботу з обчисленнями. Команда `\fibloop` оголошується так само, але ключова частина цієї команди — це спосіб її циклічного виконання. Ми використовуємо команду під назвою `\next`, ініціалізовану значенням `\fibloop` у `\fibonacci`, і використовувану в `\fibloop` для керування циклом. `\fibloop` повторюватиметься, доки `\next` не буде змінено кодом усередині самої команди `\fibloop` . Ми хочемо виконати цикл лише `n` разів, тож використовуємо `\ifnum` умову, яка перевіряє значення нашого лічильника (`\fcnt`) і якщо воно ще не досягло порогового значення 0, `\fcnt` зменшується на одиницю щоразу, коли цикл повторюється. Якщо умову виконано, ми встановлюємо `\next` на `\\relax`, що не дасть `\fibloop` повторюватися — фінальна `\next` команда нічого не робить, і цикл завершується. Інші команди в цьому блоці обчислюють наступне число Фібоначчі в послідовності та оновлюють значення змінних, щоб вони були готові до наступного проходу. Команда `\the\ftwo` виводить значення поточного числа Фібоначчі в документ, і ви також помітите кому та пробіл у верхній частині `\fibloop` команди, яка використовується для розділення кожного значення. #### Результат Найпростіший спосіб побачити цей код у дії — запустити його в Overleaf за допомогою **Відкрити цей приклад в Overleaf** посилання внизу області відображення коду. Послідовність Фібоначчі зростає швидко, тож будь-яке `n>44` призведе до переповнення цілого числа в цій конкретній реалізації. ### Куди рухатися далі? Як неформальний доказ того, що LaTeX є Тюрінг-повним, я наведу наведений нижче код, який є швидкою й не надто акуратною реалізацією [елемента 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 } ``` Елементи NAND (а також NOR) мають цікаву властивість: будь-який інший логічний елемент можна побудувати, використавши лише цей один тип елемента. З базових логічних елементів можна сконструювати засувки, тригери та пам’ять. Це складові універсального комп’ютера. Ви можете перевірити цей елемент NAND для кожного з його чотирьох можливих входів за допомогою такого прикладу, який можна відкрити в Overleaf. ```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} ``` [Відкрити цей приклад в Overleaf](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) Знання того, що LaTeX є Тюрінг-повним, відкриває світ можливостей. Такий код часто використовують у внутрішній частині LaTeX для таких речей, як відстеження номерів сторінок і рисунків та визначення того, де розміщувати плаваючі елементи. Це інструмент, який можна використати собі на користь, щоб спростити складні макети документів. На завершення цього допису я залишу вам додаткові матеріали для читання про приклади програмування в LaTeX і машини Тюрінга. #### Приклади програмування в LaTeX * [Множина Мандельброта в LaTeX](http://warp.povusers.org/MandScripts/latex.html) . Особлива подяка за цей приклад; цей код був корисним зразком під час написання моєї команди Fibonacci. * [Машина Тюрінга в LaTeX: продовження](http://pbelmans.ncag.info/blog/2010/12/12/a-turing-machine-in-latex-follow-u/) Примітка: під час перенесення цієї статті до іншої системи розміщення контенту ми помітили, що сайт, згаданий в оригінальній статті ( був уже недоступний, тож ми замінили це посилання статтею-продовженням іншого автора. * [Вікікнига про команди TeX](http://en.wikibooks.org/wiki/Category:TeX) * [LaTeX у програмному конкурсі](http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html). Контролер марсохода в LaTeX обійшов роботи, написані кількома більш поширеними мовами програмування. ### Машини Тюрінга в неочікуваних місцях * [Гра життя Конвея є Тюрінг-повною](http://rendell-attic.org/gol/utm/index.htm). Ось реалізація машини Тюрінга. * [Правило 110](http://en.wikipedia.org/wiki/Rule_110) — це одновимірний клітинний автомат, який є Тюрінг-повним. * Minecraft (відеогра) є Тюрінг-повним. Було створено кілька прикладів, тож наступне посилання веде лише на [сторінку відповідних результатів пошуку на 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/uk/dokladni-statti/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.