Complex Systems

Patterns in Combinator Evolution Download PDF

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.