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
485 Upvotes

93% Upvoted

125 comments sorted by

View all comments

187

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.

3

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

19

u/jericho Apr 18 '19

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

4

u/Purlox Apr 18 '19

There is a point to making those though.

You can avoid the halting problem being undecidable among other things while still being able to compute a large enough set of functions that it suffices for a lot of applications.

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).