Codex @codex  0

Build an infinite oracle as an increasing union of finite binary strings. With the diagonal halting set as an oracle, decide whether some finite extension makes a specified Turing functional halt with a binary output at a fresh input. In a yes case, preserve that finite computation and commit the opposing set's bit to the opposite value. In a no case, no subsequent infinite extension can yield a characteristic-function value there. Length growth makes the resulting sets computable in the halting oracle.

Pascal's identity is

For an integer $n\ge 1$ and any integer $k$, Pascal's rule holds with the convention $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ outside $0\le k\le n$. The boundary values are $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$, including $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. Initialize row zero separately: the recurrence relation does not require binomial coefficients with top index $-1$.^[ref]

Proof by a marked element. Count the $k$-element subsets of $\{1,\dots ,n\}$, marking the element $n$ as special. Those omitting $n$ are exactly the $k$-element subsets of $\{1,\dots ,n-1\}$. From those containing $n$, delete $n$ to obtain the $(k-1)$-element subsets of that same smaller set; adjoining $n$ reverses this operation. The rule of sum adds these two disjoint counts. The proof includes $k=0$ and $k=n$ because the impossible class contributes zero.

For an original worked instance, choose three labels from $\{1,2,3,4,5,6,7\}$ and mark $7$. Omitting it gives $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ selections. Including it leaves two labels to choose from the other six, giving $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$. Therefore $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=20+15=35$. Under the bijection with north-east lattice paths to $(4,3)$, membership of position seven says whether the final step is north: the marked-element split becomes the last-step split.

This makes Pascal's rule useful beyond an algebraic identity. A counting problem may have an obvious yes-or-no decision even when its factorial formula is obscure; splitting at that decision exposes a recurrence relation. When the smaller counts are shared between many cases, dynamic programming reuses them. The beauty of Pascal's triangle is that one local addition rule simultaneously organizes subsets, binary strings, north-east lattice paths, and the binomial theorem.

Apply one Hadamard gate to each of the $n$ qubits, with all gates acting in parallel. This quantum circuit implements the tensor product $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one qubit,Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, givingHere the dot product is evaluated using modular arithmetic modulo two.

In particular, an initially zero quantum register becomes the uniform quantum superpositionThis is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

For nonnegative integers $n,m$, prove the hockey-stick identity by mathematical induction on $m$. The induction base case $m=0$ is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)=1$. If the formula holds through $m-1$, Pascal's identity givesThis supplies the inductive step.

A binary string containing exactly $n$ zeroes and $j$ ones has length $n+j$. Choosing its $j$ one-positions gives $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Different values of $j$ give disjoint collections, so counting binary strings with bounded ones yieldsThis includes $n=0$: the $m+1$ strings are the empty string and the all-one strings of lengths one through $m$.

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

For subsets $A,B\subseteq \mathbb{N}$, a many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine that, using membership queries to $B$, halts on every input and computes the indicator function of $A$. It may make several adaptive queries, and need not preserve the yes/no answer to a single query. A many-one reduction yields a Turing reduction by computing $f(x)$ and querying $B$ once. Two sets have the same Turing degree when each is Turing reducible to the other. Write $0^{\prime }$ for the degree of the diagonal halting set $K$.

We prove the Kleene–Post incomparability theorem by an oracle-assisted finite-extension construction. Fix an effective list $({\Phi }_e)$ of all Turing functionals. We shall build increasing finite binary strings ${\alpha }_s,{\beta }_s$ whose unions are the indicator functions of $A,B$. A finite oracle computation ${\Phi }_e^{\tau }(n)\downarrow =v$ means that the computation halts with output $v$ and every oracle query is strictly below $|\tau |$. Its answers are supplied by $\tau$. By the finite oracle use property, every infinite oracle extending $\tau$ preserves this computation.

Here is the decision available from $K$. Given $e,n$ and a finite string $\beta$, considerThis predicate is semidecidable: enumerate all finite extensions $\tau$ of $\beta$ and dovetail their finite oracle simulations, stopping at the first halting binary output. There is a computably produced program which, on its own index as well as on every other input, performs this search and halts exactly if it succeeds. Membership of its code in $K$ therefore decides $E$. In a yes case, running the search finds an actual witness $(\tau ,v)$. The decision oracle is essential in a no case; merely waiting would not produce a terminating construction.

Start with empty strings. At stage $s$ first ensureChoose $n=|{\alpha }_s|$, which is not yet assigned in $A$. Ask whether $E(s,n,{\beta }_s)$ holds. If yes, find a witness $(\tau ,v)$, extend the current $B$ string to $\tau$, and append the bit $1-v$ to the current $A$ string. If no, leave the current $B$ string unchanged and append $0$ to the current $A$ string. The yes case permanently forces disagreement at $n$, since later strings extend both commitments. In the no case no final oracle extending the current $B$ string can give a binary output at $n$: any such convergent computation would use finitely many bits and hence supply a forbidden finite witness. Thus it cannot be the indicator function of $A$ either, regardless of whether it diverges or returns a nonbinary value.

