Can regular languages be Turing complete?

Problem Detail: 

I was reading about Iota and Jot and found this section confusing:

Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-branching. As a result, Iota is strictly context-free, but Jot is a regular language.

My understanding is that both Iota and Jot are Turing complete. But apparently, one is context-free, and the other is regular! Surely regular languages can't be Turing complete?

Asked By : sdleihssirhc

Answered By : jkff

In short, the answer is yes.

But you're mixing two completely unrelated meanings of the term "language" (yes, this is confusing):

• A set of strings. "Context-free language" means "a set of strings which can be recognized using a context-free grammar".
• A way of specifying a computation. "Turing-complete language" means "a way of specifying programs in which the Turing machine can be specified".

Note that you can talk about "the C++ language" from two completely unrelated viewpoints, using the two unrelated meanings of the word "language":

• C++ as a set of strings which are legal according to the C++ grammar
• C++ as a way of specifying programs.

The traits of "the C++ language" from these two viewpoints are unrelated.

More examples to help you separate these concepts:

• The expression "[a-z]+@[a-z].[a-z]" describes a set of strings recognizable by finite automata, i.e. a regular language. However, it's just that - a set of strings: is not a way of specifying programs (unless you ascribe a way to interpret each such string as a program), so it does not make sense to talk about whether or not it is Turing-complete.
• The language of flowcharts is a way of specifying programs; depending on the particular flavor of flowcharts, it may or may not be Turing-complete. However, flowcharts aren't strings, so it makes absolutely no sense to talk about flowcharts in the sense "language as a set of strings".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33666