> For the complete documentation index, see [llms.txt](https://ayakaleaf-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://ayakaleaf-pro.ayaka.space/latex/zh-cn/shen-du-wen-zhang/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md).

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

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

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 命令为我们提供一个可以用来存储整数的变量；这里，我们创建四个： `\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
    \fi
   \else 1
\fi
}
```

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
    \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/) 注：在将这篇文章移植到另一个内容托管系统时，我们注意到原始文章中引用的网站（<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://ayakaleaf-pro.ayaka.space/latex/zh-cn/shen-du-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.