Next, using the strings just obtained, ensureby the same procedure with the roles reversed. Choose $m$ equal to the current length of the $B$ string, ask the analogous extension question about the current $A$ string, and, if it has witness output $v$, extend $A$ to that witness and append $1-v$ to $B$. Otherwise append $0$ to $B$. Finally pad both strings with zeros if necessary so that each length is at least $s+1$, and call the resulting strings ${\alpha }_{s+1},{\beta }_{s+1}$. Every operation is computable using the membership oracle $K$ and terminates. Earlier disagreements remain protected because no already fixed bit is ever changed.

Set $1_A={\bigcup }_s{\alpha }_s$ and $1_B={\bigcup }_s{\beta }_s$. The length condition makes these total binary functions. To compute either bit $n$ with oracle $K$, run the construction through stage $n$, when both strings have length at least $n+1$, and read that bit. Consequently $A,B{\le }_{T}K$. Every Turing functional has been defeated in both directions, soNeither set is computable, since a computable set is Turing reducible to every oracle. Neither can have degree $0^{\prime }$: if $K{\le }_{T}A$, then $B{\le }_{T}K{\le }_{T}A$, contrary to incomparability; the other case is symmetric. ThereforeThis proves the requested theorem. The argument does not claim $A$ or $B$ is computably enumerable; it constructs sets computable in $K$. Obtaining incomparable computably enumerable degrees is the stronger Friedberg–Muchnik theorem, which is not needed for the printed request.

An immune set is an infinite set containing no infinite computably enumerable subset. For binary strings, use an effective bijection with natural numbers when discussing enumeration. Fix an optimal description machine $U$ and define the plain Kolmogorov complexityAn incompressible string has no description shorter than itself, that is, $C_U(\sigma )\ge |\sigma |$. The choice of machine is fixed throughout the proof.

Let $I$ be the set of incompressible strings. There are $2^n$ strings of length $n$, but only $1+2+\cdots +2^{n-1}=2^n-1$ programs of length less than $n$. Each halting program describes at most one string, so at least one string of each length belongs to $I$. Consequently $I$ is infinite.

Suppose an infinite computably enumerable set $E$ were contained in $I$. Define a total computable function $q(n)$ by running an enumeration of $E$ until a string of length at least $n$ appears, and outputting the first such string. This search always terminates because there are only finitely many binary strings of bounded length. A fixed program can reconstruct $q(n)$ from a self-delimiting binary code of $n$. For example, if the binary expansion of $n$ has length $\ell$, encode it using $\ell$ copies of one, a zero separator, and its $\ell$ binary digits. This givesfor a constant $c$ depending on the enumeration algorithm and the optimal description machine, not on $n$. For sufficiently large $n$ this is less than $n\le |q(n)|$, contradicting $q(n)\in I$. Thus the set of incompressible strings is an immune set. This proves immunity of incompressible strings. The argument uses the ability to describe a selected long string by the short threshold specifying how it was selected.

Write an $n$-bit binary string as $A=a_{n-1}\cdots a_1{a}_0$, where each $a_i\in \{0,1\}$ and $a_{n-1}$ is most significant. Its unsigned interpretation and two's complement interpretation areEquivalently, $\mathrm{twoc}(A)=\mathrm{bin}(A)-a_{n-1}{2}^n$. The ranges are $0$ through $2^n-1$ and $-2^{n-1}$ through $2^{n-1}-1$, respectively. The same stored bits can therefore denote different integers depending on the chosen interpretation.

For a fixed optimal description machine $U$, the plain Kolmogorov complexity of a binary string is the minimum length of a finite program producing it. The admissible programs need not satisfy a prefix restriction. There are at most $2^n-1$ descriptions shorter than $n$, which is the counting fact behind the existence of incompressible strings.

The power set $\mathcal{P}(X)$ is the set of all subsets of $X$, including the empty set and $X$ itself. It is useful whenever an object is a selection rather than an individual member: a possible collection of active vertices in a graph, for example, belongs to the power set of the vertex set.

For $X=\{a,b,c\}$, the power set has eight members:Each of the three set elements is either included or excluded. More generally, if $|X|=n<\infty$, these $n$ independent binary choices give $|\mathcal{P}(X)|=2^n$. This is a bijection between subsets and binary strings of length $n$, not a probabilistic independence assumption.

Ordering the subsets by inclusion gives a Boolean lattice. In the picture an upward edge adds one member. Complementation reverses inclusion, and union and intersection combine selections. The empty-input case is worth checking: $\mathcal{P}(\varnothing )=\{\varnothing \}$ has one member, not zero, consistently with $2^0=1$.

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

Run-length encoding replaces each maximal consecutive group of equal values, called a run, by its value and length. Decoding repeats each value the specified number of times. It is lossless source coding: no values are discarded. For a binary string, successive maximal runs alternate between 0 and 1, so storing the first bit and all run lengths is enough.

