Post by 《§》carbonara <3〖ƧƐ〗 on Aug 14, 2015 18:01:43 GMT
We are going to use a language called "SKIΩ combinator calculus". It is defined as following:
- We have four combinators: I, K, S and Ω. They take respectively 1, 2, 3 and 3 arguments.*
- I(x), or just Ix, is the identity function: Ix => x
- K(x,y), or just Kxy is a constant function of x: Kxy => x
- S(x,y,z), or just Sxyz, is a substitution operator. It is litteraly "x is applied to y inside the environment z", so it is pretty much a function call: Sxyz => xz(yz)
The process of systematically evaluate combinators using these rules (always by starting with the left-most combinator) is called "β-reduction"
The β-reduction continues until no combinator has enough parameters to apply.
For example: "SKS(KIS) => K(KIS)(S(KIS)) => KIS => I"
Note that some tree doesn't stop reducing: "SII(SII) = I(SII)(I(SII)) = SII(I(SII)) = SII(SII)"
And you can't always know wether some SKI expression will stop reducing or not
You can prove that any "computable" function (every function that a computer can run) is expressible using these 3 combinators, using the numbers of combinators left when β-reduction stopped as the "output" of the function. There is a class of trees that computes all values for, say, 2x+100
Then, ξ(n), defined as the maximum output of a n-combinator program, can be shown to grow faster than any computable function
The language can be improved much by adding a new combinator:
- Ω(x,y,z), or just Ωxyz, is an "oracle": it "knows" if the tree "x" will stop β-reducing or if it won't. Then, Ωxyz => y if x β-reduce to I, but if it doesn't Ωxyz => z
This improved language can compute ξ(n) and much more, but it also can make self-referential / paradoxical statements, so we will proceed as the following:
- Expressions consisting entirely of S, K and I are called "rank 0". If, in the sequence of beta-reductions of a an expression E, we only have to apply Ω to expressions of rank less than the ordinal α, then we say that T has rank α. Expressions with ranks are known as well-founded.
ξ(n) can be computed with a rank-2 tree, and with higher ranks trees we can do a lot of things!
Then, Ξ(n) is the largest output of a well-founded SKIΩ program with at most n combinators. It easily crush 99% of all functions known, and yet the only functions defined that beats it are Rayo's function, the F7(n) function and the FOOT(n) function. Both of the last two functions are extensions of Rayo's function.
- We have four combinators: I, K, S and Ω. They take respectively 1, 2, 3 and 3 arguments.*
- I(x), or just Ix, is the identity function: Ix => x
- K(x,y), or just Kxy is a constant function of x: Kxy => x
- S(x,y,z), or just Sxyz, is a substitution operator. It is litteraly "x is applied to y inside the environment z", so it is pretty much a function call: Sxyz => xz(yz)
The process of systematically evaluate combinators using these rules (always by starting with the left-most combinator) is called "β-reduction"
The β-reduction continues until no combinator has enough parameters to apply.
For example: "SKS(KIS) => K(KIS)(S(KIS)) => KIS => I"
Note that some tree doesn't stop reducing: "SII(SII) = I(SII)(I(SII)) = SII(I(SII)) = SII(SII)"
And you can't always know wether some SKI expression will stop reducing or not
You can prove that any "computable" function (every function that a computer can run) is expressible using these 3 combinators, using the numbers of combinators left when β-reduction stopped as the "output" of the function. There is a class of trees that computes all values for, say, 2x+100
Then, ξ(n), defined as the maximum output of a n-combinator program, can be shown to grow faster than any computable function
The language can be improved much by adding a new combinator:
- Ω(x,y,z), or just Ωxyz, is an "oracle": it "knows" if the tree "x" will stop β-reducing or if it won't. Then, Ωxyz => y if x β-reduce to I, but if it doesn't Ωxyz => z
This improved language can compute ξ(n) and much more, but it also can make self-referential / paradoxical statements, so we will proceed as the following:
- Expressions consisting entirely of S, K and I are called "rank 0". If, in the sequence of beta-reductions of a an expression E, we only have to apply Ω to expressions of rank less than the ordinal α, then we say that T has rank α. Expressions with ranks are known as well-founded.
ξ(n) can be computed with a rank-2 tree, and with higher ranks trees we can do a lot of things!
Then, Ξ(n) is the largest output of a well-founded SKIΩ program with at most n combinators. It easily crush 99% of all functions known, and yet the only functions defined that beats it are Rayo's function, the F7(n) function and the FOOT(n) function. Both of the last two functions are extensions of Rayo's function.
