Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $e$ be any expression in the SKI combinator calculus. Let $R(e)$ denote the number of possible reduction orders for $e$.

Is $R$ a computable function?

I believe that $R$ is not computable. But I'm not completely sure.

It appears to me that the only way to compute $R$ is to actually construct all possible reduction sequences. In other words, to run the program. And if the program does not terminate, then clearly the counting procedure also does not terminate. So it looks like computing $R$ might be equivalent to solving the Halting Problem.

This assumes that there is no other way to compute $R$ though, and I have proved no such thing.

Alternatively, if $R(e)$ is finite, then all reduction sequences for $e$ terminate. So it looks like computing $R(e)$ almost allows you to solve the Halting Problem - except that I gather some expressions have both terminating and non-terminating reduction sequences, so that doesn't quite work.

share|improve this question
Given that there are expressions which have infinite reduction sequences, your function is not even finite... –  Zhen Lin Jun 1 '12 at 14:15
@ZhenLin Sure. But 1/x is not finite when x=0, and it's still perfectly computable... –  MathematicalOrchid Jun 3 '12 at 19:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.