# How many gates until Turing Complete

A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone have to put before it can be expected that the "computer" is Turing Complete?

A single finite machine is never Turing-complete. (Such a machine with $n$ bits of internal memory has only $2^n$ states, so it can be modelled as a DFA with at most $2^n$ states.) So, strictly speaking, it only makes sense to even ask about Turing-completeness when you have a machine model that is unbounded, or when you have an infinite family of machines $M_1,M_2,\dots$ of increasing size.