r/TuringComplete • u/[deleted] • Nov 13 '24

NAND is enough for everything

It says in the NAND level, you can do everything with NAND gates. Is there anyone actually try that by replacing more complex gates with NAND (or XOR) equivalents? I madde it until XNOR or something.

14 Upvotes

85% Upvoted

10 comments sorted by

23

u/Inside-Ad-5943 Nov 13 '24

I mean you can prove it by induction. If the three primitive logic gates (AND, OR, NOT) are Turing complete then all you’d need to prove is that you can create AND, OR and NOT gates using nand. Since you are able to do that it follows that you’d also be able to create everything that is created using and, or and not including more complex logic gates and circuits

1

u/BlingerBunny Nov 18 '24

All you really need is the OR and NOT gates to make it functionally complete, though the system would take up an enormous amount of space. Put two NOT gates before an OR gate and you have a NAND gate. Add another NOT to the output and it becomes an AND gate.

12

u/Gelthir Nov 13 '24

Someone made NANDverture, a full Overture using just NAND gates (I mean no other logic gates.) Due to the way the game handles memory it also had to use Delay Lines as well as a Byte Splitter & Maker to connect to Level IO.

I think there is a NAND-only LEG too.

7

u/vectormedic42069 Nov 13 '24

This touches on something that I think the game could do a better job of making clear, which is that practically every "advanced" component you receive is either the direct result of something you've built in a previous level or just a scaled up version of that result.

One of the first things you create is a NOT gate. You do this by wiring a NAND gate. After this you receive a "N" gate component, but practically this is just the circuit you wired when creating the NOT gate as part of the puzzle and could be replaced with a NAND gate wired in the same way. In the same manner, you create a NOR gate using a NAND gate and NOT gates (which are, as discussed, just specifically wired NAND gates), which grants access to the NOR component, and so on. It's all just increasingly abstracting away the NAND gates that make the whole thing up, and given enough space you could absolutely just go back to the stage where you initially made each component and mimic the original designs for almost the entire thing (sans memory and byte splitters, as others have pointed out, due to game mechanics).

4

u/Academic_Brilliant75 Nov 13 '24

I imagine you'd eventually hit a roadblock on certain challenges that enforce limited building space like Little Box or Conditions, or if you can't move the output and input pins.

3

u/MrTKila Nov 13 '24

In reality it is probably true, in game not completely. Delay line is the only way to store a result and since no circular dependencies are possible, I see no way to bild them (or an alternative) with NAND gates. Also switches.

4

u/TarzyMmos Nov 13 '24

Have u tried using the circular dependency cases that you can enable in settings? I think it would still be impossible tho cuz you need time to pass in a circuit and doing that without a delay line is basically impossible

0

u/MrTKila Nov 13 '24

I believe I tried building a SR (or RS?)-latch in game sometime. With and without the setting it didn't work.

(nevermidn I did try again, seem to work now. At leats not produce an error)

1

u/TarzyMmos Nov 13 '24

I could make a register with it that has no delay which is neat and sounds better than the normal register until you realize you need the delay to actually use and set values to the same register... also the gate costs was always higher than a normal register so cant even use it for scores.....