0
$\begingroup$

I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.

But I cannot pinpoint what aspect makes a programming language RE, not context-sensitive. For example, I'm guessing the variables in any scope structures like for can be described in a context-sensitive grammar with a fairly bulky (but finite) number of production rules.

One wild guess is that it's because of pointers or references, making it impossible to describe with a finite number of production rules. Can anyone teach me about why it is?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

I think you are conflating syntax and semantics.

A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means only that a compiler could convert the program into an executable, without saying anything about what that executable does.

That has basically nothing to do with the semantics of the program. We could design a programming language which is arbitrarily difficult to parse, but whose semantics are simple enough that the generated executable is guaranteed to be a complete function. (Removing all looping constructs is a good start.)

On the other hand, we could design a language which is trivial to parse, as are most stack languages, but whose semantics are effectively Turing complete (aside from the finiteness of memory in a physical realization of a processor.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I'm thinking of the semantic restrictions (e.g., array accesses are only permitted inside a boundary) as a part of the language grammar. If it's the case, what feature is making the grammar RE? (assuming the programming language, say, C.) $\endgroup$
    – Gwangmu Lee
    Commented Aug 21, 2019 at 1:50
  • 1
    $\begingroup$ @gwangmulee: runtime behaviour depends on input; you cannot reliably reject a program which might break at runtime. Anyway, that's not what formal language theory is about. And what makes C RE (if it is) is the macro preprocessor. $\endgroup$
    – rici
    Commented Aug 21, 2019 at 4:01
1
$\begingroup$

Let us view the programming language abstractly as the (finite) description of a Turing machine's operation, which I assume is what you are aiming at by saying the language is RE or context-sensitive. The setting here is us having a single machine (a "universal" interpreter) to which we feed inputs of the form $(P, x)$ where $P$ is a program, $x$ is an input for $P$, and, considering $P$ as a function operating on $x$, we wish to compute $P(x)$. Note this is quite a different setting than when recognizing the language of valid programs (see @rici's answer).

We know the context-sensitive languages are those recognizable with a linear space bound. This means a machine for this kind of language only uses as much memory as its input is long. In "programming language terms", this roughly corresponds to the input being processed in place (e.g., sorting an array in place). In contrast, a recursively enumerable language (in general) requires an arbitrary amount of space.

It seems to me this is as far as the abstraction takes us. Pinpointing a particular programming language construct is infeasible unless we also make explicit assumptions on said language (e.g., what paradigms it uses).

Improve this answer
$\endgroup$

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.