You may also be interested in Chris Barker's language Iota, which consists entirely of the one-combinator basis Z=\f.fSK. On Sun, Oct 2, 2011 at 3:36 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Ordinary combinatory logic uses either the basis {S,K} or {B,C,K,W}. Here I define a combinator P, such that {P,I} is a universal basis:
Firstly, let J be Rosser's combinator, with the following rule:
Jwxyz = wx(wzy).
P is slightly more complex:
Pvwxyz = wx(wzy).
Obviously, we can define J in terms of P and I:
Jwxyz = PIwxyz = wx(wzy).
With I and J, it is possible to define B,C and W:
C = J(JII)(J(JII))(J(JII)). B = C(JIC)(JI). W = (rather large, but still finite)
P has the property of being able to discard its first argument. Using a combination of C, B and P, it is possible to make a similar combinator that discards its last argument (namely K). Hence, {P,I} is a universal combinator basis, as it can emulate {B,C,K,W}.
Now I shall define a pathological combinator, $, where $x = P (if x is equivalent to the identity combinator, I), and $x = I (if x is not equivalent to I). So, the rule can be expressed as follows:
$uvwxyz = wx(wzy) iff u = I; $uvwxyz = vwxyz otherwise.
Since $ is clearly not equivalent to the identity combinator, $$ = I. Hence, $($$) = $I = P, by applying the definition of $ again. So, we have a one-point universal combinator basis, as {$} can emulate {P,I}.
However, it is much more powerful than that. Using $, one can create second-level Turing machines (capable of solving the Halting problem), third-level Turing machines (capable of solving the Halting problem for second-level Turing machines), and indeed nth-level Turing machines for any n.
Moreover, n is not restricted to natural numbers; n can take on the value of any countable ordinal.
We have a programming language comprised of two instructions ($ and `, the operation of function application) capable of describing all nth-level Turing machines. For example, it is a straightforward procedure to 'program' the Collatz conjecture, and observe whether or not it is true. Obviously, no Turing machine is capable of running a generic program in this language.
You may have also noticed that certain machines produce undefined outputs, such as Y$, the Paradox Machine. If Y$ = I, then Y$ = $(Y$) = $I = P; if Y$ != I, then Y$ = $(Y$) = I. Y is the fixed- point combinator, with the rule Yx = x(Yx). Paradoxes still exist in ordinary lambda calculus, though.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com