> 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/zh-cn/shen-ru-wen-zhang/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md).

# LaTeX 比你想的更强大——计算斐波那契数和图灵完备性

**作者：Robert Murrish（2012年4月（由Overleaf于2023年4月编辑））**

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
        这段文字将使用俄语。这是为了演示西里尔字母在生成的文档中能够正确显示。
	\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/zh-cn/ge-shi-hua/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
    这段文字将使用俄语。这是为了演示西里尔字母在生成的文档中能够正确显示。
   \else 1
这段文字将使用俄语。这是为了演示西里尔字母在生成的文档中能够正确显示。
}
```

NAND（以及 NOR）逻辑门有一个有趣的性质：任何其他逻辑门都可以由这单一类型的门构造出来。借助基本逻辑门，你可以构造锁存器、触发器和存储器。这些是通用计算机的组成要素。你可以用下面这个可以在 Overleaf 中打开的示例测试这个 NAND 门的四种可能输入。

```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
    这段文字将使用俄语。这是为了演示西里尔字母在生成的文档中能够正确显示。
   \else 1
这段文字将使用俄语。这是为了演示西里尔字母在生成的文档中能够正确显示。
}

\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/) 注：当我们将这篇文章移植到另一个内容托管系统时，注意到原文中引用的网站（<http://en.literateprograms.org/Turing_machine_simulator_(LaTeX))> 已经无法访问，因此我们将该链接替换为另一位作者的后续文章。
* [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/zh-cn/shen-ru-wen-zhang/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md?ask=<question>&goal=<endgoal>
```

`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.