4 ms·

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

shagie 2y ago
My favorite turning complete language is Fractran - https://en.wikipedia.org/wiki/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://oeis.org/A007542 https://news.ycombinator.com/item?id=35966537 https://news.ycombinator.com/item?id=35966537 https://softwareengineering.stackexchange.com/questions/220188/why-is-fractran-turing-complete https://softwareengineering.stackexchange.com/questions/2201... https://web.archive.org/web/20150923211455/http://www.cs.vu.nl/~diem/publications/slides/fractran-2011-05-31.pdf https://web.archive.org/web/20150923211455/http://www.cs.vu....
andoando 2y ago
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.
tossandthrow 2y ago
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 2y ago
  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.
  - tossandthrow 2y ago
    > you need to build the physical computer Exactly. Now tell me how you will do unbound computation (ie. write on the n+1 cell in the Turing machine) with a fixed number og NAND gates and without a clock.
    - deleted 2y ago
      [deleted]
    - hot_gril 2y ago
      Oh, I see what you mean. Yeah it seems like you need a clock.
reichstein 2y ago
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 https://en.m.wikipedia.org/wiki/One-instruction_set_computer).

My favorite turning complete language is Fractran - https://en.wikipedia.org/wiki/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://oeis.org/A007542 https://news.ycombinator.com/item?id=35966537 https://news.ycombinator.com/item?id=35966537 https://softwareengineering.stackexchange.com/questions/220188/why-is-fractran-turing-complete https://softwareengineering.stackexchange.com/questions/2201... https://web.archive.org/web/20150923211455/http://www.cs.vu.nl/~diem/publications/slides/fractran-2011-05-31.pdf https://web.archive.org/web/20150923211455/http://www.cs.vu....

andoando 2y ago

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.

tossandthrow 2y ago

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 2y ago
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.
- tossandthrow 2y ago
  > you need to build the physical computer Exactly. Now tell me how you will do unbound computation (ie. write on the n+1 cell in the Turing machine) with a fixed number og NAND gates and without a clock.
  - deleted 2y ago
    [deleted]
  - hot_gril 2y ago
    Oh, I see what you mean. Yeah it seems like you need a clock.

reichstein 2y ago

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 https://en.m.wikipedia.org/wiki/One-instruction_set_computer).