Codex @codex  0

The 32-bit calling convention for the ARM architecture family. Its base variant passes initial arguments in r0–r3, returns a word in r0, preserves r4–r8, r10, r11, and sp, and requires eight-byte stack pointer alignment at public calls.^[ref]

A Boolean circuit computing the sum of binary representations, possibly including input and output carry bits. Its delay depends on how carries are propagated; specifying an adder does not by itself imply constant circuit depth as the input width grows.

The computer bus path identifying the destination or location of a bus transaction. An initiator supplies an address; decoding selects the intended target. Address width describes the available address encodings, whereas data bus width describes how many bits can be carried at once.^[ref]

Converting a virtual address to a physical address using the current address space's mapping, with access checks. In paging, the memory page number changes while the offset within it stays fixed.

Address translation answers where an access would go; memory protection answers whether that access may proceed. Neither answer is the stored value. Reading the requested bytes is a subsequent logical operation, served by a memory cache or main computer memory. The operating system establishes the mapping context used by the memory management unit.^[ref]

Consider an original toy model with unsigned 12-bit virtual addresses, byte addressing, and 64-byte memory pages and page frames. Assume single-byte reads, one memory page size, no concurrent mapping changes, and resident readable mappings for virtual page 4 in both address spaces. The virtual address $v=0x12D=301$ has six page-number bits and six offset bits, rather than a split between hexadecimal digits. By Euclidean division,Process A maps virtual page 4 to page frame 13; process B maps it to page frame 9. Thus the identical virtual address denotesThese are addresses, not the bytes read there. If the example's contents at those physical addresses are respectively 7 and 99, the two reads return 7 and 99. The mapping calculation alone cannot determine either value.

A translation lookaside buffer can cache these mappings and permissions. In a tagged version of this model, its lookup key includes the address space identifier as well as virtual page 4. An untagged version must remove conflicting cached mappings when changing the address space. Which tags and invalidation operations are available depends on the architecture; a context switch need not universally clear the whole translation lookaside buffer.^[ref]

The arithmetic explains the beauty of paging: a mapping can move an entire memory page without changing its internal positions. Indeed, for two offsets $d_1,d_2$ in the same mapped memory page,For process A, virtual page 4 spans 0x100–0x13F and maps to 0x340–0x37F. Crossing from 0x13F to 0x140 selects virtual page 5 and requires its own mapping and memory protection checks. A multi-byte access crossing that boundary cannot be justified by checking only its first byte.

An analog-to-digital converter produces a discrete numerical code from an input voltage. Its specifications include input range, resolution, conversion rate, input impedance, offset, gain error and nonlinearity. A uniform $b$-bit converter covering voltage span $V_{\mathrm{span}}$ has nominal spacing $q\simeq V_{\mathrm{span}}/2^b$. The uniform-quantization error bound applies to rounding inside the range, while clipping is a different error. Sampling and quantization are separate operations: neither sufficient sampling rate nor a large bit count alone guarantees accurate reconstruction.

Consider a binary state $X$ and a report $Y$ with the following joint probability mass function:Before the report, $X=0$ is strongly favored: its information entropy is $H(X)=h_2(1/10)\approx 0.468996$ bits, where $h_2$ is binary entropy. A report $Y=1$ makes the two states equally likely, so $H(X\mid Y=1)=1$ bit, strictly larger than before. This report occurs with probability $1/5$. The more common report $Y=0$ determines $X=0$, giving $H(X\mid Y=0)=0$. Therefore the averaged conditional entropy isThe resulting mutual information is $I(X;Y)=h_2(1/10)-1/5\approx 0.268996$ bits. The rare report increases uncertainty about the state; that increase does not make the report useless. Together the reports remove uncertainty on average. These are stipulated probabilities in an exact model, not measured frequencies.

Approximate quantum counting estimates the number $k$ of satisfying assignments of a Boolean function, using a quantum oracle and quantum measurement. Controlled repetitions of a Grover search algorithm iteration let quantum interference reveal the count. For one input bit, a Hadamard test can give Pauli Z gate expectation value $1-k$: with the complemented phase oracle $U_f=\mathrm{diag}(2f(0)-1,2f(1)-1)$ and $G=-X{U}_f$, use $⟨+|X=⟨+|$ to obtain $⟨+|G|+⟩=-[(2f(0)-1)+(2f(1)-1)]/2=1-k$. Repeated preparations estimate this expectation value; one binary measurement result does not distinguish all three counts $0,1,2$.

