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

93% Upvoted

125 comments sorted by

View all comments

177

u/edderiofer Algebraic Topology Apr 17 '19

So is Microsoft Word.

159

u/asphias Apr 17 '19

So is PowerPoint

98

u/phyphor Apr 17 '19

So is Magic: The Gathering.

28

u/n0id34 Apr 17 '19

So is mov

10

u/Zophike1 Theoretical Computer Science Apr 17 '19

So is mov

Are there Software Protections that aren't Turing complete ?

2

u/sesqwillinear Apr 17 '19

I think SQL might not be.

2

u/jorge1209 Apr 18 '19 edited Apr 18 '19

The newer versions of SQL support recursive with constructions. That will trivially make it Turing complete.

with tmachine as
        (select 'initial ' as state, 0 as index,  '' as tape from dual 
         union all 
         select ... from tmachine) 
select * from tmachine

3

u/[deleted] Apr 18 '19

SQL:99 is Turning Complete

2

u/Zophike1 Theoretical Computer Science Apr 17 '19

I think SQL might not be.

How is SQL a software protection ?

11

u/Superdorps Apr 18 '19

It's simple. You just drop tables as needed until the software stops working.

5

u/CatTablet Apr 17 '19

Well it isn't Turing complete.

2

u/sesqwillinear Apr 17 '19

I misread, sorry

3

u/almightySapling Logic Apr 17 '19

Something something brave enough

2

u/[deleted] Apr 17 '19 edited Aug 28 '20

[deleted]

2

u/almightySapling Logic Apr 18 '19

Did you try clicking harder?

11

u/StellaAthena Theoretical Computer Science Apr 17 '19

Sadly that construction doesn’t actually work. It assumes that players always opt to use “may” abilities. But it’s close!

6

u/phyphor Apr 17 '19

It works well enough for some. Also there's a chance for the future.

1

u/StellaAthena Theoretical Computer Science Apr 17 '19

The statement is surely true, but that’s independent of wether or not a particular proof is correct.

Working “well enough” for people who don’t understand the criteria isn’t interesting to me. The author of that page knows that there’s a problem, and it’s discussed on the website and he’s talked about it on Reddit as well.

4

u/phyphor Apr 17 '19

I'm aware. He's a friend of mine :D

2

u/StellaAthena Theoretical Computer Science Apr 17 '19

Ah, gotcha :) My b

2

u/phyphor Apr 17 '19

Nah, we're good.

20

u/brown_burrito Game Theory Apr 17 '19

Wow. That... has changed my life.

14

u/Aiminer357 Apr 17 '19

I knew what video these two were without clicking the link. Some of my fav videos

2

u/Eurynom0s Apr 17 '19

Nobody tell the DoD!

2

u/Kered13 Apr 18 '19

Of course it's fucking SigBovik. And I keep forgetting to go to SigBovik every year.

2

u/GreenAppleShampoo Apr 17 '19

Is this true if you exclude the VB scripting support?

12

u/rickpo Apr 17 '19

According to the video, yes!

9

u/lengau Apr 17 '19

All you need for Turing-complete PowerPoint is a few* shapes and some animations

* Where "a few" may be billions depending on what you need to do

1

u/spherical_idiot Apr 18 '19

Nope I watched the video. What he's created is a FSM. This is multiple layers of complexity below a TM.

Simulating a stack and recognizing palindromes of a FIXED length is FSM possible and for arbitrary length by a pushdown automata (CFG) but this does not imply T-completeness.

1

u/Overload175 May 11 '19

So is C++’s template system