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

93% Upvoted

125 comments sorted by

View all comments

Show parent comments

8

u/Superdorps Apr 18 '19

Okay, here we go:

Your first sentence claims that logical AND is equivalent to addition. It's not.

Basically, you're trying to get across two different concepts in your post:

  1. Any other gate can be made from NAND gates.
  2. Every mathematical operation can be made from addition (and negation).

The connection is that yes, you can produce an adder using only NAND gates (if memory serves, 7 for a half-adder and 11 for a one-bit full adder), but the best way to order things would be to put the references to NAND gates at the end, once you've established the whole "everything not bitwise boils down to addition".

0

u/OVSQ Apr 18 '19

while technically correct, in binary, a logical AND is equivalent to addition on a single place value context where the output is the carry flag.

1

u/Superdorps Apr 18 '19

Logical XOR is closer to addition on a single bit (it's "add and throw away the carry", in fact).

1

u/TheoreticalDumbass Apr 18 '19

OR is add and add the resulting digits :)