Complex Systems

Patterns in Combinator Evolution Download PDF

Eric James Parfitt


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.