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 machines that are not Turing, as well?)
+1
A:
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.
Matt Ball
2010-08-30 12:37:58
The difference between data and computation is tricky. [LaTeX](http://stackoverflow.com/questions/2968411/ive-heard-that-latex-is-turing-complete-are-there-any-programs-written-in-latex) is Turing-complete, despite being a text-processing language.
Philip Potter
2010-08-30 12:43:09
@Phillip: Not entirely fair, since LaTeX has access to all of TeX which is intended (at least in part) to be a general-purpose language. See Knuth's page, where he answers the question "What is your favorite language?".
Charles
2010-09-01 02:56:59
+6
A:
Regular expressions, in the formal definition, consisting only of:
- concatenation ( ab )
- unbounded repetition ( a* )
- alternation ( a|b )
- grouping ( (ab)|(cd) )
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.)
Philip Potter
2010-08-30 12:42:04
For example, the Perl regexp can be recursive: http://www.catonmat.net/blog/recursive-regular-expressions PHP regexp has the /e flag to evaluate PHP expressions in the subsitution.
SHiNKiROU
2010-08-31 17:13:16
Once saw a regular expression in Perl that matched strings with a length that was a prime number only. Used backtracking and took quite a while...
Thorbjørn Ravn Andersen
2010-09-27 15:57:41