We give a modern computational introduction to the S,K combinators invented by Moses Sch\"onfinkel in 1920, and present a variety of new results and ideas about combinators. We explore the spectrum of behavior obtained with small combinator expressions, showing a variety of approaches to analysis and visualization. We discuss the implications of evaluation strategies, and of multiway systems representing all possible strategies. We show how causal graphs introduced in recent models of fundamental physics can be applied to combinators, as well as describing how combinators introduce a new form of treelike separation. We give a variety of new results on minimal combinator expressions, as well as showing how empirical computation theory and computational complexity theory can be done with combinators. We also suggest that when viewed in terms of ongoing computation, the S combinator alone may be capable of universal computation.
翻译:我们对1920年Moses Sch\'onfinkel发明的S,K 组合器进行现代的计算介绍,并介绍关于组合器的各种新结果和想法。我们用小组合器表达式探索获得的行为范围,展示各种分析和可视化的方法。我们讨论了评估战略和代表所有可能战略的多路系统的影响。我们展示了如何将最近基本物理学模型中引入的因果图应用于组合器,并描述了组合器如何引入一种新的树形分离形式。我们对最小组合器表达式提供了各种新结果,并展示了如何用组合器进行实验性计算理论和计算的复杂性理论。我们还建议,从不断计算的角度看,光是组合器就能够进行普遍计算。