Search code examples
programming-languagescomputer-sciencecomputation-theoryformal-languages

How come we write programs in context-free languages? Shouldn't programs be in recursively enumerable languages in order to be Turing complete?


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.


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.