Towards Empirical Computer Science

Part I presents a model of interactive computation and a metric for expressiveness, part II relates inter- active models of computation to physics, and part III considers empirical models from a philosophical perspective. Interaction machines, which extend Turing machines to interaction, are shown in Part I to be more expressive than Turing machines by a direct proof, by adapting Godel’s incompleteness result, and by observability metrics. Observa- tion equivalence provides a tool for measuring expressiveness according to which interactive systems are more expressive than algorithms. Refinement of function equivalence by observation of outer interactive behavior and inner computation steps are examined. The change of focus from algorithms specified by computable functions to interac- tion specified by observation equivalence captures the essence of empirical computer science.
Part II relates interaction in models of computation to observation in the natural sciences. Explanatory power in physics is specified by the same observability metric as expressiveness in interactive systems. Realist models of inner structure are characterized by induction, abduction, and Occam’s razor. Interactive realism extends the hidden-vari- able model of Einstein to hidden interfaces that provide extra degrees of freedom to formulate hypotheses with test- able predictions conforming with quantum theory. Greater expressiveness of collaborative computational observers (writers) than single observers implies that hidden-interface models are more expressive than hidden-variable models. By providing a common foundation for empirical computational and physical models we can use precise results about computational models to establish properties of physical models.
Part III shows that the evolution in computing from algorithms to interaction parallels that in physics from ratio- nalism to empiricism. Plato’s cave metaphor is interactively extended from Platonic rationalism to empiricism. The Turing test is extended to TMs with hidden interfaces that express interactive thinking richer than the traditional Tur- ing test. Interactive (nonmonotonic) extensions of logic such as the closed-world assumption suggest that interactive- ness is incompatible with monotonic logical inference. Procedure call, atomicity of transactions, and taking a fixed point are techniques for closing open systems similar to “preparation” followed by “observation” of a physical sys- tem. Pragmatics is introduced as a framework for extending logical models with a fixed syntax and semantics to mul- tiple-interface models that support collaboration among clients sharing common resources.