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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
For similar reasons, strictly speaking, the computer sitting on my desk is not Turing-complete, either, because it is finite. Nonetheless, it is useful to think of it as Turing-complete, in a looser sense: there is a natural abstraction of my machine where we disregard its finiteness (consider an abstract model where instead of being limited to 1TB of disk space, it has an unlimited amount of disk space). For many purposes, the differences between my actual finite machine and the abstract, idealized machine with unlimited storage isn't very important. But for your question, the difference can't be ignored, and to make your question well-specified, you'd have to think about how you plan to address this important distinction.
If you're interested in computing models that are somehow "simple"/"small" yet Turing-complete, you might be interested in rule 110, tag systems, and the lambda calculus. See also Universal binary rewriting system. Do some searches on these terms on this site (and elsewhere) to learn more about these topics.
-
$\begingroup$ @Halbort, I edited my answer to mention some other related ideas you might find interesting. $\endgroup$– D.W. ♦Commented Apr 3, 2017 at 22:40