Λ-HELL
- This is still a work in progress. It may be changed in the future.
λ-HELL is an esolang made by User:Yetyetty1234567890.
The goal of the language is not to be as "reduced" as possible, but rather as unconcise as possible, without adding any bloat. Bloat in this case means any unnecessary things, such as "add 200 million a's to the end of the program" or something more subtle, like in INTERCAL where you need a certain ratio of "PLEASE" to "DO" at the start of every line.
Definiton
λ-HELL is an extremely stripped down version of Lambda calculus. First, the output of λ-HELL MUST be determenistic. However, the execution order of the Lambdas in an expression in λ-HELL are still indeterministic. Secondly, there is only 1 type of variable; x
. Therefore, all Lambdas are assumed to be λx.
. Other than that, Lambdas only have two inputs: λx. (_ _)
.
Turing-completeness proof
To start with the Turing-completeness proof of this language, we must first talk about state machines.
Expressions as state machines
Simply speak, let's say we have some expression A. Now, this expression A will reduce to Expression B on it's own. This is called a _ reduction, because we don't need to know what actually happens for now. Now let's say, there is an expression like this: (A C)
(Note that A and C are just placeholders for lambda expressions) In this case, we have a new type of transition, a C transition. Let's say if both expression A and expression B go through a C transition, they become expression D. What we have made is a simple, deterministic operation. This idea forms the base for the rest of the proof. (Note that the actual state graphs that will be used are MUCH more complex.)
Something idk
TODO: Finish this proof