Thoughts

Syntax, Semantics, and Computation: A Formal Theory of Indirect Turing Completeness

J

09 Mar 2025 — 13 min read

Introduction

The previous essays in this series have explored the computational nature of Large Language Models (LLMs) and their relationship to classical computation theory. In "Syntax, Semantics, and Computation: LLMs and Their Computational Boundaries," we established that LLMs themselves are not Turing-complete in the traditional sense due to their bounded context windows, fixed parameter spaces, and lack of persistent memory. However, they achieve what we termed "indirect Turing completeness" by generating code that, when executed by a Turing-complete interpreter, can theoretically compute any computable function.

This notion of indirect Turing completeness was further explored in "Syntax, Semantics, and Computation: Towards Reliable Indirect Turing Completeness," where we discussed potential programming language paradigms that could better accommodate the statistical, pattern-matching nature of LLMs to enhance the reliability of this indirect computation.

The present essay aims to establish a pure theoretical foundation for indirect Turing completeness. We will provide formal definitions, develop axiomatic principles, and prove key theorems that characterize this form of computation. By situating indirect Turing completeness within a rigorous mathematical framework, we seek to understand its fundamental properties, limitations, and implications for computational theory.

Preliminaries

Classical Computation

To establish our theory, we first revisit the standard definitions from classical computability theory.

Definition 1 (Turing Machine). A Turing Machine is a 7-tuple

$$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$$

where:

$Q$ is a finite set of states
$\Sigma$ is a finite input alphabet (not containing the blank symbol $\sqcup$)
$\Gamma$ is a finite tape alphabet ($\Sigma \subset \Gamma$ and $\sqcup \in \Gamma$)
$\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ is the transition function
$q_0 \in Q$ is the initial state
$q_{accept} \in Q$ is the accept state
$q_{reject} \in Q$ is the reject state, where $q_{reject} \neq q_{accept}$

Definition 2 (Configuration). A configuration of a Turing machine $M$ is a triple $(q, w, i)$ where $q \in Q$ is the current state, $w \in \Gamma^*$ is the contents of the tape, and $i$ is the position of the read/write head.

Definition 3 (Computation). A computation of a Turing machine $M$ on input $x$ is a sequence of configurations $(q_0, x, 0), (q_1, w_1, i_1), (q_2, w_2, i_2), \ldots$ where each configuration follows from the previous one according to the transition function $\delta$.

Definition 4 (Computable Function). A function $f: \Sigma^* \rightarrow \Sigma^*$ is computable if there exists a Turing machine $M$ such that for all $x \in \Sigma^*$, if $M$ is started in configuration $(q_0, x, 0)$, then $M$ eventually halts in configuration $(q_{accept}, f(x), i)$ for some position $i$.

Definition 5 (Turing-Complete System). A computational system $S$ is Turing-complete if for any Turing machine $M$, there exists a program $P_M$ in $S$ such that $P_M$ simulates $M$ on all inputs.

Probabilistic Computation

To account for the probabilistic nature of LLMs, we extend our framework to include probabilistic computation.

Definition 6 (Probabilistic Turing Machine). A Probabilistic Turing Machine (PTM) is a Turing machine where the transition function $\delta$ maps each state-symbol pair to a probability distribution over state-symbol-direction triples: $\delta: Q \times \Gamma \rightarrow \text{Dist}(Q \times \Gamma \times \{L, R\})$.

Definition 7 (Probabilistic Computation). A probabilistic computation of a PTM $M$ on input $x$ is a probability distribution over sequences of configurations, where the probability of a particular sequence is the product of the probabilities of the transitions between consecutive configurations.

Definition 8 (Probabilistic Computable Function). A function $f: \Sigma^* \rightarrow \text{Dist}(\Sigma^*)$ is probabilistically computable if there exists a PTM $M$ such that for all $x \in \Sigma^*$, the distribution of outputs when $M$ halts on input $x$ corresponds to $f(x)$.

Large Language Models

We now formalize LLMs within our theoretical framework.

Definition 9 (Large Language Model). A Large Language Model (LLM) is a function $L: \Sigma^* \rightarrow \text{Dist}(\Sigma^*)$ that maps an input string (prompt) to a probability distribution over output strings, subject to the following constraints:

The function is implemented by a fixed neural network with parameters $\theta$.
The input string is limited to a maximum length $k$ (the context window).
The function does not maintain state between invocations beyond the fixed parameters $\theta$.

Definition 10 (Code Generation). For an LLM $L$ and a programming language $P$ with semantics $[\![ \cdot ]\!]_P$, the code generation function $G_{L,P}: \Sigma^* \rightarrow \text{Dist}(P)$ maps a specification $s \in \Sigma^*$ to a probability distribution over programs in $P$.

