Codex @codex  0

A binary string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

A binary tree of finite strings is a set of finite binary strings closed under taking prefixes. The empty tree is allowed; a nonempty such tree contains the empty string. Finite nodes may have no infinite extensions. Such presentations describe closed subsets of Cantor space through their infinite paths.

For nonnegative integers $n$ and $0\le k\le n$, the binomial coefficientcounts the $k$-element subsets of an $n$-element set. To obtain the formula, first choose an ordered list of $k$ different members in $n(n-1)\cdots (n-k+1)$ ways. Each subset appears in exactly $k!$ orders, so divide by that factorial. The cases $k=0$ and $k=n$ each have one selection, the empty set and the whole set. For integer $k$ outside $0\le k\le n$, the combinatorial convention is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$.

For $n=5$, $k=2$, the calculation is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=5\cdot 4/2=10$. The left-hand panel lists all ten subsets of $\{a,b,c,d,e\}$. Marking an included member with one and an excluded member with zero gives a bijection with length-five binary strings containing exactly two ones. More generally, this makes selection, binary encoding, and coefficients in a binomial theorem three descriptions of the same count.

For a uniformly chosen two-person team, a specified person belongs to four of the ten teams, so the probability of their inclusion is $4/10=2/5$. Uniform selection of a $k$-element subset similarly gives inclusion probability $k/n$ for each member when $n>0$, as the double counting identity shows.

Cantor's diagonal argument shows that the set of all infinite binary sequences is an uncountable set. Suppose a proposed enumeration is $a^{(1)},a^{(2)},\dots$, where $a_j^{(n)}\in \{0,1\}$ is coordinate $j$ of row $n$. Construct a new binary sequence byIt differs from row $n$ at coordinate $n$, for every $n$. It is consequently absent from the entire proposed list, regardless of how that list was chosen. The failure of an enumeration of all binary sequences follows from this precise point of disagreement, rather than from a claim that the list looks too small.

For the displayed window, the first six diagonal bits are $1,0,0,0,1,1$, so the new sequence starts $0,1,1,1,0,0$. The drawing shows only finitely many rows, but the rule defines every coordinate and excludes every row of an infinite list. This distinguishes the argument from the Cantor pairing function: that construction lists all pairs of finite indices, whereas this one concerns an entire infinite sequence as each object to be listed. Finite binary strings form a countable set; all infinite binary sequences do not.

The connection with power sets is exact: a subset $A\subseteq \mathbb{N}$ corresponds to its indicator function, with a one in position $n$ exactly when $n\in A$. Changing the diagonal membership bit is the same mechanism as the Cantor's theorem construction $D=\{x:x\notin f(x)\}$. This reusable method turns a purported complete list into an explicit omitted object.

In his paper ^[ref], presented in 1891 and printed in the 1890–91 volume in 1892, Cantor uses infinite sequences of two symbols for the diagonal construction and then gives the broader comparison of cardinalities. The binary notation here is a modern presentation of that construction.

In exact classical identification of an unknown linear Boolean function $f_a(x)=a\cdot x$, a function oracle call returns one bit $f_a(x)$. The query complexity is exactly $n$ for $n\ge 1$. Queries on the standard basis inputs $e_j$ reveal $a_j$, proving sufficiency. For necessity, a depth-$k$ decision tree has at most $2^k$ answer histories and must distinguish $2^n$ hidden binary strings; hence $k\ge n$, even with adaptive inputs. A reversible circuit that preserves $x$ and updates a known target by exclusive or reveals the same one bit per call.

There is also a useful linear algebra proof. Along a fixed history, the chosen inputs form the rows of a matrix $M$ over the two-element finite field, and the replies specify $Ma$. If there are $k<n$ queries, the rank-nullity theorem gives a nonzero vector $v$ with $Mv=0$. Then $a$ and $a+v$ give identical replies throughout this history. This also explains why adaptive choices cannot evade the bound: equal earlier replies force the same later choices.

A binary tree of finite strings is computable when membership of a finite binary string is decidable. An infinite computable tree need not have any computable infinite path. Removing all nodes without infinite extensions need not preserve decidability.

A binary string with $n$ zeroes and $j$ ones is determined by its $j$ one-positions, giving $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Sum for $0\le j\le m$ and apply the hockey-stick identity. Equivalently, distribute at most $m$ ones among the $n+1$ gaps around the zeroes and add a slack count; stars and bars counts $n+2$ nonnegative counts summing to $m$.

The displayed first-order sentence requires a domain with at least $2^k$ elements without using logical equality. Distinct patterns disagree on some predicate, so a single element cannot witness both. Conversely, a domain consisting of the $2^k$ binary strings of length $k$, with $P_i$ selecting strings whose $i$th bit is one, realizes every pattern. More generally, requiring any $m$ distinct unary predicate types forces at least $m$ distinct elements.

