What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?
-
05-11-2019 - |
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange