> 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-tw/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
        \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/zh-tw/ge-shi-hua/10-counters.md) 可以直接使用，例如 `\count0`, `\count1`等等，但為它們命名可以避免我們對已在使用中的計數器寫入。如果你有興趣，可以把這段程式碼中的其中一個變數改成 `\count0`，那麼之後文件其餘部分的頁碼就會錯誤。

接著是 `\fibonacci` 指令。我們用 `\newcommand`來建立它，並提供名稱、參數數量，以及要作為參數處理的 TeX 程式碼。對這個指令而言，我們接受單一參數，也就是要輸出的斐波那契數數量。這個指令的內容很簡單：我們先設定變數的初始值，輸出前兩個斐波那契數字（因為它們不需要計算），然後呼叫 `\fibloop`，它將負責完成計算的大部分工作。

指令 `\fibloop` 的宣告方式相同，但這個指令的關鍵在於它如何迴圈。我們使用一個名為 `\next`的指令，它在 `\fibloop` 中被初始化，並在 `\fibonacci`中使用，以控制迴圈。 `\fibloop` 將會重複，直到 `\fibloop` 被 `\next` 指令內的程式碼改變為止。我們只想迴圈 `\fibloop` 次，所以我們使用一個 `n` \ifnum `敘述來檢查我們的計數器值（` ）是否尚未達到 0 這個門檻值，`\fcnt`會在每次迴圈重複時遞減。如果條件成立，我們就把 `\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 中的 Mandlebrot 集合](http://warp.povusers.org/MandScripts/latex.html) 。特別感謝這一個；在撰寫我的 Fibonacci 指令時，這段程式碼是一個很有幫助的範例。
* [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-tw/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.