Somewhere on stackexchage, I, or someone else asked what was the proper term for Turing completeness minus the infinite memory (e.g. a Turing machine that one can actually build, no bigger than your typical data center). Answer was inconclusive.

Also, someone else asked somewhere else on stackexchange about the number of gates for a Turing machine, but that got sidetracked into the useless infinite definition (that many quanta do not exist in the known universe).

So using the non-infinite Turing machine definition (*), whatever that is, is there a known lower bound on the number of 2-input binary gates needed to produce a Turing complete computer? Or a reasonable guess or a minimum among known current published existing example implementations?

(* If necessary assume the "tape" is external to the logic gate count, the gates just drive the tape read/write/move mechanism).

  • 1
    $\begingroup$ A good start would be to provide links to all the questions and answers that you mention. That would help to clarify this question. $\endgroup$ Commented Sep 3, 2019 at 8:12
  • $\begingroup$ It is classically known that every function from $n$ bits to $1$ bit can be implemented using $O(2^n/n)$ gates (AND,OR,NOT), and this bound is tight - some functions require $\Omega(2^n/n)$ gates. $\endgroup$ Commented Sep 3, 2019 at 8:13

1 Answer 1


As soon as you limit "memory" you are talking about machine models that are equivalent to finite automata. If you limit "memory" to input size, you are at linear bounded automata, which are easily seen to be limited to recognizing (some) recursive sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.