Can regular languages be Turing complete?

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?

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

StackExchange Computer Science Q#33666, answer score: 48