How come we write programs in context-free languages? Shouldn't programs be in recursively enumerable languages in order to be Turing complete?
computation-theory, computer-science, formal-languages, programming-languages
Solution
You are confusing the specification of a program with its output.
For example, a Turing machine that can accept a recursively enumerable language is still specified by a finite transition function or "rule table". The rule table itself can be expressed in a regular language.
Then again, only the basic syntax of a modern programming language is completely defined by a context free grammar. A valid program has to fulfill many conditions that are not captured by a grammar: identifiers have to be declared before they are used, a function can be defined only once, the program has to pass the typechecker, and so on.
Problem
I really can't understand how we can simulate the output of a Turing machine (which accepts a recursively enumerable language) if we mostly code in context-free languages.