3

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


1

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


Only top voted, non community-wiki answers of a minimum length are eligible