5
$\begingroup$

Suppose we have a $\kappa$-calculus with operator $fix$, that could be used to transform function with type $(1 \rightarrow a) \rightarrow a$ to a value of type $1 \rightarrow a$. We use a normal reduction strategy.

We'd like to represent factorial function in such a system. The problem is that whatever function we're trying to find a fixed point of, when we apply the function to its fixpoint, there's no way to determine whether we need to use the value of argument $x$ or not. There's no "counter" to base our solution on.

$fix (\kappa{}x. \cdots) = (\kappa{}x. \cdots) (fix (\kappa{}x. \cdots))$

In $\lambda$-calculus we could run $fix (\lambda f. \lambda x.\cdots)$ and terminate depending on the value of $x$.

  1. How to prove that $\kappa$-calculus with fixed point operator cannot really represent a factorial function?
  2. How could we extend $\kappa$-calculus to make it Turing-complete, leaving space for its translation into generalized arrows?
$\endgroup$
9
$\begingroup$

The bare $\kappa$-calculus does not permit defining factorial, even when extended with a fixed point operator. However, this answer deserves some unpacking.

  1. The fixed point operator you give is not well-formed according to the grammar of types in the $\kappa$-calculus. Note that the grammar of types does not contain the function space $\tau \Rightarrow \tau'$ -- this is because the $\kappa$-calculus is a language of first-order functions. An expression has a type $\tau_1 \to \tau_2$, to indicate that it is an expression of type $\tau_2$, whose free variables are typed by $\tau_1$.

    The proper typing for a fixed point operator would be roughly something like: $$ \frac{\Gamma, x:1 \to \tau \vdash e : 1 \to \tau} {\Gamma \vdash \mu x:1 \to \tau. e : 1 \to \tau} $$

  2. Once you've fixed this, you still can't define a factorial.

    The plain $\kappa$-calculus does not have sums or natural numbers as a base type. As a result, you can't write branching programs, and so you cannot define interesting recursive functions. If you added natural numbers and their iterator, you could define a factorial function. Hasegawa actually gives factorial as an example in his paper on the $\kappa$-calculus, in a calculus augmented with a basic natural number type.

    However, you might wonder why you are able to define factorial in the pure lambda calculus, even though it has no apparent control structures. The reason is that the interaction of fixed points and recursion gives you a "universal type" (i.e., a type $V$ such that $V$ is isomorphic to $V \to V$), and this lets you encode any datatype as a subset (more accurately, a retract) of it.

    In more syntactic terms, you can write the Y combinator (i.e., Curry's paradox) in any language with (a) higher-order functions, (b) recursion, and (c) the ability to use each variable more than once in a program. Since the basic $\kappa$-calculus lacks (a), adding even an unrestricted fixed point operator does not make it Turing-complete!

$\endgroup$
  • $\begingroup$ Forgot that generalized arrows include primitives for $+$ type too. It seems that I need a kind of primitive recursion and minimization operators to make $\kappa$-calculus Turing-complete again. Thank you for the great answer. $\endgroup$ – polkovnikov.ph May 27 '14 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.