This question is not meant to be too theoretical or nitpicky. I have experience programming, so I'm trying to get a better understanding of what it takes to get Turing-completeness by using my intuition about practical programming languages.

Basically: What minimal elements of a language like Javascript do we need to have Turing completeness, and why? (I'm pretty sure we don't need interfaces or subclasses, etc).

Extra question: Is there a simple, natural polynomial-time reduction from a language like Javascript/C++/C# to a Turing machine?


It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all three languages.

The While language is also good for an intuition of Turing completeness. You need

  1. Potentially infinite loops, because Turing complete computations may not terminate.

  2. Condition-dependend behaviour, so that you can break out of loops (important: in contrast to for loops, the time after which the loop ends is not be known in advance).

  3. A data type with an infinite domain.

In both examples I gave above, the third ingredient is the type of integers of unbounded size. Arguably, it is not natively supported in C++ (I do not know about JavaScript or C#. A "normal" programming that has it is Python 3.) You promised not to nitpick, but if you did one would have to either

  • replace your languages by "conceptual" variants thereof where integers are unbounded, or

  • implement unbounded integers in a library (like GNU MP). When you do that, you inevitably use the "true" third ingredient of your languages: They achieve infinite-domain data through dynamic allocation.

All of the above would as well hold for C. Yet your question, at least the title, is specifically about OOP languages. Basically, your three languages are extensions of C by objects. My Turing-complete subsets then discard these extensions. At the moment I cannot come up with natural subsets of any of these languages where some OOP feature is essential for Turing completeness.

As for simple, natural, polynomial time reductions to Turing machines: Polynomial time is possible, natural in a sense, simple I do not think (such a reduction is a full-feature compiler for the language, so it cannot be any simpler than the language is). Let there be three tapes. One for the heap, one for the stack and one for indexing. The heap and the stack would contain sequences of substrings like [1010011] which encode unbounded integers (83 in this case). When used as pointers, these integers are somehow mapped to positions in the heap or the stack. Indexing an element of the heap or the stack works by copying the pointer to the indexing tape and then moving to the respective part of the tape by using the indexing tape as a counter.


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.