Introduction

Large language models (LLMs) have transformed much of the field of natural language processing (NLP) (Radford et al., n.d.; Vaswani et al. 2017; Devlin et al. 2019; Raffel et al. 2023), the study of human languages. Its success, in some sense, is a little surprising: humans essentially have made for themselves a general “reasoning” algorithm (albeit a pretty bad one as of right now) using entirely inexact Bayesian modeling approaches. Exactly since LLMs developed from literature in the Bayesian modeling community, “formal” questions about what an LLM can or cannot do—the complexity-theoretic elements of LLMs as models—are comparatively understudied. Even now, we have very little idea of what an LLM is even learning, let alone trying to understand how to steer them or bound their behavior (Wu et al. 2025)—which, for a purported thinking machine, is a thing we probably want.

Bits is a universal currency to transmit information. As long as we can encode

Source-Channel Separation Theorem

“Are we loosing information by using Bits? No.”

Statement:

If a source can be transmitted over a channel at a certain resolution, then it can be transmitted using a binary interface between the source and channel at the same resolution.

Meaning:

If a communication channel has a certain fidelity for arbitrary data, encoding the data by bits will not change the fidelity of the channel.

\begin{align} 0v &= (0+0)v \\ &= 0v+0v \end{align}

Given scalar multiplication is closed, \(0v \in V\), which means \(\exists -0v:0v+(-0v)=0\). Applying that to both sides:

\begin{equation} 0 = 0v\ \blacksquare \end{equation}

The opposite proof of \(\lambda 0=0\) but vectors work the same exact way.

eigenvalue is the scalar needed to scale the basis element of a one dimensional invariant subspace of a Linear Map to represent the behavior of the map:

\begin{equation} Tv = \lambda v \end{equation}

Note we require \(v \neq 0\) because otherwise all scalars count.

eigenvector is a vector that forms the basis list of length 1 of that 1-D invariant subspace under \(T\).

“operators own eigenvalues, eigenvalues own eigenvectors”

Why is eigenvalue consistent per eigenvector? Because a linear map has to act on the same way to something’s basis as it does to the whole space.

• New Deal