> 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/ru/podrobnye-stati/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/ru/formatirovanie/10-counters.md) можно использовать напрямую, например как `\count0`, `\count1`, и т. д., но присвоение им имён позволяет избежать записи в уже используемый счётчик. Если вам интересно, замените одну из переменных в этом коде на `\count0`, и номера страниц будут неверными до конца документа. Далее у нас есть `\fibonacci` команда `\newcommand`Мы создаём её с помощью `\fibloop`, которому передаём имя, число аргументов и код TeX, который будет обрабатываться как аргументы. Для этой команды мы принимаем один аргумент — количество чисел Фибоначчи, которое нужно вывести. Содержимое этой команды просто: мы задаём начальные значения для наших переменных, печатаем первые два числа Фибоначчи (поскольку их не нужно вычислять), а затем вызываем Команда `\fibloop` объявлена аналогичным образом, но ключевая часть этой команды — то, как она выполняет цикл. Мы используем команду под названием `\next`, инициализированную значением `\fibloop` внутри `\fibonacci`, и используемую внутри `\fibloop` для управления циклом. `\fibloop` будет повторяться, пока `\next` не будет изменён кодом внутри `\fibloop` самой команды. `n` раз `\ifnum` оператор`\fcnt`(\fcnt) `\fcnt` уменьшается на единицу каждый раз, когда цикл повторяется. Если условие выполняется, мы устанавливаем `\next` на `\relax`\let\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) . Особая благодарность за этот пример; этот код оказался полезным образцом при написании моей команды Фибоначчи. * [Машина Тьюринга в 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/ru/podrobnye-stati/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.