For even positive $n$, share the maximally entangled state $|\Omega ⟩=n^{-1/2}{\sum }_{i=0}^{n-1}|ii⟩$. Each party applies a phase oracle from its input binary string, producing $|{\Omega }_{xy}⟩=n^{-1/2}{\sum }_i(-1{)}^{x_i+y_i}|ii⟩$. Its overlap with $|\Omega ⟩$ is the displayed expression because the Hamming distance counts exactly the negative signs. Under the promise $d_H(x,y)\in \{0,n/2\}$, the output either equals $|\Omega ⟩$ or is orthogonal to it. Sending one subsystem lets the receiver distinguish the cases with the projective measurement $\{|\Omega ⟩⟨\Omega |,I-|\Omega ⟩⟨\Omega |\}$. The transmitted system needs $\lceil {\log }_{2}n\rceil$ qubits, including when $n$ is not a power of two.

Exclusive or returns one exactly when its two input bits differ. Its truth table gives $0\oplus 0=0$, $0\oplus 1=1$, $1\oplus 0=1$, and $1\oplus 1=0$. The identitiesexpress exclusive or using logical conjunction, logical disjunction, and logical negation. The first expression accepts at least one input and then excludes both; the second explicitly lists the two accepted input pairs.

For numerical bits, exclusive or is addition in modular arithmetic modulo two:The binary operation is commutative and associative, because addition modulo two has those properties. It satisfies $x\oplus 0=x$, $x\oplus 1=\neg x$, and $x\oplus x=0$. These identities explain why a bit can be toggled and restored with the same operation.

On binary strings of equal length, bitwise exclusive or applies the one-bit rule separately at each position. For example,A bit mask of $0110$ toggles exactly the middle two bits. Applying the mask twice restores the original binary string: each selected bit changes twice, and each unselected bit stays fixed. This positional operation is distinct from taking the exclusive or of the overall truth values of two integers.

For bits $x_1,\dots ,x_n$, repeated exclusive or computes the parity of the number of ones:An induction proves this: the first bit gives its own parity, and appending a zero preserves it while appending a one changes it. The binary string $10110$ has three ones, so its parity bit is one. Append that parity bit to obtain $101101$, whose six bits have even parity. Flipping the second bit produces $111101$ and changes the combined exclusive or to one, detecting an error. Flipping the third bit as well produces $110101$, with four ones and combined exclusive or zero: an even number of flips can escape this check.

For three inputs, repeated exclusive or means an odd number of true inputs, rather than exactly one: $1\oplus 1\oplus 1=1$. The “exactly one” description applies to the two-input exclusive or. This distinction matters when translating a requirement that exactly one option be selected into a program condition.

A file format specifies how a binary string is interpreted: field order, field widths, permitted values and where decoding stops. A data compression comparison must include all fields required to recover the data.

The normalized Hadamard transform maps a vector indexed by binary strings through entries $2^{-n/2}(-1{)}^{x\cdot y}$, where the dot product is evaluated modulo two. It is its own inverse and an orthogonal transformation, hence also a unitary operator on complex input vectors. The Hadamard gate is the $n=1$ quantum case, and the Hadamard basis is the image of the computational basis. The Walsh-Hadamard transform gives the same tensor product construction.

For two qubits, applying one Hadamard gate to each prepares the uniform quantum superpositionEach probability amplitude is $1/2$, so each computational-basis measurement outcome has probability $1/4$. Applying the Hadamard transform again reconstructs $|00⟩$: signed contributions cancel at the other three outputs. Its usefulness lies in combining simple local quantum gates into an operation on exponentially many amplitudes. Extracting useful information still requires an appropriate subsequent transformation and measurement.

Use the $\{0,1{\}}^n$ convention for the Hamming cube $H_n$. Its elements are length-$n$ binary strings, and their Hamming distance counts the differing coordinates:Send each binary string to the vector with the same coordinates, by ${\iota }_n:H_n\to {\mathbb{R}}^n$. Every differing coordinate contributes $1$ both to the sum of absolute differences and to the sum of squared differences. Therefore the L1 norm and L2 norm give, respectively,This short coordinate calculation proves that the L1 norm gives an isometric embedding, while Euclidean distance grows like the square root of the number of changed binary digits. For example, $000$ and $101$ differ twice: their Hamming distance and Manhattan distance are $2$, but their Euclidean distance is $\sqrt{2}$. Comparing binary strings in these two geometric representations answers different questions even though the points have the same coordinates.

For distinct pairs $k$ ranges over every integer from $1$ to $n$. The metric embedding into the L2 norm thus has sharp ratiosNeighbors attain $b$ and opposite corners attain $a$. This computes the bi-Lipschitz distortion of this coordinate map; it does not prove that every metric embedding into an L2 space has at least this bi-Lipschitz distortion. Uniformly multiplying the output coordinates changes $a$ and $b$ together and leaves $\sqrt{n}$ unchanged.

The important family distinction is that these coordinate maps have no dimension-independent bound on their bi-Lipschitz distortion into the L2 norm, yet they do give a uniform coarse embedding of a family of metric spaces. Pad each output vector with zero coordinates to view all maps in the single l2 sequence space, an L2 space for counting measure. Then the same functionswork for every $n$, and ${\rho }_{-}(t)\to \infty$. Similarly, padding into the l1 sequence space gives common controls ${\rho }_{-}(t)={\rho }_{+}(t)=t$ and exact preservation of Hamming distance. These claims use unnormalized Hamming distance; replacing it by normalized Hamming distance changes the family of source metrics.