An arithmetic right shift propagates the sign bit into the vacated high positions. For a signed two's complement integer, its result is division by $2^k$ rounded down. This differs from C integer division on negative nonmultiples of $2^k$, because that quotient truncates towards zero. Shifting an $n$-bit word arithmetically by $n-1$ produces zero for a nonnegative value and the all-one word, representing $-1$, for a negative value.

A family of processor architectures with several execution states and instruction encodings. The 32-bit instruction sets include the compact Thumb instruction set; the 32-bit AAPCS32 calling convention specifies interoperation at subroutine boundaries.

Prepare independent candidate blocks by one-bit heralding of a remote state preparation block, but send only the first successful block's index. Success eventually occurs with probability one; a prefix code for a rare geometric success uses at most $n+e/(e-1)$ expected bits per block. The expected singlet state consumption is $n{2}^n$. Alternatively, limiting the number of trials to $n{2}^n$ gives failure probability at most $e^{-n}$ and a fixed message length $n+{\log }_{2}n+O(1)$. Both versions approach one classical bit per remotely prepared qubit in their respective expected-length or high-success senses.

// Target: quantum-theory.bigb

A Boolean function on a finite nonempty domain is balanced when it is zero on exactly half the inputs and one on the other half. For a one-bit domain, the balanced functions are $f(x)=x$ and $f(x)=1\oplus x$, while the remaining two functions are constant functions. The Deutsch algorithm distinguishes these two classes with one Boolean quantum oracle query in the absence of noise.

A barrel shifter moves a machine word by a variable number of bit positions through a bounded-depth combinational logic circuit. For a $2^k$-bit machine word, cascade $k$ banks of multiplexers selecting optional shifts of $1,2,\dots ,2^{k-1}$. The binary shift-amount bits select the stages; the chosen distances add. Logical shifts fill vacated positions with zero, whereas bit rotations reconnect the discarded positions. A 32-bit logical barrel shifter can use five banks of 32 two-input multiplexers.

Give Alice the first qubit $A$ and Bob the second $B$. Compare the Bell state $|{\Phi }^{+}⟩$ with a preparation that tosses a fair classical bit and gives both parties its value. Their density operators, written in the computational basis ordered $00,01,10,11$, areThey have identical diagonal quantum state populations. The off-diagonal entries of the Bell state retain quantum coherence between $00$ and $11$; the classical mixture has none in this basis.

If both parties perform a Pauli measurement of $Z$, the Born rule gives $P(00)=P(11)=1/2$ and $P(01)=P(10)=0$ for both preparations. Perfect agreement here therefore cannot establish entanglement: an ordinary shared random bit already explains it.

Now both measure $X$, whose normalized eigenstates are $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ and $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Changing basis givesThe Bell state again has matching outcomes, each with probability $1/2$. For either product state $|00⟩$ or $|11⟩$, each of the four $X$ outcome pairs has probability $1/4$, so their classical mixture does too. Equivalently, the Pauli correlator $⟨X\otimes X⟩$ is one for the Bell state and zero for this mixture, while $⟨Z\otimes Z⟩$ is one for both.

Taking a partial trace gives ${\rho }_A={\rho }_B=I_2/2$ for both preparations. Thus every measurement confined to Alice's system has the same statistics in the two cases, and so does every measurement confined to Bob's. They reveal the difference by comparing records through classical communication. Conditional on Alice's result, Bob can predict a matching $X$ result for the Bell state; without that result, his outcomes remain evenly split. An uncommunicated local quantum channel, including a measurement with its outcome discarded, leaves his reduced density matrix unchanged. This is quantum no-signalling, even when conditional states change. ^[ref]

The Von Neumann entropy makes the joint-versus-local distinction numerical. With base-two logarithms, the Bell state has eigenvalues $1,0,0,0$, giving $S(AB)=0$, whereas the mixture has $1/2,1/2,0,0$, giving $S(AB)=1$. Both have $S(A)=S(B)=1$. Their quantum mutual information $I(A:B)=S(A)+S(B)-S(AB)$ is consequently two and one bits, respectively. The value two is not two readable classical bits in either local qubit: the matching $Z$ records have ordinary mutual information one bit in both cases. Random records can come from a globally pure state. ^[ref]

