38
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Note that a language describing a turing machine can be trivially written in a regular language, for example i={0,1,-1},b={end of input} (i+bi+bi)+b(i+) describes a non-empty set of rules followed by a non-empty input. Or, rather, you can interpret it like that if you have an interpreter, which, as the answers mention, is a separate concept to the class of the language. $\endgroup$
    – Cubic
    Commented Dec 1, 2014 at 14:25
  • 2
    $\begingroup$ @Cubic: for that matter, Turing machines can be numbered such that every number represents exactly one machine (i.e. they're countable), and those numbers can be expressed in unary notation. I never properly studied this stuff, so I have to labour over the definitions, but I reckon 1*0 is a regular language ;-) Albeit not a very friendly programming language either for the programmer or the compiler-writer. $\endgroup$
    – Steve Jessop
    Commented Jul 10, 2015 at 17:18

5 Answers 5

Reset to default
48
$\begingroup$

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".
Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ I would add that (([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)* is a regular language that is able to describe grammar of any language of class 0 $\endgroup$
    – Erbureth
    Commented Dec 2, 2014 at 8:44
  • 3
    $\begingroup$ Also note that this is possible because we encode any Turing Machine as a binary string, and can make sure every binary string represents a Turing Machine. So the obviously regular language of $\{0,1\}^*$ can have Turing Complete semantics attached to it. $\endgroup$
    – Joey Eremondi
    Commented Jun 13, 2016 at 20:29
11
$\begingroup$

While the set of legal programs in Jot is regular, Jot itself is Turing-complete. That means that each computable function can be expressed in Jot. We can even come up with a language in which all binary strings are legal, but the language itself is Turing complete (exercise). You're confusing syntax and semantics.

By the way, context-free languages are also (probably) not NP-complete, since they have a polynomial time parsing algorithm.

Improve this answer
$\endgroup$
9
$\begingroup$

Syntax alone (as encoded in syntax trees) of modern programming languages is far from everything they do. In fact, the formal languages defined by the set of all programs in a given language that compile without error are rarely even context-free.

Static and dynamic semantics factor into the equation. They are invisible in the syntax tree but determine if a piece of code is actually a program and what it computes. Bottom-line, the context-free resp. regular formal language which is defined by "syntax" gives an overapproximation of the programming language.

Now to answer your question: yes, it's possible. Consider, for instance, any Gödel numbering of Turing machines; you get the "programming language" of all natural numbers, each representing a TM. Granted, it's not a nice language to program in, but it's certainly a Turing-complete language which is regular -- trivial, even.

Improve this answer
$\endgroup$
5
$\begingroup$

  1. A programming language is Turing-complete if it is expressive enough to specify every function computable by Turing machines. Here we are discussing the power of languages specified in the programming languages. E.g. it is not difficult to write an interpreter for Turing machines in Python, so Python is a Turing-complete programming language.

  2. The syntax of a programming language, i.e. the set of strings corresponding to valid programs in the programming language, is itself a language. E.g. consider the set of all possible Python programs. The syntax of a programming language can be context-sensitive, context-free, regular, etc. We are interested in the difficulty of checking that a given string is a valid program in the programming language (this is done by compilers/interpreters). When we say the syntax of a programming language is context-free it means that there is a context-free grammar for its syntax and implies that there is push-down automata for checking the validity of programs,

Note that the simplicity of the syntax of a programming language does not imply a restriction on the computational power of the programs specified in that programming languages.

Improve this answer
$\endgroup$
2
$\begingroup$

The answer is yes. You see, as the accepted answer states, a grammar is independent of its meaning. In Chomsky's own words:

I think we are forced to conclude that a grammar is autonomous and independent of meaning...

Chomsky, Syntactic Structures (1956)

If a grammar can produce sufficient sentences to describe all things that can be computed then we can arbitrarily assign computational meaning to its sentences - one for each thing that can be computed.

As for a real concrete example, the popular language whitespace has a regular grammar and perhaps even x86 assembly languages (needs verification).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think that passage means that Go's grammar is a regular language in the formal sense; I think it just means that the grammar is not irregular, i.e. consistent. If Go's syntax were actually a regular language in the Chomsky hierarchy, it would be incapable of generating e.g. balanced, nested parentheses. $\endgroup$
    – tsleyson
    Commented Jun 14, 2016 at 7:09
  • $\begingroup$ Yes, there is recursion in Go's grammar. Updating post. $\endgroup$
    – Eric
    Commented Jul 2, 2016 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.