Menu
I know a little about what is a turing-machine and a turing-complete language, but to understand better, could someone give examples of languages that are not Turing complete? (maybe even machines that are not Turing, as well?)
716
Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete. A related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.
It probably comes as no surprise that powerful programming languages like Python, JavaScript, and C++ are Turing complete. They're currently the standard for building software, and they could theoretically be used as the foundation of any computable task.
It should be noted that technically speaking, C++ the language is Turing complete, while any particular implementation (such as " g++ on machine X") is not.
PHP is a Turing complete computer language.
Regular expressions, in the formal definition, consisting only of:
can only recognise regular languages. A Turing-complete programming language can recognise recursively-enumerable languages.
An example is that regular expressions cannot tell you if a string consists of matched pairs of parentheses: eg ()(()) is accepted while ()((())() is rejected, while Turing-complete programming languages can.
(Note that regexes in modern programming languages are more powerful than the formal academic definition of regular expressions. Some may even be Turing complete.)
69
Regular languages - those that can be described as regular expressions - are not Turing complete.
Markup languages (used for describing data, not computation) like XML and JSON are not Turing complete.
3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
