Historic working paper. An early, DOI-published draft preserved for historical reference. Its implementation terminology predates the current PGS compiler and runtime architecture and is superseded by the current Papers. Figures survive only in the canonical PDF below.
Download PDF (canonical, with figures)
Categories: Software Engineering (cs.SE), Programming Languages (cs.PL), Computational Complexity (cs.CC)
Keywords: Turing completeness, universal computation, protocol governance, declarative systems, constitutional architecture, deterministic execution, auditability, AI-era software
Introduction
Motivation: Why Turing Completeness Is No Longer Enough
The theory of computation has long celebrated Turing completeness as the definitive measure of computational power. A system is deemed “complete” if it can simulate any Turing machine—if it can compute any function that is computable in principle . This criterion, established nearly a century ago, remains the benchmark against which programming languages, virtual machines, and computational models are evaluated.
Yet Turing completeness, as classically formulated, is silent on questions that dominate contemporary software engineering. It says nothing about governance—who may authorize computation and under what constraints. It says nothing about auditability—whether execution can be inspected, replayed, or verified. It says nothing about semantic stability—whether a system’s meaning can be preserved as its implementation evolves.
These omissions were tolerable when computation was a scarce resource, carefully managed by human programmers who understood both intent and implementation. They become intolerable in the AI era, where large language models generate code at velocities that exceed human capacity to audit . When AI produces the majority of production software—a transition industry analysts project within this decade —the question shifts from “Can this system compute?” to “Can this system be governed?”
A system may be Turing complete and yet ungovernable: its behavior implicit, its side effects unbounded, its execution irreproducible. Such systems pose existential risks in domains requiring regulatory compliance, financial accountability, or safety-critical operation. The classical criterion of computational universality provides no protection.
This paper argues that Turing completeness must be reconceived—not abandoned, but reframed. We seek systems that are universally expressive yet constitutionally constrained: capable of computing any computable function while remaining bounded by explicit governance, traceable through observable execution, and resilient to semantic drift under implementation evolution.
The Governance Deficit in Classical Computation Models
Classical computational models—Turing machines, lambda calculus, register machines—share a characteristic that renders them unsuitable as foundations for governed systems: they are semantically unconstrained.
A Turing machine’s tape is infinite and arbitrarily mutable. Its transition function may encode any computable behavior. There is no authority that sanctions state changes, no trace that records execution history, no invariant that constrains permissible operations. The machine simply computes, and computation is its own justification.
This unconstrained expressiveness was precisely the point. Church, Turing, and their contemporaries sought to characterize the limits of computation—what could and could not be computed in principle . Governance was not merely absent from their models; it was deliberately excluded to achieve mathematical generality.
Modern systems inherit this unconstrained heritage. Programming languages, virtual machines, and execution runtimes provide Turing-complete expressiveness without governance mechanisms. Any behavior that is computable is permissible. Constraints, when they exist, are bolted on after the fact through static analysis, runtime monitoring, or procedural controls. These mechanisms inspect computation from the outside; they do not arise from computational architecture itself.
Protocol-governed systems take a different approach. Governance is not external to computation but constitutive of it. Behavioral constraints are not inspected after the fact but encoded in the very artifacts that define computable behavior. The question “Is this computation permitted?” has a structural answer, not a procedural one.
Contribution Summary
This paper makes three contributions to the foundations of governed computation:
Architectural Reframing of Turing Completeness. We demonstrate that Turing completeness can be realized as a property of protocol-governed architecture rather than a feature of programming languages. Universal computation emerges from declarative artifact composition, not imperative code execution.
Constitutionally Constrained Computation. We introduce and formalize the concept of constitutionally constrained computation: systems that achieve universal expressiveness while remaining bounded by explicit governance, traceable through execution observation, and resilient to semantic drift.
Governance as Architectural Primitive. We argue that governance must be treated as a first-class architectural concern—not as an external constraint on computation but as an intrinsic property of computational systems. This reframing is essential for AI-era software where execution velocity exceeds human audit capacity.
Background: Classical Models of Universal Computation
The Turing Machine as Semantic Idealization
Alan Turing’s 1936 paper “On Computable Numbers” introduced the abstract machine that bears his name . The Turing machine comprises an infinite tape divided into cells, a head that reads and writes symbols, a finite state register, and a transition function that determines head movement and symbol modification based on current state and symbol.
The power of the Turing machine lies in its universality. A universal Turing machine can simulate any other Turing machine given an encoding of that machine’s transition function . This simulation capability establishes the machine as a model of general computation—a mathematical formalization of what it means to compute.
Yet the Turing machine is not a blueprint for governed computation. Its tape is infinite and unconstrained; any cell may be modified at any time. Its transition function is opaque; no external observer can determine why a state change occurred without simulating the entire computation. Its execution produces no trace; the only observable output is the final tape configuration (if the machine halts).
These properties were virtues for Turing’s purpose: characterizing the theoretical limits of computation. They are deficits for our purpose: building systems whose behavior can be governed, audited, and preserved across implementation evolution.
Modern Computational Descendants
The Turing machine’s descendants populate contemporary computing:
Lambda Calculus. Church’s concurrent development of lambda calculus provides an equivalent model of computation based on function abstraction and application rather than state mutation . Lambda calculus is computationally universal and foundational to functional programming. Yet it, too, is governance-silent: any lambda term may be constructed, and reduction proceeds without constraint.
Register Machines. Register machines model computation through finite registers and simple operations (increment, decrement, conditional branch) . They are closer to physical hardware than Turing machines while maintaining computational universality. Yet they inherit the same governance deficit: registers may be arbitrarily modified, and execution is unconstrained.
Virtual Machines and Bytecode Runtimes. Modern virtual machines (JVM, CLR, WASM) provide portable execution environments for compiled bytecode. They achieve practical universality within their instruction sets. Yet bytecode execution remains fundamentally unconstrained: any sequence of valid instructions may execute, and governance is external to the execution model.
What Classical Models Omit
Four concerns absent from classical computational models are central to governed systems:
Classical models include no concept of authorization. Any computation that can be encoded can execute. There is no distinction between permitted and prohibited behavior at the model level.
Classical models produce no execution trace. The only observable artifact is the final result (if computation terminates). Intermediate states, decision points, and execution paths are invisible.
Classical models provide no mechanism for reproducing execution. Given the same program, different runs may produce different results due to non-determinism, timing dependencies, or external state.
Classical models provide no mapping between execution events and declared behavioral intent. The “why” behind any state change must be inferred from code inspection, not observed from execution evidence.
These omissions are not accidents. They reflect the mathematical purpose of classical models: characterizing computability, not constraining it. A foundation for governed computation must address these concerns architecturally, not procedurally.
Protocol-Governed Execution: A Different Starting Point
Separation of Behavior and Execution
Protocol-governed systems begin from a fundamentally different architectural premise: the strict separation of what a system does (behavior) from how it does it (execution) .
Protocol artifacts are declarative, version-controlled specifications that define permissible system behavior. They declare workflows, capability contracts, actor authorities, and state transitions in explicit, machine-readable form. Protocol artifacts are the constitutional law of the system—the authoritative specification against which all execution is measured.
Execution engines interpret protocol artifacts deterministically. They compile declarative specifications into executable structures, route operations to appropriate handlers, and produce traces that witness execution. Crucially, execution engines are semantically blind: they have no knowledge of business domain meaning. They enforce protocol structure without understanding protocol semantics.
This separation enables a property unavailable in classical computational models: implementation replaceability. Execution engines can be optimized, rewritten, or AI-generated without altering system behavior, provided they produce equivalent traces. Behavioral equivalence is verified mechanically through trace comparison, not through code review.
Constitutional Constraints as First-Class
In protocol-governed systems, constraints are not external to computation but constitutive of it:
The protocol vocabulary defines the complete space of possible behaviors. Behaviors not expressible in the vocabulary cannot occur. This is not a limitation but a feature: the behavioral surface is explicitly bounded and auditable.
All world-affecting operations are declared in capability contracts. There are no ambient side effects, no hidden mutations, no implicit external interactions. The system’s risk profile is proportional to its declared side-effect surface.
Every execution produces a structured trace that witnesses what occurred. Traces are the canonical evidence of system behavior—they enable replay, verification, and audit without implementation inspection.
Computational Primitives in a Protocol-Governed System
Protocol-governed computation rests on four architectural primitives that collectively enable universal expressiveness while preserving governance. These primitives are described at the semantic level, without reference to specific encodings or implementation mechanisms.
State Representation
Classical Model: The Turing machine’s infinite tape provides unbounded, arbitrarily-mutable storage. Any cell may be read or written at any time. State mutation is the fundamental computational act.
Protocol-Governed Model: State exists as protocol-declared artifacts and governed side effects. State transitions occur only through explicitly declared capability side effects. There is no ambient mutable memory—all storage is named, versioned, and traced.
The key distinction is explicitness. In classical models, state is implicit infrastructure. In protocol-governed models, state is declared behavioral surface. Every state container has a name, a governance contract, and a modification trace.
This explicitness does not reduce expressiveness. Any state structure that can be represented on a Turing tape can be represented in governed storage. The difference is that governed storage maintains provenance: who authorized the state, when it changed, and through what protocol operation.
Control Flow
Classical Model: Turing machines and their descendants achieve control flow through transition functions, conditional branches, and unbounded loops. Control can jump to any reachable state.
Protocol-Governed Model: Control flow is expressed through declarative workflow orchestration. Workflows define directed acyclic graphs of operations, with branching expressed as conditional node routing rather than imperative jumps.
The question arises: can acyclic workflow structures express the unbounded iteration required for Turing completeness? The answer is yes, through lawful re-invocation. A workflow may invoke another workflow, including (through versioning) workflows that achieve equivalent behavioral recursion. The recursion is not lexical but semantic: it occurs through protocol-declared invocation paths, not through goto-equivalent jumps.
Computation
Classical Model: Computation occurs through primitive operations on state—symbol writes on the Turing tape, beta reductions in lambda calculus, register modifications in register machines.
Protocol-Governed Model: Computation occurs through capability transforms: pure, deterministic functions that accept declared inputs and produce declared outputs. Transforms have no side effects; they are replayable, cacheable, and compositional.
Expressiveness emerges through composition. Complex computations assemble from primitive transforms through workflow orchestration. Each transform is independently testable and governable. The composition itself is declared in protocol artifacts, not implicit in code structure.
Observation
Classical Model: Observation is external to the computational model. A Turing machine produces a final tape configuration; intermediate states are visible only through simulation.
Protocol-Governed Model: Observation is intrinsic to computation. Every execution produces events—structured records of what occurred, in what order, with what inputs and outputs. Events are emitted facts, not commands; they cannot be suppressed, modified, or filtered by execution logic.
The trace—the ordered sequence of events—is the canonical witness of system behavior. It enables replay (re-executing computation from trace produces identical results), audit (external observers can verify behavior without implementation access), and verification (behavioral equivalence across engine implementations is mechanically provable).
Conditions for Turing Completeness Under Governance
Minimal Requirements for Universal Computation
The Church-Turing thesis establishes that any system capable of simulating a Turing machine can compute any computable function . The minimal requirements for such simulation are well-characterized:
Unbounded Storage: The system must be capable of storing an arbitrarily large amount of symbolic information.
Conditional Branching: The system must be capable of executing different operations based on stored state.
Unbounded Iteration: The system must be capable of repeating operations an arbitrary number of times.
These requirements are necessary and sufficient. Any system satisfying them can simulate a Turing machine; any system failing to satisfy them cannot .
How Protocol-Governed Systems Satisfy These Requirements
Protocol-governed systems satisfy the requirements for Turing completeness through their architectural primitives:
Unbounded Storage. Governed state containers (capability side effects) provide unbounded symbolic storage. While any physical implementation has finite bounds, the architectural model places no limit on state capacity. A governed storage contract can hold an arbitrarily large data structure, just as a Turing tape can hold an arbitrarily long symbol sequence.
Conditional Branching. Workflow orchestration provides declarative conditional branching. Workflow nodes may route to different successors based on state conditions. This is semantically equivalent to the Turing machine’s transition function: current state determines next operation.
Unbounded Iteration. Lawful re-invocation enables unbounded iteration. Lawful re-invocation is semantically equivalent to recursion, not syntactic recursion. A workflow may invoke operations that, through protocol-governed recursion, repeat an arbitrary number of times. Unlike imperative loops, this iteration occurs through declared invocation paths—but the computational power is equivalent.
Why Governance Does Not Reduce Expressiveness
A potential objection: does constitutional constraint reduce computational power? If behaviors are vocabulary-bounded, can all computable functions be expressed?
The answer is no—governance does not reduce expressiveness—for a fundamental reason: governance constrains mechanism, not outcome. A governed system may compute any function that an ungoverned system can compute. The difference is in how computation is achieved:
In ungoverned systems, computation proceeds through arbitrary state mutation and control flow.
In governed systems, computation proceeds through declared artifacts, explicit transitions, and traced execution.
The space of computable outcomes is identical. The space of permissible mechanisms is constrained. This is precisely the architectural property we seek: universal expressiveness with bounded mechanism.
Proposition 1 (Governance-Expressiveness Independence). Let
$\mathcal{C}$ be the class of computable functions. Let
$\mathcal{P}$ be a protocol-governed system satisfying the conditions
of Section 5. Then for any
$f \in \mathcal{C}$, there exists a protocol specification $\pi$
such that $\mathcal{P}$ executing $\pi$ computes $f$.
The proposition asserts that governance does not exclude any computable function from the system’s expressive range.
Comparison to Classical Turing Machines
The following comparison illuminates the architectural distinction between classical and protocol-governed computation:
| Aspect | Classical TM | Protocol-Governed |
|---|---|---|
| State | Infinite tape, implicit | Governed containers, explicit |
| Control | Transition function | Declarative workflow law |
| Mutation | Implicit, unconstrained | Explicit, traced |
| Semantics | Inferred from execution | Declared in artifacts |
| Auditability | None (external only) | Structural (trace-based) |
| Governance | None | Constitutional |
| Replaceability | Implementation-bound | Engine-independent |
| Authority | Absent | First-class |
Architectural comparison: Classical Turing Machine vs. Protocol-Governed System.
The comparison reveals that protocol-governed systems add governance dimensions absent from classical models while preserving computational universality. This is not a trade-off but an augmentation: governed systems can do everything classical systems can do, plus provide auditability, authority, and semantic stability.
The Governance Invariant
We can state the relationship formally:
Theorem 1 (Informal). A protocol-governed system with unbounded governed storage, conditional workflow branching, and lawful re-invocation can simulate any Turing machine while maintaining complete execution traceability.
The significance is that traceability is not purchased at the cost of expressiveness. The two properties are orthogonal: one concerns what can be computed; the other concerns how computation is witnessed.
Why This Is Not Merely a Turing Machine With Logging
A superficial reading might dismiss protocol-governed computation as “a Turing machine with logging.” This misses the architectural distinction:
In a “Turing machine with logging,” logging is an external observation of an unconstrained computation. The machine computes as it pleases; the log records what happened. Logging does not constrain the machine, and the machine’s behavior is defined independently of logging.
In a protocol-governed system, traceability is constitutive of computation. Execution cannot occur except through governed pathways that produce traces. There is no “underlying computation” that is separately logged. The computation is the traced execution of declared behavior.
This distinction matters for governance. A logged Turing machine can be audited, but auditing is external and after-the-fact. A protocol-governed system is governed intrinsically—behavior that cannot be declared cannot be computed.
Is Constrained Computation an Anti-Pattern?
The Objection: Constraints Limit Power
A reasonable objection arises: constraints are generally understood to limit capability. If we constrain how computation occurs, do we not limit what computation can achieve?
This objection conflates two senses of “limit”:
Outcome Limitation: Reducing the set of computable results
Mechanism Limitation: Reducing the set of permissible computational paths
Protocol governance imposes mechanism limitation, not outcome limitation. Any computable outcome remains achievable; the paths to that outcome are disciplined.
Consider an analogy: traffic laws constrain how vehicles may travel, but they do not limit where vehicles can go. A driver obeying traffic laws can reach any destination a lawless driver can reach. The journey is different; the destination space is unchanged.
Why Constraint Is a Feature
In the context of governed systems, mechanism limitation is precisely what is desired. The goal is not to prevent any particular computation but to ensure that all computation occurs through auditable, authorized, traceable channels.
Consider the alternative: a system with unconstrained computational power that can produce any side effect, invoke any external service, and modify any state without governance. Such a system is maximally powerful and minimally governable. Its behavior cannot be predicted from its artifacts, verified through its traces, or constrained by its architecture.
Protocol governance trades mechanism freedom for behavioral clarity. This is the right trade-off for systems requiring:
Long-term auditability
Regulatory compliance
Multi-stakeholder governance
AI-assisted development with preserved meaning
Safety-critical operation
Expressiveness Through Composition
Protocol-governed systems achieve expressiveness through composition rather than primitive complexity. Simple, well-governed primitives combine to produce complex behavior. The composition itself is declared, versioned, and governed.
This compositional approach offers advantages beyond governance:
Testability: Primitive transforms are independently testable
Reusability: Governed primitives compose across workflows
Evolvability: New behaviors emerge from novel compositions of stable primitives
Comprehensibility: Complex behavior decomposes into understood components
Implications for the AI Era
AI as Execution Generator, Not Law Author
The emergence of AI-assisted software development creates both opportunity and risk . AI excels at generating implementation code—the mechanical translation of behavioral intent into executable instructions. AI struggles to preserve behavioral semantics when refactoring, optimizing, or extending existing systems .
Protocol-governed architecture aligns with AI capabilities. AI may generate, optimize, and replace execution engines without constraint, provided the engines conform to protocol specifications. Behavioral equivalence is verified mechanically through trace comparison. AI becomes an execution generator, not a law author.
The protocol—the declarative specification of what the system does—remains under human governance. AI contributes implementation; humans govern behavior. This division of labor exploits AI strengths while mitigating AI risks.
Semantic Drift Resistance
Semantic drift—the gradual divergence between intended and actual system behavior—is endemic to imperative software . Each modification risks subtle behavioral change. Over time, systems become inscrutably different from their original specifications.
Protocol-governed systems resist semantic drift structurally. Behavioral specification exists independently of implementation. Execution engines may evolve, optimize, or be replaced, but the behavioral specification remains authoritative. Conformance verification ensures that implementation evolution does not introduce semantic divergence.
This property is essential for AI-accelerated development. When AI modifies implementation at velocities exceeding human audit capacity, the only viable governance strategy is specification-based verification. If behavior is defined by implementation, AI modification is ungovernable. If behavior is defined by protocol, AI modification is verifiable.
The Governance Imperative
We can now state the core argument: in AI-accelerated software environments, governance must be architectural, not procedural.
Procedural governance—code review, testing, documentation—scales with human velocity. As AI increases implementation velocity, procedural governance becomes the bottleneck. Review backlogs grow; testing coverage declines; documentation diverges from implementation.
Architectural governance—specification-based verification, trace-based conformance, vocabulary-bounded behavior—scales with machine velocity. Conformance verification is automated. Behavioral equivalence is mechanically proven. Semantic drift is structurally prevented.
Protocol-governed architecture provides architectural governance. It is not merely a software pattern but a governance strategy adapted to the realities of AI-accelerated development.
Related Work
Turing Machines and Computational Theory
The foundation of computability theory rests on Turing’s seminal work establishing the limits of mechanical calculation . Church’s lambda calculus provides an equivalent formulation through function abstraction . Subsequent developments—recursive function theory , register machines —provided alternative characterizations of the same computational class. These works characterize what can be computed but do not address how computation should be governed.
Formal Specification Languages
TLA+ enables rigorous behavioral specification through temporal logic . Alloy provides lightweight formal methods through relational modeling . Z and VDM offer mathematical notation for software specification . These approaches share protocol-governed architecture’s emphasis on declarative behavioral specification.
The distinction is execution authority. Formal specification languages traditionally separate specification from implementation: the specification is verified, then translated to code, then executed. Protocol-governed architecture maintains specification authority through execution. The specification is not translated but interpreted; it remains authoritative throughout the system lifecycle.
Workflow Systems
Workflow engines based on Petri nets and BPMN provide orchestration governance: they control the sequencing and routing of computational steps. However, workflow engines typically delegate semantic authority to the code invoked at each step. The workflow declares when operations execute; the operations themselves are governed (or not) independently.
Protocol-governed systems extend governance from orchestration to semantics. Capability contracts govern not just when operations execute but what operations are permitted, what inputs they accept, what outputs they produce, and what side effects they may cause.
Model-Driven Architecture
The OMG’s Model-Driven Architecture (MDA) separates platform-independent models from platform-specific implementations . Models are transformed into code, which is then compiled and executed.
The distinction from protocol governance is authority persistence. In MDA, the model generates code; the code becomes authoritative. In protocol-governed systems, the specification remains authoritative through execution. This difference is subtle but consequential: protocol-governed systems can verify behavioral equivalence across engine implementations because the specification, not the code, defines correct behavior.
Capability-Based Security
Capability-based security systems constrain computational authority through unforgeable tokens . A process may only perform operations for which it holds capabilities. This approach shares protocol governance’s emphasis on explicit authority.
Protocol-governed systems apply capability principles to behavioral governance, not just resource access. Capability contracts govern not only which resources a computation may access but what behaviors it may exhibit.
Limitations and Non-Goals
What This Paper Does Not Claim
This is not a programming language proposal. Protocol-governed computation is an architectural model, not a language design. The artifacts that declare behavior may be authored in various notations; the architecture is independent of authoring syntax.
This is not a new complexity class. Protocol-governed systems are Turing complete. They compute the same class of functions as classical models. The contribution is architectural, not computational-theoretic.
This is not a replacement for low-level systems programming. Operating systems, device drivers, and performance-critical infrastructure may require implementation patterns that protocol governance does not address. The architecture is optimized for business logic, compliance-critical systems, and long-lived applications.
Appropriate Domains
Protocol-governed computation is optimized for systems characterized by:
Long operational lifetimes (years to decades)
Multi-stakeholder governance requirements
Regulatory or compliance obligations
Behavioral auditability mandates
AI-assisted development with semantic preservation needs
Safety-critical or high-assurance domains
It is less applicable to short-lived scripts and utilities, performance-critical inner loops, systems requiring unconstrained low-level access, and exploratory or prototyping contexts.
Governance Overhead
Protocol governance imposes upfront costs. Behavioral specification requires explicit declaration of workflows, contracts, and authority. This overhead may not be justified for systems where governance is not a concern.
The architecture does not claim universal applicability. It claims that for systems where governance matters, architectural governance is superior to procedural governance, and constitutional constraint is compatible with computational universality.
Conclusion
The classical theory of computation answered the question “What can be computed?” Protocol-governed computation addresses a different question: “What can be computed while remaining governed?”
This paper has demonstrated that the answer is: anything. Turing completeness is achievable within constitutional constraint. Universal computation does not require unconstrained execution.
The key insights are:
Governance is architectural, not external. Constrained computation is not computation-with-governance-added but a different computational architecture in which governance is constitutive.
Constraint does not reduce expressiveness. The space of computable outcomes is unchanged. The space of permissible mechanisms is disciplined. Mechanism constraint enables governance without outcome limitation.
Traceability is intrinsic, not optional. Execution produces evidence. This evidence enables verification, audit, and behavioral equivalence proof—capabilities absent from classical computational models.
Implementation is replaceable. Execution engines are interchangeable. Behavioral equivalence is verified through trace comparison. AI may generate engines; humans govern behavior.
For the AI era, this reframing is essential. When AI generates the majority of production code, behavioral governance cannot rely on code inspection. It must rely on specification authority—declarative artifacts that define what systems do, independent of how they do it.
Protocol-governed computation provides that foundation. It preserves universal expressiveness while enforcing constitutional constraint. It enables computation that is simultaneously powerful and governable.
This is not a theoretical curiosity. It is an architectural necessity for systems that must remain auditable, deterministic, and semantically stable as implementation velocity accelerates beyond human governance capacity.
Computation becomes a governed act—not an accidental side effect.
License and Use
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).
You are free to share and redistribute this material in any medium or format, provided that: appropriate credit is given to the author, the material is not used for commercial purposes, and the material is not modified, transformed, or built upon.
The paper does not grant rights to implement patented methods, systems, or workflows that may be covered by pending or future patent claims.
For licensing inquiries or permissions beyond the scope of this license, contact the author.
Author Information
Bachi (aka Bhash Ganti)
Contact: bachipeachy@gmail.com
Conflict of Interest: The author is developing commercial implementations of the described architecture.
99
Bachi aka Bhash Ganti (2026a). Protocol-Governed Systems: An Architectural Foundation for the AI Era. Zenodo Working Paper. DOI: https://doi.org/10.5281/zenodo.18715516.
Barendregt, H.P. (1984). The Lambda Calculus: Its Syntax and Semantics. North-Holland, revised edition.
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H.P.O., Kaplan, J., et al. (2021). Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2):345–363.
Dennis, J.B. and Van Horn, E.C. (1966). Programming semantics for multiprogrammed computations. Communications of the ACM, 9(3):143–155.
GitHub (2023). GitHub Copilot research recitation. Technical report, GitHub.
Hopcroft, J.E., Motwani, R., and Ullman, J.D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 3rd edition.
Jackson, D. (2012). Software Abstractions: Logic, Language, and Analysis. MIT Press, revised edition.
Lamport, L. (2002). Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley.
Miller, M.S., Yee, K.-P., and Shapiro, J. (2003). Capability myths demolished. Technical report, Combex, Inc.
Minsky, M.L. (1967). Computation: Finite and Infinite Machines. Prentice-Hall.
Object Management Group (2011). Business process model and notation (BPMN) version 2.0. OMG Standard.
Object Management Group (2014). Model driven architecture (MDA) guide revision 2.0. OMG Document ormsc/14-06-01.
Parnas, D.L. (1972). On the criteria to be used in decomposing systems into modules. Communications of the ACM, 15(12):1053–1058.
Pearce, H., Ahmad, B., Tan, B., Dolan-Gavitt, B., and Karri, R. (2022). Asleep at the keyboard? Assessing the security of GitHub Copilot’s code contributions. In IEEE Symposium on Security and Privacy, pages 754–768.
Plotkin, G.D. (1981). A structural approach to operational semantics. Technical Report DAIMI FN-19, Computer Science Department, Aarhus University.
Rogers, H. (1987). Theory of Recursive Functions and Effective Computability. MIT Press.
Scott, D. and Strachey, C. (1971). Toward a mathematical semantics for computer languages. Proceedings of the Symposium on Computers and Automata, pages 19–46.
Shepherdson, J.C. and Sturgis, H.E. (1963). Computability of recursive functions. Journal of the ACM, 10(2):217–255.
Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3rd edition.
Spivey, J.M. (1989). The Z Notation: A Reference Manual. Prentice Hall.
Turing, A.M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42):230–265.
van der Aalst, W.M.P., ter Hofstede, A.H.M., Kiepuszewski, B., and Barros, A.P. (2003). Workflow patterns. Distributed and Parallel Databases, 14(1):5–51.