Looking for languages that are not Turing complete

Question

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?)

Gamesmanship

Answer 1

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.)

Epiphytotic

For example, the Perl regexp can be recursive: catonmat.net/blog/recursive-regular-expressions PHP regexp has the /e flag to evaluate PHP expressions in the subsitution. – Elisaelisabet

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... – Pampas

Answer 2

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.

Damato

The difference between data and computation is tricky. LaTeX is Turing-complete, despite being a text-processing language. – Epiphytotic

@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?". – Janniejanos