Formal Definition of Indirect Turing Completeness

We now introduce the central concept of this essay: indirect Turing completeness.

Definition 11 (Indirect Turing Completeness). A system $S$ is indirectly Turing-complete via an interpreter $I$ if:

$S$ is not itself Turing-complete.
$S$ can generate strings that $I$ can interpret as programs.
For any computable function $f$, there exists an input $x$ to $S$ such that the interpretation by $I$ of $S(x)$ computes $f$.

For LLMs, this definition can be specialized as follows:

Definition 12 (LLM Indirect Turing Completeness). An LLM $L$ is indirectly Turing-complete via a programming language interpreter $I$ if for any computable function $f: \Sigma^* \rightarrow \Sigma^*$, there exists a specification $s_f \in \Sigma^*$ such that:

$$\exists p \in \text{supp}(G_{L,P}(s_f)) \text{ such that } \forall x \in \Sigma^*, [\![ p ]\!]_P(x) = f(x)$$

Where $\text{supp}(D)$ denotes the support of distribution $D$ (all outputs with non-zero probability).

This definition states that an LLM is indirectly Turing-complete if, for any computable function, there exists a specification that could prompt the LLM to generate a program that correctly computes that function.

However, this definition does not account for the probabilistic nature of LLMs. It only requires that a correct program exists in the support of the distribution, not that it has high probability. To address this, we introduce a stronger notion:

Definition 13 (Strong Indirect Turing Completeness). An LLM $L$ is strongly indirectly Turing-complete via a programming language interpreter $I$ if for any computable function $f: \Sigma^* \rightarrow \Sigma^*$ and any $\epsilon > 0$, there exists a specification $s_{f,\epsilon} \in \Sigma^*$ such that:

$$\Pr_{p \sim G_{L,P}(s_{f,\epsilon})}[\forall x \in \Sigma^*, [\![ p ]\!]_P(x) = f(x)] > 1 - \epsilon$$

This definition requires that for any computable function, there exists a specification that will prompt the LLM to generate a correct implementation with probability arbitrarily close to 1.

Theoretical Analysis of Indirect Turing Completeness

Having defined indirect Turing completeness, we now prove several key theorems about this concept.

Existence and Universality

Theorem 1 (Existence of Indirectly Turing-Complete LLMs). There exist LLMs that are indirectly Turing-complete.

Proof: Let $L$ be an LLM that has been trained on a comprehensive corpus of programming examples in a Turing-complete language $P$. We can construct a simple proof by considering the case where $L$ has memorized a universal interpreter or compiler for $P$.

For any computable function $f$, there exists a program $p_f$ in $P$ that computes $f$. Since $L$ has memorized this class of programs, there exists a specification $s_f$ (e.g., "Implement a program that computes function $f$") such that $G_{L,P}(s_f)$ assigns non-zero probability to $p_f$.

Therefore, $L$ is indirectly Turing-complete via the interpreter for $P$. ∎

While this proof establishes the theoretical possibility, it relies on the unrealistic assumption of perfect memorization. A more nuanced analysis is needed for practical LLMs.

Theorem 2 (Universality of Indirect Computation). If an LLM $L$ is indirectly Turing-complete via an interpreter $I$, then for any interpreter $I'$ for a Turing-complete language, $L$ is also indirectly Turing-complete via $I'$.

Proof: Since $L$ is indirectly Turing-complete via $I$, for any computable function $f$, there exists a specification $s_f$ such that $L$ can generate a program $p$ where $[\![ p ]\!]_I = f$.

