0
$\begingroup$

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

Improve this question
$\endgroup$
  • 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$ – Yuval Filmus Sep 3 '19 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$ – Yuval Filmus Sep 3 '19 at 8:13
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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