Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. an arbitrary Turing machine). On the other hand, a model of computation is Turing complete if and only if it can compute (the indicator function of) all recursive sets. Is there a special recursive set $S$ (or finite subset of recursive sets) so that it is enough for $C$ to compute $S$ to assure that $C$ is Turing complete? Informally, $S$ would be a set for whose computation branching, looping and memory are all needed in an unavoidable way. If such sets do exist, which are the simplest ones?

In a practical sense, the utility of these sets would be the following test: if your model of computation can solve this type of (e.g. numerical or geometric) problem, then it is Turing complete.


Your Answer

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

Browse other questions tagged or ask your own question.