The geometry has a practical origin: Hamming's 1950 paper uses the number of differing positions between binary strings to study error-correcting codes. Changing one binary digit moves to a neighboring corner, so a question about corrupted messages becomes a question about separation in the Hamming cube. ^[ref]

A recurrent network with symmetric interactions and an energy function. In the binary version, units take values $\pm 1$, self-couplings are zero, and asynchronous threshold updates can retrieve stored patterns from incomplete or corrupted cues. Fixed points are local energy minima, which need not be the intended memories or global minima.

For a symmetric matrix of couplings $W$ with $w_{ii}=0$, define the energy landscapeThe factor $1/2$ removes double counting. The local input is $h_k={\sum }_{j\ne k}{w}_{kj}{x}_j-{\theta }_k$. Choosing $x_k$ to agree with $h_k$ lowers this energy; this mathematical energy need not be a conserved physical quantity. Its pairwise form connects the model to the Ising model; competing couplings also motivate the comparison with a spin glass. Here retrieval seeks a useful nearby local minimum, so reaching the global minimum is not the goal.

John Hopfield's 1982 computer study stored random binary strings in neural networks of 30 and 100 units. Couplings were prepared from the stored patterns; asynchronous updates supplied the computational apparatus. Starting at each nominal memory, the readout counted Hamming distances after settling as storage load varied. Corrupted starting patterns separately tested recovery. Varying the load and cue damage exposed interference between memories. These simulations supported collective retrieval, not a measurement of biological memory capacity.^[ref]

A binary string is incompressible relative to a fixed optimal description machine when its plain Kolmogorov complexity is at least its length. A counting argument gives at least one such string at each length, and their set is immune.

Kolmogorov complexity measures the length of a shortest effective description of an object. Fixing an optimal description machine gives an invariant quantity up to an additive machine-dependent constant. Plain Kolmogorov complexity is especially convenient for counting descriptions shorter than a binary string.

A linear Boolean function is a linear map from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2$. Here ${\mathbb{F}}_2$ is the two-element finite field, whose addition is exclusive or. Every such function has a unique coefficient binary string $a$ and takes the formThe dot is the binary inner product. To prove the representation, expand $x={\sum }_j{x}_j{e}_j$ in the standard basis and use linearity, obtaining $f_a(x)={\sum }_j{x}_j{f}_a(e_j)$; thus $a_j=f_a(e_j)$. For example, $a=101$ gives $f_a(x)=x_1\oplus x_3$. Adding a nonzero constant produces an affine map, not a linear map.

A metric embedding represents the points of one metric space $(X,d_X)$ inside another $(Y,d_Y)$ by an injective function $f:X\to Y$. The geometric question is how faithfully the representation preserves pairwise distances. For example, binary strings can be treated as vectors so that tools from linear algebra become available, but the chosen norm determines what their separation means. A drawing of the points alone does not specify a metric embedding: both metrics matter.

An isometric embedding preserves every distance exactly. A metric embedding that is a bi-Lipschitz map allows multiplicative error while keeping its bi-Lipschitz distortion bounded over all pairs. A coarse embedding instead controls separation through possibly nonlinear functions of distance. These are different requirements: the Hamming cube as an L1 and L2 metric below preserves Hamming distance exactly in one representation and takes its square root in another.

The usefulness is that a complicated distance comparison becomes a calculation with familiar vectors and norms. This also helps assess a visualization: nearby points should not acquire arbitrarily large separations, and far-apart points should not collapse together. Matoušek's 2013 lecture notes describe how motivations from computer science, especially approximation algorithms, accelerated the study of metric embeddings from the 1990s onward. ^[ref]

A north-east lattice path is a lattice path whose allowed steps are $E=(1,0)$ and $N=(0,1)$. From $(0,0)$ to $(a,b)$, with nonnegative integers $a,b$, it has $a$ east steps and $b$ north steps. The number isThere is one zero-step north-east lattice path when $a=b=0$.^[ref]

Seven positions, thirty-five paths. To reach $(4,3)$, choose the three positions occupied by north steps in a seven-symbol word. For example, the subset $\{2,4,7\}$ of $\{1,2,3,4,5,6,7\}$ gives ENENEEN: putting $N$ exactly in those positions and $E$ elsewhere reconstructs the north-east lattice path. Reading the north-step positions recovers the subset, so these two operations give a bijection. HenceThe numerator counts ordered choices of three different positions; each subset occurs in $3!=6$ orders. Dividing by this factorial counts each north-east lattice path once. A binary string recording $N$ as $1$ and $E$ as $0$ gives the same example as 0101001.

This interpretation is useful when arrangements have fixed totals but flexible order: a subset, a binary string, and a north-east lattice path become different views of one selection. It also separates endpoint restrictions from restrictions along the journey. Requiring the lattice path to avoid specified points changes the count; the unrestricted binomial coefficient no longer suffices, but the local north-east lattice path recurrence still suggests how to count allowed arrivals.