> 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/ja/xiang-xi-ji-shi/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 で実装された完全なアルゴリズムのよい例です。 ### フィボナッチ数 フィボナッチ数列の各数は、数列の直前の2項の和で、最初の2項は出発点として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` コマンドは整数を保持するための変数を作ります。ここでは4つ作成します: `\fcnt`, `\fone`, `\ftwo` や `\temp`。なお、これらは新しい変数ではなく、既存のカウンタへの別名のようなものです。 [LaTeX のカウンタ](/latex/ja/shu-shi-she-ding/10-counters.md) は `\count0`, `\count1`などのように直接使えますが、名前を付けておけば、すでに使用中のカウンタに書き込んでしまうのを防げます。興味があれば、このコード中の変数の一つを `\count0`に置き換えてみてください。すると、文書の残りのページ番号が誤って表示されます。 次に `\fibonacci` コマンドがあります。これを `\newcommand`を使って作成します。これには、名前、引数の数、そして引数として処理するTeXコードを与えます。このコマンドでは、出力するフィボナッチ数の個数という1つの引数を受け取ります。このコマンドの内容は単純です。変数の初期値を設定し、最初の2つのフィボナッチ数を出力し（計算する必要がないため）、その後 `\fibloop`を呼び出します。これが計算の大部分を担います。 コマンド `\fibloop` は同様に宣言されていますが、このコマンドの重要な部分はループの仕組みです。 `\next`というコマンドを使います。これは `\fibloop` の内部で `\fibonacci`で初期化され、 `\fibloop` の中でループ制御に使われます。 `\fibloop` は `\next` によって変更されるまで繰り返されます。 `\fibloop` コマンド自体の内部のコード `n` 回だけループさせたいので、 `\ifnum` 文を使ってカウンタ（`\fcnt`）の値を確認し、しきい値である0に達していなければ、 `\fcnt` はループが繰り返されるたびに1ずつ減算されます。条件が満たされると、 `\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）論理ゲートには、他のどんな論理ゲートもこの1種類のゲートだけで構成できるという興味深い性質があります。基本的な論理ゲートから、ラッチ、フリップフロップ、メモリを構築できます。これらが汎用コンピュータの材料です。Overleafで開ける以下の例を使って、このNANDゲートを4通りの入力それぞれでテストできます。 ```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) 。この1つには特に感謝します。このコードは、私がフィボナッチコマンドを書いている間に役立つ例でした。 * [LaTeX におけるチューリングマシン：続編](http://pbelmans.ncag.info/blog/2010/12/12/a-turing-machine-in-latex-follow-u/) 注: この記事を別のコンテンツホスティングシステムに移植する際、元の記事で参照されていたサイト（ はもはやアクセスできなくなっていたため、そのリンクを別の著者による続編記事に置き換えました。 * [TeX コマンドの Wikibook](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) はチューリング完全な1次元セルオートマトンです。 * 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/ja/xiang-xi-ji-shi/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.