Empirical Computation: Prompting versus Programming

Large Language Model (LLM) agents can solve any computational problem without an algorithm in a runtime independent of the computational complexity of that problem. Instead of specifying precisely how to solve problem instance using programming, we ask an LLM to solve the problem instance using prompting. Outputs are sampled from a distribution rather than generated procedurally. In this vision paper, we explore the challenges and opportunities of this new form of computation and observe that its capabilities and limits cannot be understood within the classic, rationalist framework of computation. Hence, we appeal to the software engineering (SE) community to develop the foundations and techniques required to analyze the properties of this "empirical computation" as it generates solutions to computational problems: How can we analyze and improve the correctness of LLMs solving a computational problem in the general, in the problem-specific, or in the instance-specific? What are the properties and fundamental limits of empirical computation? This paper aims to establish empirical computation as a field in SE that is timely and rich with interesting problems.