# Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive.

For example, some problems require loops practically - making 10^100^1000^10000 repeated calculations (even no-ops) is not possible practically as the space necessary to store the code would likely be greater than the number of atoms in the universe, but would be possible theoretically given infinite memory (similar to how current implementations of programming languages only approximate Turing-completeness).

Alternatively: is there a problem which requires Turing-completeness to solve theoretically?

• Um... an interpreter for a Turing-complete language would only be implementable in a Turing-complete language... Of course, you have to prove that it actually does correctly implement the language. For example, it's actually rather non-obvious that C is Turing-complete because it does expose some hardware limits so an "obvious" implementation of a putative interpreter may well not be correct. This is a bit of an odd case though. In most cases an "obvious" implementation will not be limited in this way. Commented May 14, 2017 at 23:33
• "some problems require loops practically" -- no, there's also recursion. Also, for-loops are striclty less powerful than while-loops. Commented May 15, 2017 at 5:15
• Note that, in practice, Turing-power is rarely ever needed. Most stuff you'll ever program is primitive recursive. Commented May 15, 2017 at 5:16
• @DerekElkins Would a language with exactly one program, said interpreter, be Turing-complete itself? I don't think so -- it solves only one problem, not all of them. Commented May 15, 2017 at 5:17
• @Raphael I guess that's a good if pedantic point. Say we can implement an interpreter for a Turing-complete language and can represent (and provide) input to it. For example, I absolutely would say a programming language that provided only one operation -- a string accepting function that would interpret the string as source code in some Turing-complete language -- and had string literals and nothing else was Turing-complete. That said, for a Universal Turing Machine, we expect the desired program to be part of the input, so I'm not sure I would exclude even your scenario. Commented May 15, 2017 at 5:51

Let $f : \Sigma^* \rightarrow \Sigma^*$ be some arbitrary function, then it is implementable in the following "stupid" language which is not Turing complete:
Any string $s\in \Sigma^*$ is a valid program, and all strings represent the program which, given $x$ as input, outputs $f(x)$. Note that I don't really care how it computes $f$ (as I'm defining a new model of computation). If this bothers you, imagine any string is translated to the same fixed Java program which computes $f$ (assuming $f$ is computable).