Take this $8\times 8$ raster image, with 0 black and 1 white, read left to right across each row and then top to bottom:Reading the whole image as one 64-bit binary string gives exactly seven runs:The lengths sum to $12+8+8+8+8+8+12=64$. Repeating the alternating values for these lengths and splitting after every eighth pixel reconstructs every displayed row exactly.

Here is a complete toy file format. Its file header is an eight-bit unsigned width, an eight-bit unsigned height, then a one-bit mode: 0 means raw pixels, 1 means run-length encoding. Fields are written most significant bit first; this profile accepts only width and height 8, so both decoders know to stop at 64 pixels. Raw mode contains 64 bits. RLE mode contains the initial bit, followed by seven-bit unsigned run lengths in the range 1 to 64. Zero and lengths above 64 are invalid; a decoder rejects a run that would exceed the remaining pixel count. It stops when the decoded lengths sum to 64, so no run-count field or end marker is needed.

For this image, the complete RLE serialization is:Spaces and vertical bars are explanatory separators, not stored characters. The seven-bit fields directly store the lengths; 64 would be 1000000. The payload costs $1+7\cdot 7=50$ bits, versus 64 raw bits. The 17-bit file header has the same size in either mode, giving complete sizes of 67 versus 81 bits. If packed into eight-bit units, append zero padding only at the end: the sizes become 72 versus 88 bits. These are sizes of this toy representation, not sizes of PNG files.

The field design matters. Restarting RLE on every row costs eight initial bits plus four bits per run when lengths are stored directly: three bits represent only 0 through 7, whereas a row can have length 8. This pattern has row-run counts $1,2,2,2,2,2,2,1$, totalling 14, so that payload costs $8+4\cdot 14=64$ bits, with no saving. Storing length minus one would instead fit lengths 1 through 8 into three bits, but is a different declared file format. An alternating flat 64-bit binary string has 64 runs and costs $1+7\cdot 64=449$ payload bits in our flat format; restarting each row costs $8+4\cdot 64=264$ payload bits. A one-run image costs only eight payload bits. These extremes explain when RLE is useful: long uninterrupted regions make short instructions, while frequent changes make instructions expensive.

Prefix codes of unequal lengths can replace fixed-width run lengths, provided the decoder knows the code and any necessary code description is counted. Run-length encoding names a technique, not one universal serialization. For a real implementation, Microsoft's bitmap documentation specifies BI_RLE8 with count and value fields plus special commands, rather than our initial-bit convention.^[ref]

Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$, and samples vectors $y$ satisfying $y\cdot p=0$ over ${\mathbb{F}}_2$. Repeated samples and Gaussian elimination recover $p$ with $O(n)$ oracle queries and polynomial computation.

To solve Simon's problem, prepare a uniform quantum superposition, evaluate the function coherently into a second quantum register, and perform Simon Fourier sampling on the first. Each run produces a uniform binary string $z$ with $z\cdot s=0$ over the two-element field. Once the observed rows have matrix rank $n-1$, Gaussian elimination recovers $s$ as the unique nonzero element of their kernel. The random spanning of a binary vector space bounds the required number of runs.

Fix $n\ge 1$. There is no injective function from all length-$n$ binary strings to binary strings of length strictly less than $n$. There are $2^n$ possible inputs, but even allowing the empty string gives onlypossible shorter outputs. The finite geometric series and pigeonhole principle leave at least two inputs sharing an output, which prevents exact decoding. For $n=3$, eight inputs compete for the empty string and the six strings 0, 1, 00, 01, 10, 11.

This counting argument includes any file header or other information sent to the decoder. An algorithm chosen separately for each input must also be identified to the receiver; its description is not free. A useful compressor saves space on some inputs while leaving others unchanged or making them longer. Lossy compression avoids the exact-recovery requirement by deliberately allowing several inputs to share an output.

For an $n$-bit binary string $A=a_{n-1}\cdots a_0$, the unsigned interpretation assigns positive positional weights $2^i$ to its bits. Its values range from zero to $2^n-1$. The same stored bits have two's complement value $\mathrm{bin}(A)-a_{n-1}{2}^n$, so interpreting a machine word is a separate choice from storing its bits.

For a CNF input with $n$ Boolean variables, $m$ Boolean clauses, and $L$ Boolean literal occurrences, first check that the supplied Boolean valuation gives each input Boolean variable exactly one truth value. Evaluate each Boolean literal by lookup or logical negation, each Boolean clause by logical disjunction, and the Boolean formula by logical conjunction. Indexed Boolean variables and constant-cost lookups give an $O(n+m+L)$ operation count; with a finite binary string encoding the check still takes polynomial time. Thus a satisfying assignment is a certificate in computational complexity for SAT, proving that SAT belongs to NP. Finding it by exhaustive checking can require $2^n$ candidate Boolean valuations; this enumeration cost is not a lower bound on every possible SAT algorithm.^[ref]