> 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/no/dybdeartikler/31-latex-is-more-powerful-than-you-think-computing-the-fibonacci-numbers-and-turing-completeness.md). # LaTeX er kraftigere enn du tror – beregning av Fibonacci-tallene og Turing-kompletthet **Forfatter: Robert Murrish (april 2012 (redigert av Overleaf i april 2023))** LaTeX er et kraftig verktøy. Så kraftig, faktisk, at det kan brukes til mye mer enn dokumentoppmerking. LaTeX er [Turing-komplett](https://en.wikipedia.org/wiki/Turing_completeness); det vil si at det kan programmeres til å beregne nesten hva som helst. For å demonstrere LaTeXs programmeringsevner til generell bruk, skal vi se på et eksempel som beregner de første Fibonacci-tallene. Selv om dette ikke er et bevis på Turing-kompletthet, er det et godt eksempel på en fullstendig algoritme implementert i LaTeX. ### Fibonacci-tallene Hvert tall i Fibonacci-sekvensen er summen av de to foregående leddene i sekvensen, med de to første leddene definert som 1 for å gi et utgangspunkt. Vi kan skrive en ny kommando for å beregne disse tallene. La oss begynne med å bestemme hvordan et kall til vår ennå ikke skrevne kommando kan se ut: ```latex \fibonacci{10} ``` Når denne kommandoen kalles fra LaTeX-dokumentet vårt, bør den produsere en liste over `n` Fibonacci-tall (der `n=10` i eksempelkallet her). Her er koden for `\fibonacci` kommandoen (dvs. LaTeX-makroen). La oss se på hvordan den fungerer. ```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} ``` [Åpne dette eksemplet i 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) Først setter vi opp noen variabler vi skal bruke senere. Kommandoen `\newcount` gir oss en variabel vi kan bruke til å holde et heltall; her oppretter vi fire: `\fcnt`, `\fone`, `\ftwo` og `\temp`. Det er verdt å nevne at dette ikke er nye variabler; de er mer som aliaser for eksisterende tellere. [LaTeX-tellere](/latex/no/formatering/10-counters.md) kan brukes direkte slik som i `\count0`, `\count1`, osv., men å gi dem navn hindrer oss i å skrive til en teller som allerede er i bruk. Hvis du er nysgjerrig, kan du erstatte en av variablene i denne koden med `\count0`, og sidenummerne vil være feil resten av dokumentet. Vi har deretter `\fibonacci` kommandoen. Vi oppretter den med `\newcommand`, som vi gir navnet, antall argumenter og TeX-kode som skal behandles som argumenter. For denne kommandoen aksepterer vi ett enkelt argument, antallet Fibonacci-tall som skal skrives ut. Innholdet i denne kommandoen er enkelt: vi setter startverdier for variablene våre, skriver ut de to første Fibonacci-tallene (siden de ikke trenger å beregnes), og kaller deretter `\fibloop`, som vil gjøre grovarbeidet for beregningene våre. Kommandoen `\fibloop` er deklarert på samme måte, men en nøkkel del av denne kommandoen er hvordan den løkker. Vi bruker en kommando kalt `\next`, initialisert til `\fibloop` inne i `\fibonacci`, og brukt inne i `\fibloop` for å styre løkken. `\fibloop` vil gjenta seg til `\next` endres av kode inne i selve `\fibloop` kommandoen. Vi vil bare sløyfe `n` ganger, så vi bruker en `\ifnum` setning som sjekker verdien til telleren vår (`\fcnt`) og deretter, hvis den ikke har nådd terskelverdien 0, `\fcnt` blir `\next` til `\relax`, som vil hindre `\fibloop` i å gjenta seg — den siste `\next` kommandoen gjør ingenting, og løkken avsluttes. De andre kommandoene i denne blokken beregner det neste Fibonacci-tallet i sekvensen og oppdaterer verdiene til variablene slik at de er klare for neste runde. Kommandoen `\the\ftwo` skriver ut verdien av det nåværende Fibonacci-tallet til dokumentet, og du vil også legge merke til et komma og et mellomrom øverst i `\fibloop` kommandoen som brukes til å skille hver verdi. #### Resultatet Den enkleste måten å se denne koden i aksjon på er å kjøre den på Overleaf ved å bruke **Åpne dette eksemplet i Overleaf** lenken nederst i kodevisningen. Fibonacci-sekvensen vokser raskt, så enhver `n>44` vil føre til heltallsoverløp i denne konkrete implementasjonen. ### Hvor går vi herfra? Som et uformelt bevis på at LaTeX er Turing-komplett, presenterer jeg følgende kode, som er en rask og grov implementering av en [NAND-port](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-porter (og også NOR-porter) har den interessante egenskapen at enhver annen logisk port kan bygges med denne ene typen port. Fra de grunnleggende logiske portene kan du konstruere latches, flip-flopper og minne. Det er ingrediensene for en datamaskin til generell bruk. Du kan teste denne NAND-porten for hver av de fire mulige inngangene med følgende eksempel, som du kan åpne i 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} ``` [Åpne dette eksemplet i 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) Å vite at LaTeX er Turing-komplett åpner opp en verden av muligheter. Kode som dette er vanlig i bakenden av LaTeX for ting som å holde oversikt over side- og figurnumre og bestemme hvor flytende objekter skal plasseres. Det er et verktøy du kan bruke til din fordel for å forenkle komplekse dokumentoppsett. For å avslutte dette innlegget vil jeg gi deg videre lesning om eksempler på programmering i LaTeX og Turing-maskiner. #### Eksempler på LaTeX-programmering * [Mandlebrot-mengden i LaTeX](http://warp.povusers.org/MandScripts/latex.html) . Spesiell takk til denne; denne koden var et nyttig eksempel mens jeg skrev Fibonacci-kommandoen min. * [En Turing-maskin i LaTeX: oppfølgeren](http://pbelmans.ncag.info/blog/2010/12/12/a-turing-machine-in-latex-follow-u/) NB: Da vi porterte denne artikkelen til et annet innholdshostingsystem, la vi merke til at nettstedet det ble henvist til i den opprinnelige artikkelen ( ikke lenger var tilgjengelig, så vi erstattet den lenken med en oppfølgingsartikkel av en annen forfatter. * [Wikibok om TeX-kommandoer](http://en.wikibooks.org/wiki/Category:TeX) * [LaTeX i en programmeringskonkurranse](http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html). En kontroller for Mars-roveren i LaTeX slo bidrag skrevet i flere mer vanlige programmeringsspråk. ### Turing-maskiner på uventede steder * [Conways Game of Life er Turing-komplett](http://rendell-attic.org/gol/utm/index.htm). Her er en implementering av en Turing-maskin. * [Regel 110](http://en.wikipedia.org/wiki/Rule_110) er en endimensjonal cellulær automat som er Turing-komplett. * Minecraft (videospillet) er Turing-komplett. Flere eksempler har blitt bygget, så den følgende lenken er ganske enkelt til en [side med relevante YouTube-søkeresultater](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/no/dybdeartikler/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.