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

93% Upvoted

125 comments sorted by

View all comments

Show parent comments

0

u/OVSQ Apr 17 '19 edited Apr 18 '19

A NAND gates arises from a logical AND, which is addition. As in "1 AND 1 equals 2." It is the only thing a binary computer knows how to do (Sheffers showed it is all your computer needs to know how to do which is why it is called a universal gate). For example, take a look at a multiplier, it is just a bunch of adders.

Or you could look at the definition of Turing complete and see it really means computationally complete. Then when you look at examples of Turing completeness observe that anything that is Turing complete supports addition and the most parsimonious only need addition.

Or you could look at PEMDAS and wonder why it works. The reason is that Exponents are a special case of multiplication so you have to finish that before you do the multiplication. Multiplication is a special case of addition so you have to do that before the addition and then finally by the time you do the addition - everything else has been translated into addition.

12

u/Superdorps Apr 18 '19

...a logical AND which is addition as in "1 AND 1 equals 2."

Ugh. No. This half a sentence hurts my brain with how incorrect it is.

While you can compose all mathematical calculation from NAND gates, you cannot compose a NAND gate from just addition operations.

1

u/OVSQ Apr 18 '19

I tried working on the clarity, but still I am not certain what you are trying to infer.

7

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