36
$\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?

$\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
    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$ Jul 10, 2015 at 17:18

6 Answers 6

44
$\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".
$\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
    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$
    – jmite
    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.

$\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.

$\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.

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

$\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
    Jun 14, 2016 at 7:09
  • $\begingroup$ Yes, there is recursion in Go's grammar. Updating post. $\endgroup$
    – Eric
    Jul 2, 2016 at 20:48
-2
$\begingroup$

To all the buddying alan turings who saying that a regular language can be turing complete, i have just one question to ask -

" a turing complete language, like the one which can be produced by an unrestricted grammar, must be undecidable in the sense that for a given statement which is not in that language a turing machine can either accept, reject or loop, that's why they are also called recursively enumerable languages . But if a regular language is turing complete then we know that regular languages are decidable. And given the expressive power of unrestricted grammars that turing complete regular language can also be given in terms of an unrestricted grammar. Thus now we can call the same language as a recursively enumerable language, cuz its produced by an unrestricted grammar But ain't that would mean that now there is a recursively enumerable language for whom the decision problem, or equivalently the halting problem , is decidable ? "

And if that's truly the case i think you fellas should publish your findings, and become immortal in the field of mathematics.

$\endgroup$
2
  • 1
    $\begingroup$ In addition to the fact that you are not answering the question, you are trying to compare non-comparable things. Turing complete refers to a way to describe a Turing machine (all of them actually). Regular refers to a set of strings recognizable by a finite automaton. Those are not incompatible (read the first answer again). Jot is a Turing complete "programming" language, and any string of $0$ and $1$ is a program in Jot (so the set of programs written in Jot is regular). $\endgroup$
    – Nathaniel
    Nov 13, 2021 at 17:14
  • 1
    $\begingroup$ Thank you for you interest. However, please use the "answer" form for answers only. We try to be a bit strict in this, to have a more structured form of conversation. So, please, rephrase your post as a question, ask it, and include a link to this question. Thanks! $\endgroup$
    – Discrete lizard
    Nov 14, 2021 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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