1
$\begingroup$

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.

$\endgroup$

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.