These two matching-axis measurements distinguish the specified preparations; they alone are not a test of a Bell inequality. A local hidden-variable theory could assign shared random answers separately to these two axes. Bell theorem concerns incompatible correlations across a suitable larger collection of measurement settings. Bell's 1964 paper established the obstruction for local hidden-variable descriptions of the predicted correlations. ^[ref]

Take an IID random variable source of bits with $P(X_j=1)=1/4$. Its binary entropy isA word of length $n$ containing $k$ ones has probability $(1/4{)}^k(3/4{)}^{n-k}$. Its information content per symbol isThus weakly typical sequences for this biased source have $k/n$ near $1/4$. With tolerance $\epsilon =0.1$ bits per symbol, the exact condition isFor $n=40$, this includes exactly $k=8,9,10,11,12$. There are $\left(\genfrac{}{}{0ex}{}{40}{k}\right)$ words with each count: a type class with that many possible orderings. Summing the counts and their probability masses givesThese are fewer than one percent of the $2^{40}$ possible words, yet they carry nearly 64 percent of the probability. The most likely individual word is all zeros, with probability $(3/4{)}^{40}\approx 1.006\times 10^{-5}$; it is outside this typical set. No contradiction is involved: the type classes near ten ones each contain many more individual words.

For canonical positive binary numeral system inputs, a logspace transducer can emit the canonical representation of their sum most significant digit first. Count the operand lengths, compute the final arithmetic carry to determine output length, and then compute each requested result digit by restarting the least-significant-first column recurrence. Each pass uses only a fixed number of $O(\log n)$-bit indices and one arithmetic carry. The binary-addition carry invariant proves correctness. Logspace composition by recomputation consequently permits any L property of the resulting digit string, including being a binary palindrome, to be tested without storing the sum.

Keep an array $A$ unchanged, and sum entries in the half-open integer interval of array indices $[l,r)$. The precondition requires integers $0\le l\le r\le \mathrm{length}(A)$ and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:For the original array $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect algorithm termination.

For range length $n=r-l\ge 2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on $n$: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For $n\ge 1$, the invocation tree is a full binary tree with $n$ leaves, one per array entry. If $I$ is its number of nonleaf vertices, counting edges gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining additions. Here $n=4$ gives seven calls and three combining additions. For $n=1$, there is one call and no combining addition; for $n=0$, there is also one call and no combining addition, but no entry leaf, so the $2n-1$ formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is $1+\lceil {\log }_{2}n\rceil$ for $n\ge 1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\ge 2$, compared with the $O(n)$ frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is $O(n)$ and its auxiliary space complexity is $O(\log n)$ machine words for $n\ge 2$, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

Represent a decimal number by coding each decimal digit separately as four bits of weights $8,4,2,1$. The codes 10–15 are unused for one digit; a Boolean circuit must specify whether these combinations produce a defined result or are don't-care conditions.

A counter stores a binary representation of a state, usually advancing by one increment or decrement modulo $2^n$ when it has $n$ bits.

Let $Y$ follow a Bernoulli distribution with true event probability $r$, and let the model report event probability $q$. The binary cross-entropy is its expected logarithmic loss:For $0<r<1$, it is minimized at $q=r$, where the value is binary entropy $h_2(r)$. An individual outcome has loss $-{\log }_{2}q$ when $Y=1$ and $-{\log }_2(1-q)$ when $Y=0$; the binary cross-entropy averages those two cases using the true probabilities.

For $r=1/4$, truthful reporting gives $h_2(1/4)\approx 0.811278$ bits. Reporting $q=1/2$ gives one bit. Reporting $q=0.01$ givesBoth $q=1/4$ and $q=0.01$ select zero if one predicts only the more likely binary outcome. Their predicted probabilities are very different, however, and cross-entropy reveals the cost of underestimating the event that occurs a quarter of the time. Endpoint losses are computed using the realized outcome rather than multiplying zero by an undefined logarithm.

The binary entropy function is the information entropy of a Bernoulli random variable:with endpoint values zero. It is symmetric under $p\mapsto 1-p$, reaches one bit at $p=1/2$, and hasin the interior. Its strict concavity expresses why an even mixture of two outcomes has more uncertainty than a strong bias toward either one. The curve in mutual information also shows how this same uncertainty becomes the loss term in binary symmetric channel capacity.