Hacker News new | ask | show | jobs
by tossandthrow 763 days 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.

1 comments

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.

> 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.

Oh, I see what you mean. Yeah it seems like you need a clock.