Patterns in Combinator Evolution
Eric James Parfitt
eparfitt84@gmail.com
Abstract
Rules for speeding up SK combinator evaluation were investigated, and experiments were performed to determine the proportion of SK combinator expressions that reach a fixed point before exceeding certain computational limits. It was found that approximately 80.3 percent of SK combinator expressions with size 100 reach a fixed point within 300 steps and also without having reached a combinator size of 200000 sometime during evaluation.
