Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper formalizes the concept of "emulation-completeness" for programming languages, which goes beyond Turing-completeness to require that a language can emulate its own programs while preserving guest-visible state like control flow and runtime metadata. It introduces a taxonomy distinguishing between source-level and compiled-code emulation, as well as weak and strong emulation-completeness based on the fidelity of preserved runtime behavior. The paper then categorizes requirements for emulation-completeness into language-side (expressiveness) and emulator-side (faithful masking/reproduction of observations), illustrated with examples from Erlang.
Turing-completeness doesn't guarantee a language can faithfully emulate itself, because preserving guest-visible state like timing, memory usage, and stack traces introduces a whole new level of complexity.
We study when a programming language can emulate programs written in that same language without delegating the guest program back to the host evaluator or compiler. We call this property emulation-completeness. The central observation is that Turing-completeness by itself is not enough: a self-emulator must not only compute the guest program's result, but must also account for the guest-visible state on which realistic programs depend, including control flow, exceptions, callbacks, timing, memory usage, and runtime metadata such as stack traces or line numbers. This paper is a systematization paper. Its contribution is not a new emulator implementation, but a precise vocabulary and a structured taxonomy for reasoning about self-emulation. We distinguish source-level evaluation from compiled-code emulation, define syntactic and compiled-code emulation-completeness, and separate weak from strong emulation-completeness according to how much observable runtime behavior must be preserved. We then organize the requirements into two classes: language-side requirements, which determine whether the guest semantics can be represented explicitly inside the language, and emulator-side requirements, which determine whether the resulting emulator can faithfully mask or reproduce relevant observations. The discussion is grounded by concrete examples, including publicly documented details from Erlang, where argument limits, bitstring pattern matching, and message reception expose subtle mismatches between direct execution and self-emulation. The resulting framework is intended as guidance for language designers, implementers of evaluators and emulators, and researchers interested in secure sandboxing, decompilation, and reflective execution.