[nferraz]

In fact, NAND gates are enough to build a Turing complete machine. ;-)

[shagie]

My favorite turning complete language is Fractran - https://en.wikipedia.org/wiki/FRACTRAN

    17 78 19 23 29 77 95 77  1 11 13 15  1 55
    -- -- -- -- -- -- -- -- -- -- -- -- -- --
    91 85 51 38 33 29 23 19 17 13 11  2  7  1

That computes prime numbers.

Iterate through the list (start with n = 2) and iterate through until the fraction is an integer. Repeat with the new number.

For this, after 2, the next value is 15 (when it gets to 15/2). Then it will be 825 (15 * 55/1). Then it will be 725 (825 * 29 / 33) and so on. At some point, n will be 2^x where the sequence of when the number is just a power of 2 will be: 2^2, 2^3, 2^5, 2^7, 2^11 and so on... the exponents of 2 are the prime sequence.

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30 ...

https://oeis.org/A007542

https://news.ycombinator.com/item?id=35966537

https://softwareengineering.stackexchange.com/questions/2201...

https://web.archive.org/web/20150923211455/http://www.cs.vu....

[tossandthrow]

How will you do unbound computation with only NAND gates? Either you need a clock (not a NAND gate) or you need to implement a clock using NAND gates, but that assumes physical aspects such as power propagation speed.

Typically you say that you can make arbitrary functions between any two closed domains using only NAND gates.

[hot_gril]

Turing completeness isn't about having everything you need to build the physical computer, just about expressing program logic that can perform a certain class of unbounded computations. Like, given any C program's logic that takes some input and gives an output, you could calculate the same thing (painfully) with NAND gates.

Anyway, bringing up Turing completeness is overly theoretical when talking about a programming language. It's pretty hard to make a language not Turing-complete, and it doesn't say much about what you can use it for IRL.

[reichstein]

NAND gates are enough to computer any boolean function. Being Turing complete requires some notion of state and state transition.

However, a RAM machine where the program counter is memory mapped, can be Turing complete with a [single machine instruction]( https://en.m.wikipedia.org/wiki/One-instruction_set_computer).

[andoando]

While true, to build a language using NAND gates, the language has to specify how to assemble those gates, which will still require conditionals and loops if you want it to build any machine.