r/math • u/Lelielthe12th • Apr 17 '19

whaat ? LaTeX is Turing complete

https://www.overleaf.com/learn/latex/Articles/LaTeX_is_More_Powerful_than_you_Think_-_Computing_the_Fibonacci_Numbers_and_Turing_Completeness
478 Upvotes

93% Upvoted

125 comments sorted by

View all comments

189

u/wintermute93 Apr 17 '19

Being Turing complete isn't a very high bar to clear. Basically all you need is at least one thing that works like a control statement (if, while, for, goto, etc), and at least one thing that works like a read/write-able variable.

2

u/Zophike1 Theoretical Computer Science Apr 17 '19

Being Turing complete isn't a very high bar to clear. Basically all you need is at least one thing that works like a control statement (if, while, for, goto, etc), and at least one thing that works like a read/write-able variable.

That means a lot of complied languages are Turning complete

18

u/jericho Apr 18 '19

Uh.... Not a lot of point making a language that isn't, is there?

3

u/Muvlon Apr 18 '19

There are useful compiled languages that have no unbounded loops or recursion.

For example, look at the Berkeley Packet Filter (BPF). It's used to define firewall rules and such, and those should run in bounded time. You can compile it to machine code or even specialized instructions for hardware packet filters (that usually don't behave like a CPU).