It is well known that all computable functions can be expressed as terms of the lambda calculus and computed according to its rules. It is also more or less obvious that many classical formal languages (i.e. languages with formalized semantics) can be translated into the lambda calculus (e.g. using a Church encoding). I am, however, pretty sure that there are languages where such a translation is not possible, the simplest example would be a language with a builtin primitive that solves the Halteproblem.That makes me wonder if there is an established terminus for the languages that can be translated.Is there a name for the class of languages that can be translated (correctly, completely) into the lambda calculus?
Class of languages that are equivalent to the lambda calculus
computability;terminology;lambda calculus
The lambda calculus is exactly equivalent in expressive power to Turing machines, so the languages that can be translated into it are exactly those that are no more powerful than Turing machines.Models of computation that are more powerful than Turing machines are known as hypercomputation. However, except for computability theorists, most people don't ever consider languages that can express hypercomputation, so most people don't need a word that not capable of hypercomputation. It's a bit like there being no word for food that isn't poisonous because not being poisonous is the default state for food so people don't really need a word for that.Your question title asks about languages that are equivalent to the lambda calculus, i.e., those where we can translate in both directions. Because the lambda calculus has the same power as Turing machines, these are exactly the Turing-complete languages.