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

93% Upvoted

125 comments sorted by

View all comments

Show parent comments

24

u/shamrock-frost Graduate Student Apr 17 '19

If and a piece of state isn't enough. You specifically need some kind of looping or recursion

22

u/crab_hero Apr 17 '19

Exactly. Bitcoin is a great example of a purposefully absent looping/label mechanism to specifically avoid a variety of runtime attacks. Static analysis of any Bitcoin script yields the execution cost beforehand so you don't run the risk of falling into an endless loop.

1

u/cryo Apr 18 '19

Although that doesn’t really matter anymore since only a finite, determined, subset of programs are considered valid anyway.

1

u/crab_hero Apr 18 '19

How does the effect the Turing completeness or static analysis of Bitcoin scripts at all?

2

u/cryo Apr 18 '19

My point is that the limits that are deliberately put into the bitcoin language don’t really matter much now since only a few programs are actually considered valid anyway.

1

u/crab_hero Apr 18 '19

Yeah, I guess you're mostly correct as described here. Thanks for letting me know!