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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Derek Elkins May 14 '17 at 23:33
  • $\begingroup$ "some problems require loops practically" -- no, there's also recursion. Also, for-loops are striclty less powerful than while-loops. $\endgroup$ – Raphael May 15 '17 at 5:15
  • $\begingroup$ Note that, in practice, Turing-power is rarely ever needed. Most stuff you'll ever program is primitive recursive. $\endgroup$ – Raphael May 15 '17 at 5:16
  • $\begingroup$ @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. $\endgroup$ – Raphael May 15 '17 at 5:17
  • $\begingroup$ @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. $\endgroup$ – Derek Elkins May 15 '17 at 5:51

The answer is no (although from a rather syntactic reason, which might not be what you were looking for).

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

  • $\begingroup$ Indeed - not quite the reason I was looking for, but if it's the right one then it's all the same to me. Thank you for the explanation! $\endgroup$ – user991710 May 21 '17 at 19:11

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.