JavaScript Is Turing Complete— Explained
rajaraodv
80012

I enjoyed the article’s explanation of single and multi-tape TMs. It furnished a nice review of the basic concepts involved. However, the last paragraph left me hanging with the assertion that any program that can be run on a TM can also be programmed and run in JS.

It seems to me that this is a proposition that requires proof beyond mere assertion, doesn’t it? After all, the article is presented as an “Explanation” of the idea that JavaScript is a Turing Machine. Merely stating that JS can run every program that a “Turing Machine” can run, and is therefore called “Turing Complete,” explains only the potential use of the terminology. That is, we may apply the rubric “Turing Complete” to JS and it will be a well-formed proposition (i.e., both JS an TM are well-defined terms), but it is an incomplete explanation of the equivalence of the two terms. Such an explanation — proof, really — would require showing that an arbitrary sequence of n operations of the Turing machine can be mapped into a corresponding sequence of well-formed JS programming statements.

I get that this is probably beyond the scope of what the article was trying to accomplish, but my view is that it would be kinder to the reader to promise only to explain what it means to state that Java Script is Turing Complete, which the article does quite well, rather than presenting it as an accomplished fact, which the article asserts but does not quite demonstrate.