Theoretical Limits on AI Code Transformation You Can't Always Get There From Here

Introduction

One of my favorites experiences of trimming unfruitful work directions thanks to theoretical results happened when I discovered this 2001 article from Jeroen Voeten: On the fundamental limitations of transformational design.

For context, when I discovered this article (around 2010), I was working on delivering an “optimizing compiler” for a novel microprocessor architecture. Some more senior researcher than me had been floating the idea that compiler technology was underrated, because (paraphrasing) “with a sufficiently advanced compiler, we could take an arbitrary human specification and produce an optimal implementation given a target architecture”. With my past experience building compilers, I found this claim fantastical—a case of magical thinking, really—but I was not able to fully explain why. Reading Jeroen Voeten’s article, soon afterwards, put a rest to this argument: no, such compilers can’t be made. Or we couldn’t call them “compilers.”

Jeroen Voeten’s original argument was motivated by research in microchip specification systems (e.g. VHDL). However, as we see below, it also applies to any computing system where we use algorithms to transform one system into another (e.g. program transformation, software refactoring, etc.) and desire confidence that the transformation is semantics-preserving, e.g. it does not introduce new problems that were not there originally.

How this relates to generative AI: yesterday, I offered to model the combination of a human operator + AI programming agent as a computing system, which we called “HACS”, and explore if results from computing theory could apply. Today, we explore how yesterday’s argument expands when we focus on the findings from Jeroen Voeten’s article, to explore the following question: in which areas can we expect theoretical limits to the ability of AI programming workflows to transform software?

Remember, again, that I am not a computer theoretist. While I am familiar with the theory, I am unable to formalize the ideas that follow as a professional theoretist would. This is an exploration.

I. The core insight from Jeroen Voeten (2001)

Setup:

• Design space \(\mathcal{D}\): all syntactically valid programs/designs
• Semantic equivalence \(\equiv\): programs with the same meaning
• Transformation system \(\mathcal{T}\): a set of transformations \(t: \mathcal{D} \rightarrow \mathcal{D}\)
• Correctness: transformations preserve equivalence: \(d \equiv t(d)\)

The partition argument: if each transformation \(t \in \mathcal{T}\) is:

1. Semantics-preserving: \(d \equiv t(d)\)
2. Invertible: there exists \(t^{-1}\) such that \(t^{-1}(t(d)) = d\)

Then \(\mathcal{T}\) generates a group action on \(\mathcal{D}\), and the orbits of this action partition \(\mathcal{D}\) into disjoint equivalence classes under reachability.

SEMANTIC EQUIVALENCE CLASS [d]≡
┌──────────────────────────────────────────────────┐
│                                                  │
│    ┌─────────────┐          ┌─────────────┐      │
│    │  Subspace 1 │          │  Subspace 2 │      │
│    │   (orbit    │          │   (orbit    │      │
│    │   under T)  │          │   under T)  │      │
│    │      ●──●   │          │    ●──●──●  │      │
│    │     /    \  │          │    │     │  │      │
│    │    ●      ● │          │    ●─────●  │      │
│    └─────────────┘          └─────────────┘      │
│           ╳ UNREACHABLE ╳                        │
│                                                  │
│    ┌─────────────┐          ┌─────────────┐      │
│    │  Subspace 3 │   ...    │  Subspace ∞ │      │
│    │    ●──●──●  │          │     ●──●    │      │
│    └─────────────┘          └─────────────┘      │
│                                                  │
└──────────────────────────────────────────────────┘

All designs in the big box are SEMANTICALLY EQUIVALENT.
But you can only REACH designs within your starting subspace.

The fundamental result: your starting point determines your reachable solutions.

Even if there exists a “better” implementation (faster, smaller, cleaner) that is semantically equivalent to your specification, it may be provably unreachable through any sequence of correctness-preserving transformations.

II. Mapping to HACS (Coding Agents)

Agent transformations are not invertible, therefore more limits

Voeten shows that even with a group structure (invertible transformations), you get infinitely many unreachable subspaces.

However, coding agents may not be able to invert actions, because:

1. The inverse requires knowing the previous state
2. The previous state may have fallen out of the context window
3. Therefore the agent has “forgotten” how to undo

This means the agent’s effective transformation system is actually a monoid (or worse, just a semigroup), not a group. The algebraic structure is weaker. So we have:

1. Not all transformations are invertible
2. So we don’t even get clean partitions, we get directed reachability
3. Some states are “sinks” you can reach but not escape
4. The reachability relation is a preorder, not an equivalence

NON-INVERTIBLE TRANSFORMATION SYSTEM

  ●──→──●──→──●
       ↘     ↓
         ●──→──●──→──● (sink: can enter, can't leave)
              ↗
  ●──→──●──→──●

Arrows show reachability. No inverse arrows means no escape.

This doesn’t weaken the fundamental limitation; if anything, it strengthens it. Not only are some equivalent programs unreachable, but the agent can also wander into “sink” regions from which better solutions become unreachable even if they weren’t originally.

For the remainder of this essay, when we refer to “partitions” or “subspaces,” we mean this informally: regions of the design space that are mutually unreachable. The formal object in the HACS case is more complex than Voeten’s clean partitions, but the practical implication is the same or worse.

III. The “over-specification” problem for agents

Key phrase from the original article: “each specification is an over-specification.”

For HACS, this translates to the following.

IV. The Halting Problem connection

This is the connection to our earlier halting problem discussion.

V. Escape hatches: how to break out of subspaces

If Voeten’s result is so limiting, how do we ever make progress? There are several “escape hatches”.

Subspace A ─(break semantics)-> Invalid state ─(fix)-> Subspace B

VI. Relating to complexity classes

Let’s try to revisit our earlier HACS complexity hierarchy.

VII. Practical implications

VIII. Prompt interpretation as implicit specification

Question: Is the agent’s “understanding” a form of implicit specification?

When an agent interprets a prompt with specific semantics (e.g. with references to working code), it collapses ambiguity into a specific understanding. That understanding may implicitly place the agent in a particular subspace before any new code is written.

If true, then:

• Chain-of-thought reasoning is “early specification”
• Different reasoning traces result in different subspaces
• “Prompt engineering” is partly subspace selection

This suggests that how the agent interprets the prompt (not just what code it writes) is subject to the same partition constraints.

IX. Open questions

1. Is the partition structure empirically observable? Can we find real examples of codebases where a “better” implementation is provably unreachable? I suspect yes, but I don’t have a concrete case.
2. How fragmented is the space in practice? The original article proves infinite partitions exist, but maybe most practical cases are in “well-connected” regions?
3. Is finite-domain equivalence a useful approximation? The original article shows that restricting to finite input domains makes equivalence decidable. Does this suggest a practical middle ground, i.e. transformations that preserve behavior on “sufficiently large” test sets?

References

• J.P.M. Voeten, On the fundamental limitations of transformational design, 2001. ACM TDAES, Vol 6(4), pp. 533-552. DOI 10.1145/502175.502181
• Wikipedia, Rice’s theorem