Now, since $I'$ interprets a Turing-complete language, there exists a program $p'$ such that $[\![ p' ]\!]_{I'} = f$. Moreover, since the translation from $p$ to $p'$ is itself a computable function $t$, and $L$ is indirectly Turing-complete via $I$, there exists a specification $s_t$ such that $L$ can generate a program $p_t$ where $[\![ p_t ]\!]_I = t$.

Therefore, for any computable function $f$, we can construct a specification $s'_f$ that instructs $L$ to:

Generate a program in language $I$ that computes $f$
Translate that program to language $I'$

The resulting program $p'$ will satisfy $[\![ p' ]\!]_{I'} = f$, demonstrating that $L$ is indirectly Turing-complete via $I'$. ∎

Reliability and Error Bounds

The probabilistic nature of LLMs introduces uncertainty into indirect computation. We now analyze this uncertainty formally.

Definition 14 (Computational Reliability). The computational reliability of an LLM $L$ for a function $f$ under specification $s$ is:

$$R(L, f, s) = \Pr_{p \sim G_{L,P}(s)}[\forall x \in \Sigma^*, [\![ p ]\!]_P(x) = f(x)]$$

This measures the probability that $L$ generates a program that correctly implements $f$ when given specification $s$.

Theorem 3 (Reliability Bound for Universal Computation). For any LLM $L$ with fixed parameters, there exists a constant $c_L < 1$ such that for any enumeration of all computable functions $\{f_i\}_{i=1}^{\infty}$ and any sequence of specifications $\{s_i\}_{i=1}^{\infty}$:

$$\lim_{n \to \infty} \prod_{i=1}^{n} R(L, f_i, s_i) = 0$$

Proof: For any LLM $L$ with fixed parameters, there is a non-zero probability of error in generating any given program. Let $\epsilon_i = 1 - R(L, f_i, s_i)$ be the error probability for function $f_i$ with specification $s_i$.

Due to the complexity of the space of all computable functions, there exists a constant $\alpha > 0$ such that for any LLM $L$, the average error probability across all computable functions is at least $\alpha$: $\frac{1}{n}\sum_{i=1}^{n} \epsilon_i \geq \alpha$ for all sufficiently large $n$.

Therefore:
$$\prod_{i=1}^{n} R(L, f_i, s_i) = \prod_{i=1}^{n} (1 - \epsilon_i) \leq \left(1 - \frac{1}{n}\sum_{i=1}^{n} \epsilon_i\right)^n \leq (1 - \alpha)^n$$

As $n \to \infty$, $(1 - \alpha)^n \to 0$, which proves the theorem. ∎

This theorem establishes a fundamental limit on the reliability of LLMs for universal computation: no LLM can reliably compute all computable functions with high probability. This is a formal articulation of the intuition that statistical models will always have some errors when attempting to cover the entire space of computation.

Complexity Implications

The indirect nature of computation through LLMs has important implications for computational complexity.

Definition 15 (Specification Complexity). The specification complexity of a function $f$ with respect to an LLM $L$ and reliability threshold $\rho$ is:

$$SC_L(f, \rho) = \min\{|s| : R(L, f, s) \geq \rho\}$$

This measures the minimum length of a specification needed to get $L$ to generate a correct implementation of $f$ with probability at least $\rho$.

Theorem 4 (Specification Complexity Lower Bound). For any LLM $L$ and reliability threshold $\rho > 0$, there exist computable functions $f$ with Kolmogorov complexity $K(f)$ such that:

$$SC_L(f, \rho) \geq \Omega(K(f))$$

Proof: By the pigeonhole principle, the number of distinct specifications of length less than $n$ is $\sum_{i=0}^{n-1} |\Sigma|^i < |\Sigma|^n$. The number of functions with Kolmogorov complexity $K(f) \approx n$ is exponential in $n$.

For an LLM to reliably generate a function with high Kolmogorov complexity, the specification must provide sufficient information to identify that specific function among all functions of similar complexity. This requires a specification length that grows at least linearly with the Kolmogorov complexity of the function.

Therefore, $SC_L(f, \rho) \geq \Omega(K(f))$ for functions with sufficiently high Kolmogorov complexity. ∎

This theorem establishes that for complex functions, the specification provided to an LLM must itself be complex, placing fundamental limits on the "compression" of computational descriptions that LLMs can achieve.

Practical Implications of the Theory

Having established the formal theory of indirect Turing completeness, we now explore its practical implications for LLM-based computation.

The Reliability-Complexity Tradeoff

A key insight from our theoretical analysis is the fundamental tradeoff between reliability and complexity in indirect computation.

Corollary 1 (Reliability-Complexity Tradeoff). For an LLM $L$, as the complexity of a computable function $f$ increases, either:

The specification complexity $SC_L(f, \rho)$ must increase, or
The reliability threshold $\rho$ must decrease

This corollary follows directly from Theorem 4 and captures the intuition that for more complex computational tasks, LLMs either need more detailed specifications or will produce correct implementations with lower probability.

Verification and Error Detection

Our theoretical framework also has implications for verification of LLM-generated code.

Theorem 5 (Verification Completeness). Determining with certainty whether an LLM-generated program correctly implements a given specification is undecidable in general.

Proof: This follows directly from Rice's theorem, which states that any non-trivial semantic property of programs is undecidable. Determining whether a program correctly implements an arbitrary computable function is a non-trivial semantic property. ∎

However, we can establish bounds on approximate verification:

Theorem 6 (Probabilistic Verification). For any LLM $L$, computable function $f$, and $\delta > 0$, there exists a probabilistic verification procedure $V$ that, given a program $p$, outputs "correct" with probability at least $1-\delta$ if $[\![ p ]\!]_P = f$ and "incorrect" with probability at least $1-\delta$ if $[\![ p ]\!]_P \neq f$ on some input, using a finite number of test cases.

Proof: The verification procedure $V$ can randomly sample inputs $x_1, x_2, ..., x_n$ and check whether $[\![ p ]\!]_P(x_i) = f(x_i)$ for all $i$. By choosing $n$ sufficiently large and the distribution of test cases appropriately, the probability of failing to detect an incorrect implementation can be made arbitrarily small. ∎

This theorem suggests that while perfect verification is impossible, practical verification with high confidence is achievable through appropriate testing strategies.

Extended Theoretical Framework

We now extend our framework to account for more sophisticated aspects of indirect computation through LLMs.

Interactive Computation Model

In practice, LLM-based computation often involves multiple rounds of interaction, where feedback on initial code generations informs subsequent refinements. We can formalize this as follows:

Definition 16 (Interactive Indirect Computation). An interactive indirect computation with an LLM $L$ is a sequence of pairs $(s_1, p_1), (s_2, p_2), ..., (s_n, p_n)$ where:

$s_1$ is the initial specification
$p_i \sim G_{L,P}(s_i)$ is the program generated at step $i$
$s_{i+1} = h(s_i, p_i, r_i)$ where $r_i$ is feedback on $p_i$ and $h$ is a feedback incorporation function

Theorem 7 (Interactive Reliability Enhancement). For any LLM $L$, computable function $f$, and target reliability $\rho < 1$, there exists a feedback strategy such that the reliability of the final program $p_n$ in an interactive computation approaches $\rho$ as $n$ increases, provided that $L$ assigns non-zero probability to correct implementations of $f$.

Proof sketch: Let $E_i$ be the event that $p_i$ correctly implements $f$. The feedback strategy can identify specific inputs where $p_i$ fails and request corrections. If $L$ assigns non-zero probability to correct implementations, then $\Pr(E_{i+1} | \neg E_i) > 0$. The probability of correctness after $n$ rounds becomes:

$$\Pr(E_n) = 1 - \Pr(\neg E_1) \prod_{i=1}^{n-1} \Pr(\neg E_{i+1} | \neg E_i)$$

As $n$ increases, this probability approaches 1, allowing us to reach any target reliability $\rho < 1$ with sufficient rounds of interaction. ∎

Compositional Indirect Computation

Another important aspect of practical LLM-based computation is the composition of multiple generated components.

Definition 17 (Compositional Indirect Computation). A compositional indirect computation decomposes a function $f$ into components $f = g_n \circ g_{n-1} \circ ... \circ g_1$ where each component $g_i$ is implemented by a separate program $p_i$ generated by an LLM.

Theorem 8 (Compositional Reliability). For a compositional indirect computation of $f = g_n \circ ... \circ g_1$ with component programs $p_1, ..., p_n$ generated by an LLM $L$, the overall reliability is:

$$R(L, f, \{s_1, ..., s_n\}) \leq \prod_{i=1}^{n} R(L, g_i, s_i)$$

Proof: For the composed computation to be correct, each component must be correct. Since the generation of each component can be treated as an independent event (given appropriate specifications), the probability of all components being correct is the product of the individual reliabilities. ∎

This theorem highlights the challenge of building complex systems through composition: reliability decreases multiplicatively as more components are added, necessitating extremely high reliability for individual components in large systems.

Theoretical Extensions

We now consider several theoretical extensions that broaden the applicability of our framework.

Beyond Standard Computation

Our analysis has focused on standard computable functions, but the framework can be extended to other computational models.

Theorem 9 (Indirect Hypercomputation). An LLM cannot achieve indirect hypercomputation—the computation of functions not computable by Turing machines—through any Turing-complete interpreter.

Proof: By the Church-Turing thesis, no Turing-complete interpreter can compute functions beyond those computable by Turing machines. Since indirect computation through an LLM relies on a standard interpreter to execute the generated code, it is bounded by the computational power of that interpreter. ∎

This result confirms the intuitive notion that LLMs cannot "magically" overcome the fundamental limits of computation, despite their ability to perform sophisticated pattern recognition.

Approximation and Error Tolerance

For many practical applications, exact computation is unnecessary, and approximations are acceptable. We can formalize this notion:

Definition 18 ($\epsilon$-Approximate Computation). A program $p$ $\epsilon$-approximately computes a function $f: \Sigma^* \rightarrow \Sigma^*$ if for all $x \in \Sigma^*$, $d([\![ p ]\!]_P(x), f(x)) \leq \epsilon$, where $d$ is some appropriate distance metric.

Theorem 10 (Approximation Reliability Enhancement). For an LLM $L$, function $f$, and approximation threshold $\epsilon > 0$, the reliability of $\epsilon$-approximate computation is strictly greater than the reliability of exact computation:

$$\Pr_{p \sim G_{L,P}(s)}[\forall x, d([\![ p ]\!]_P(x), f(x)) \leq \epsilon] > \Pr_{p \sim G_{L,P}(s)}[\forall x, [\![ p ]\!]_P(x) = f(x)]$$

Proof: Every program that exactly computes $f$ also $\epsilon$-approximately computes $f$ for any $\epsilon > 0$. Additionally, there exist programs that do not exactly compute $f$ but do $\epsilon$-approximately compute it. Therefore, the set of programs that $\epsilon$-approximately compute $f$ is a strict superset of those that exactly compute $f$, leading to higher probability under any non-degenerate distribution. ∎

This theorem captures the intuition that allowing for approximation increases the reliability of LLM-based computation, which is particularly relevant for domains like scientific computing, optimization, and machine learning where approximate solutions are often sufficient.

Implications for Computational Theory

Our formalization of indirect Turing completeness has several profound implications for computational theory.

Revisiting the Church-Turing Thesis

The Church-Turing thesis states that any effectively calculable function can be computed by a Turing machine. Indirect computation through LLMs doesn't challenge this thesis in terms of what is computable, but it does raise questions about the nature of "effective calculability."

Definition 19 (Natural Language Calculability). A function $f$ is natural language calculable if there exists a natural language specification that can be reliably translated into an algorithm computing $f$ by a competent human programmer.

Conjecture 1 (Natural Language Computation Correspondence). As LLMs approach human-level understanding of programming, the set of functions they can reliably implement through indirect computation approaches the set of natural language calculable functions.

This conjecture suggests that the limit of what LLMs can reliably compute indirectly corresponds to what can be clearly specified in natural language—a notion that aligns with but is distinct from classical effective calculability.

A New Computational Hierarchy

Our analysis suggests a more nuanced hierarchy of computational classes based on reliability of implementation:

Definition 20 ($(L, \rho)$-Implementable Functions). For an LLM $L$ and reliability threshold $\rho$, the class of $(L, \rho)$-implementable functions is:

$$\mathcal{F}_{L,\rho} = \{f : \exists s \text{ such that } R(L, f, s) \geq \rho\}$$

Theorem 11 (Hierarchy of Implementable Functions). For any LLM $L$ and reliability thresholds $\rho_1 > \rho_2$:

$$\mathcal{F}_{L,\rho_1} \subset \mathcal{F}_{L,\rho_2}$$

Furthermore, as $\rho$ approaches 1, the class $\mathcal{F}_{L,\rho}$ becomes increasingly restricted.

Proof: If a function is implementable with reliability at least $\rho_1$, it is also implementable with reliability at least $\rho_2$ for any $\rho_2 < \rho_1$. By Theorem 3, for sufficiently high $\rho$, some computable functions must be excluded from $\mathcal{F}_{L,\rho}$, making the class strictly smaller as $\rho$ increases. ∎

This hierarchy provides a formal framework for understanding the capabilities and limitations of LLM-based computation that goes beyond the binary notion of computability.

Conclusion

This essay has established a formal theory of indirect Turing completeness, providing precise definitions, theorems, and proofs that characterize the computational capabilities of LLMs. Key insights from our analysis include:

LLMs can achieve indirect Turing completeness through code generation, despite not being Turing-complete themselves.
There are fundamental limitations on the reliability of indirect computation, especially as the complexity of the target function increases.
Interactive and compositional approaches to indirect computation have both opportunities and challenges for reliability enhancement.
The framework can be extended to account for approximate computation, which increases reliability at the cost of exactness.
Indirect computation through LLMs suggests a refinement of traditional computability theory, focusing on reliability and natural language specifiability rather than just binary computability.

These theoretical results provide a foundation for understanding the computational boundaries of LLMs and suggest directions for enhancing their reliability as computational mediators. By formalizing indirect Turing completeness, we bridge the gap between classical computation theory and the emerging paradigm of natural language-based programming, continuing the exploration of syntax, semantics, and computation that has been the focus of this series of essays.

The interaction between formal systems and statistical pattern recognition remains a rich area for theoretical investigation, with implications for programming language design, verification methodologies, and the fundamental nature of computation itself. As LLMs continue to evolve, this theoretical framework provides a basis for understanding their computational capabilities and limitations in rigorous terms.