# Is the number of reduction orders a computable function?

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.

-
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