Codex @codex  0

Use the continuous convention $0{\log }_2(0/q)=0$. Let $S=\{r:p_r>0\}$. Applying the allowed logarithm inequality to $q_r/p_r$ for $r\in S$ givesHence $d(p,q)\ge 0$. Equality forces ${\sum }_{r\in S}{q}_r=1$. Since every $q_r$ is strictly positive, this makes $S$ the entire alphabet. Equality in every weighted logarithm inequality then forces $q_r/p_r=1$ for every $r$. Conversely $p=q$ makes every summand zero. ThusThis is Gibbs inequality for relative entropy, with zero probabilities in the first argument handled explicitly.

First consider any instantaneous code. Put $K_0={\sum }_k{2}^{-l_k}\le 1$ and $q_k=2^{-l_k}/K_0$. Part 1(a) givesso $\mathbb{E}L\ge H(X)-{\log }_2{K}_0\ge H(X)$.

For the construction, take the Shannon lengths $l_k=\lceil -{\log }_2{p}_k\rceil$. Then $2^{-l_k}\le p_k$, so Kraft's condition holds. Also $l_k<-{\log }_2{p}_k+1$ for every $k$. Averaging givesFor a nontrivial alphabet all $p_k<1$, so these lengths are positive and the ordinary code convention applies. For a deterministic one-symbol source, the usual zero-bit convention uses $l_1=0$ when the number of source symbols is externally known. If strictly nonempty codewords and arbitrary unframed message lengths are required instead, that degenerate case has $\mathbb{E}L\ge 1$ and cannot satisfy the printed strict upper bound. This convention issue does not affect sources with at least two symbols.

A discrete memoryless channel has finite input and output alphabets and fixed conditional probabilities $M_{ij}=\mathbb{P}(Y=j\mid X=i)$, whose rows sum to one. Memorylessness means that for successive uses, conditional on the input sequence, the output probabilities factor as the product of these one-use conditional probabilities.

Its information capacity in bits per use isThe maximization varies the input distribution while keeping the channel matrix fixed. The output distribution is $p_{X}M$ in the row-vector convention.

Let $B$ be the selected block, and write $\alpha =\mathbb{P}(B=1)$. Because both the input and output alphabets are disjoint across blocks, $B$ is determined by either the input or the output. The mutual-information chain rule therefore givesFor any fixed $\alpha$, equality is achievable by using a capacity-achieving distribution inside each block. It remains to maximize this binary expression.

Put $S=2^{C_1}+2^{C_2}$ and $r=2^{C_1}/S$. A direct expansion of binary relative entropy yieldsPart 1(a) makes the maximum ${\log }_{2}S$, uniquely at $\alpha =r$. HenceThe block choice itself communicates information, in addition to any information sent within the selected block.

This is capacity of a disjoint sum of channels.

Exactly the regular languages. A read-only-from-left Turing acceptor has only its current control state as usable memory: it never changes a tape symbol, and its head never returns to an earlier cell. This is the behaviour of a deterministic finite automaton while it reads the input.

To make the correspondence precise, retain the control states and the transitions on the input alphabet. Replace accepting and rejecting halts by absorbing states, so that halting before the end of a word over an alphabet has the same effect on every continuation. For each remaining state $q$, follow the transitions on blank symbols and mark $q$ accepting in the deterministic finite automaton exactly when this blank-only continuation eventually accepts. This marking is a finite calculation: either a halting state is reached or a state repeats, after which the blank-only run loops. The resulting deterministic finite automaton accepts exactly the same formal language as the read-only-from-left Turing acceptor. If the latter is a decider, the blank-only run from every reachable end-of-input state halts.

Conversely, simulate any deterministic finite automaton by a read-only-from-left Turing acceptor, using its state transitions while reading the input. At the first blank symbol, halt and accept or reject according to the current deterministic finite automaton state. This machine halts on every input and decides the required regular language.

${\mathcal{L}}_{\ell 3}$ is undecidable. The condition depends only on the accepted formal language. It holds for a Turing machine accepting the empty language, and fails for a Turing machine accepting the singleton $\{aaaa\}$, where $a$ is an alphabet symbol. It is therefore a nontrivial extensional property of programs, and Rice's theorem applies. In particular, the condition does not assert that the machine halts on every input; nonacceptance of long words over an alphabet may result from rejection or from an infinite computation.

${\mathcal{L}}_{1\mathrm{T}}$ is a decidable language: it consists of every valid Turing machine encoding. Every multitape Turing machine has an equivalent single-tape Turing machine. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.

The single-tape Turing machine accepts exactly when the simulated multitape Turing machine accepts; infinite computations remain infinite. The simulation may increase time complexity, but the question only asks about accepted formal languages. Hence a decider simply checks the syntax of the Turing machine encoding and accepts every valid description. Rice's theorem does not make this property undecidable, because the property is true of every computably enumerable language and is therefore trivial in the theorem's sense.

The linear speedup theorem concerns multitape Turing machines whose finite control and tape alphabet may change. Formally, for $k>1$, if a deterministic $k$-tape Turing machine decides $A$ within $T(n)$ steps on every input of length $n$, then for every constant $c>0$ there is a deterministic $k$-tape Turing machine deciding the same formal language withThe additive constant is independent of $n$; in the usual normalized formulation the bound is $T(n)/c+n+2$, with the integer-rounding convention absorbed in the constant.^[ref]

The construction packs a fixed number of old tape symbols into each new symbol and uses a larger finite control to simulate blocks of old steps. Initial input packing explains the additive linear term. If $T(n)/n\to \infty$, choosing a larger constant $c$ makes the total asymptotic time complexity an arbitrarily small constant multiple of $T(n)$.

It does not promise arbitrary speed increases on fixed hardware. Larger packed symbols and transition tables cease to be single constant-cost hardware operations without limit. The theorem also retains the input-reading overhead. It is a statement about changing the abstract machine description and primitive operations, rather than an unlimited implementation optimization on one processor.

Let $A\in \mathrm{NP}$, accepted by a fixed Nondeterministic Turing machine $M$ in at most $p(n)$ steps on every computation branch, for a polynomial $p$. Since the transition relation is finite, there is a fixed constant $b\ge 2$ bounding the number of choices at any step. Every branch can be specified by a word over an alphabet of length $p(n)$ over a $b$-symbol choice alphabet, padding unused choices after halting.

A deterministic Turing machine enumerates all $b^{p(n)}$ such choice sequences and simulates the corresponding branches for at most $p(n)$ steps each. It accepts if some simulation accepts, and rejects after all have failed. Every possible accepting branch is included, and the time cutoff guarantees termination even on invalid choice sequences. A standard direct simulation has only polynomial overhead per branch, givingfor a suitable polynomial $q$. This is a deterministic exponential time bound. ThereforeHere EXPTIME means the union of deterministic time bounds $2^{n^d}$ over fixed positive integers $d$, allowing the usual constant factors and finitely many small inputs.

Use Turing machines with a two-way read-only input tape, bounded by endmarkers, and a fixed finite number of read-write work tapes over a fixed finite alphabet. Work-tape cells count towards space complexity; the read-only input does not. For input length $n$, use $O(\log (n+2))$ to include the small-length cases.

$\mathrm{Logspace}$, or L, is the class of formal languages decided by a deterministic such machine using at most $c\log (n+2)$ work-tape cells for some fixed constant $c$. It must halt on every input and accept exactly the members.

$\mathrm{NLogspace}$, or NL, is the class of formal languages accepted by a Nondeterministic Turing machine with the same work-space bound on every computation branch. An input is accepted if and only if at least one branch accepts. One may require all branches to halt: the configuration graph has only a polynomial number of vertices, so a logarithmic space counter can stop any branch that has taken more steps than that bound. If an accepting computation exists, one exists with no repeated Turing machine configuration, so this convention does not change the complexity class.

In standard space complexity notation,

Let a deterministic Turing machine $M$ decide $A$ with at most $s(n)=c\log (n+2)$ work-tape cells. Fix an input $x$ of length $n$. A Turing machine configuration is determined by the control state, the read-only input-head position, the work-tape contents, and the work-head positions. For one work tape with alphabet $\Gamma$, their number is bounded, up to harmless fixed factors, byThe factors respectively count the state, input-head position, work-head position and work-tape contents. With a fixed number $r$ of work tapes, replace the last two factors by $(s(n)+1{)}^r|\Gamma {|}^{rs(n)}$ if each tape is allowed $s(n)$ cells; this still gives a valid polynomial upper bound. Two-way work tapes only change fixed factors in the head-position bounds.

Sincethere are at most $(n+2{)}^d$ Turing machine configurations for some constant $d$ depending on $M$. If a deterministic computation repeats one of its Turing machine configurations on the fixed input, all subsequent steps repeat too, so it never halts. But $M$ is a decider. It therefore halts before any repetition and takes at most a polynomial number of steps. The same Turing machine is consequently a polynomial-time algorithm, establishingIt would be incorrect to count just the work-tape contents and omit the read-only input-head position; that position is part of the Turing machine configuration even though the input itself is not charged as work space.

A nondeterministic finite automaton, allowing the epsilon transitions used in this paper, is a tupleHere $Q$ is a nonempty finite set of automaton states, $\Sigma$ is a finite alphabet, $\mathcal{P}(Q)$ is the power set of $Q$, $q_0\in Q$ is the initial automaton state, and $F\subseteq Q$ is the set of accepting automaton states. The symbol $\epsilon \notin \Sigma$ denotes the empty word. Membership $r\in \delta (q,a)$ permits an automaton transition from $q$ to $r$ consuming $a$ when $a\in \Sigma$, or consuming nothing when $a=\epsilon$.

The recognized formal language isThe label of a graph path is the concatenation of its labels with all occurrences of $\epsilon$ omitted. Thus acceptance requires consuming the entire input word; a single successful choice of automaton transitions suffices. A path of length zero is allowed, so the empty word is accepted whenever $q_0\in F$, or an accepting automaton state is reachable by epsilon transitions. If epsilon transitions are excluded from the definition of a nondeterministic finite automaton, the displayed version is called an Epsilon-NFA.

A nondeterministic pushdown automaton is a tupleHere $Q$ is a nonempty finite set of control states, $\Sigma$ a finite input alphabet, $\Gamma$ a finite stack alphabet, $q_0\in Q$ the initial control state, $Z_0\in \Gamma$ the initial stack symbol, and $F\subseteq Q$ the final control states. The notation ${\mathcal{P}}_{\mathrm{fin}}$ requires each transition to have only finitely many choices. Since the domain is finite, the whole transition specification is finite.

A pushdown automaton configuration is $(q,w,\alpha )\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$, recording the control state, unread input word, and stack contents. Write the top of the stack on the left. For $a\in \Sigma$, the one-step relation isAn epsilon transition instead hasThus a move replaces the top stack symbol $X$ by the word $\gamma$, whose leftmost symbol becomes the new top. It consumes one input symbol or no input symbol. Under this convention there is no move from an empty stack.

For acceptance by final state, the recognized formal language isHere ${⊢}_M^{\ast }$ allows any finite number of moves, including zero. The entire input must have been consumed; the final stack need not be empty. Acceptance requires at least one such run of the nondeterministic pushdown automaton.

Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states $q_s,q,q_f$, input alphabet $\{a,b\}$, stack alphabet $\{S,T,U,a,b,\perp \}$, initial control state $q_s$, initial stack symbol $\perp$, and sole final control state $q_f$. The symbol $\perp$ is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.

Initialize withIn control state $q$, replace a top nonterminal symbol by one of its production rule right-hand sides:The replacements are written in the order in which they are to be processed. For example, replacing $S$ by $UST$ leaves $U$ on top; an implementation using individual push operations pushes $T$, then $S$, then $U$.

Match and pop top terminal symbols byFinally includeAll unlisted transitions have no choices; $q_f$ has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and $q_f$ cannot consume it.

For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is $u$ and the stack above $\perp$ is $\alpha$, then $S{\Rightarrow }_G^{\ast }u\alpha$. Acceptance gives $S{\Rightarrow }_G^{\ast }w$ for the entire input $w$.

Conversely, any leftmost derivation of $w$ specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of $w$ are consumed, only $\perp$ remains, enabling the move to $q_f$. The nondeterministic pushdown automaton therefore recognizes exactly $L(G)$. The empty word is accepted by choosing $S\to \epsilon$ after initialization.

$P$ is a co-recursively enumerable language, is not a recursively enumerable language, and is not a decidable language. The stipulated order on halting times includes $\infty \ge \infty$.

First, failure has a finite witness. For valid machine descriptions,Indeed, a strict inequality $t(N_1,x)<t(N_2,x)$ forces the first halting time to be finite. The second can be either a larger finite time or infinity. Whether the displayed condition holds for fixed $x,t$ is decidable by a finite simulation, including the initial configurations when $t=0$.

Enumerate all pairs $(x,t)$ and perform these finite tests by dovetailing, accepting the complement of a set of $P$ on finding a witness. Equivalently, at stage $s$, inspect all inputs of length at most $s$ through $s$ transitions. A genuine violation eventually appears; if there is no violation, the procedure never accepts. Malformed descriptions or differing input alphabets can be recognized and accepted as nonmembers immediately. Thus the complement is a recursively enumerable language, proving that $P$ is a co-recursively enumerable language.

For non-enumerability, use the standard result that the complement of a set of the halting problemis not a recursively enumerable language. Given $⟨M,w⟩$, effectively construct two Turing machines over the same fixed input alphabet. On every input $x$, let $N_1$ ignore $x$ and simulate $M$ on the fixed word $w$, halting precisely when that simulation halts. Let $N_2$ loop forever on every input.

If $M$ does not halt on $w$, both halting times are infinity for every $x$, so the pair belongs to $P$. If $M$ halts on $w$, the first halting time is finite while the second is infinity, so the pair does not belong to $P$. ThereforeThis is a many-one reduction from non-halting to the pointwise running-time domination problem. Were $P$ a recursively enumerable language, constructing the pair and running its recognizer would recognize non-halting, contradicting the stated result. Hence $P$ is not a recursively enumerable language. Since every decidable language is a recursively enumerable language, $P$ is also undecidable.

Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tupleHere $Q$ is a nonempty finite set of control states, $\Gamma$ a finite tape alphabet with a designated blank symbol $\square$, $\Sigma \subseteq \Gamma \setminus \{\square \}$ the input alphabet, $q_0\in Q$ the initial control state, and $q_{\mathrm{acc}},q_{\mathrm{rej}}\in Q$ distinct halting control states. The transition function is total on the displayed domain. The Turing machine instruction $\delta (q,a)=(r,b,D)$ means to write $b$ over the scanned $a$, enter control state $r$, and move the head one cell in direction $D$.

A Turing machine configuration is $(q,\tau ,h)$, where $q\in Q$, $h\in \mathbb{Z}$ is the head position, and $\tau :\mathbb{Z}\to \Gamma$ is the tape-content function, equal to $\square$ outside a finite set. Its next-configuration relation isif $\delta (q,\tau (h))=(r,b,D)$, with $d=-1$ for $D=L$ and $d=1$ for $D=R$, andThere is no successor to either halting Turing machine configuration.

For input $w=a_0\cdots a_{n-1}$, the initial Turing machine configuration is $C_0(w)=(q_0,{\tau }_w,0)$, where ${\tau }_w(j)=a_j$ for $0\le j<n$ and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language isThe relation ${⊢}_M^{\ast }$ permits any finite number of transitions. An input outside $L(M)$ may reach the rejecting control state or run forever; recognition does not require halting on every input.

Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite alphabet, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space $S=D_L\cup \{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.

At word $w$, an action is a position–letter pair $(i,\ell )$ with $1\le i\le L$, $\ell \in \Sigma$ and $\ell \ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, and the goal test is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.

Assign each permitted transition cost $1$. A search node at search depth $k$ hasThus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

For a discrete memoryless channel with transition probabilities $M(y\mid x)$, the conditional probability of a length-$n$ output given a length-$n$ input factors asThe same transition probabilities apply at each use. Its channel capacity isThe unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.

An $(m,n)$ channel code consists of an encoder $c:{\mathcal{V}}_m\to {\mathcal{X}}^n$ and a decoder $d:{\mathcal{Y}}^n\to {\mathcal{V}}_m$. It represents each of $m$ messages by $n$ input symbols and recovers a message from the $n$ observed output symbols. Its code rate is $R=({\log }_{2}m)/n$ bits per use. For each message $w$, its conditional error probability is $\mathbb{P}(d(Y^n)\ne w\mid W=w)$; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.

Write $T=g(Y)$. Because $T$ is determined by $Y$, the chain rule for mutual information givesThis is the data processing inequality. It holds for every input probability distribution. Maximizing each side over that same set of input probability distributions gives $C_{g(Y)}\le C_Y$; processing cannot increase channel capacity.

A simple sufficient condition for equality is that $g$ be injective on the reachable output alphabet. Then $Y$ can be recovered from $T$, giving $H(Y\mid T)=0$ and hence $I(X;Y\mid T)=0$ for every input law. The input that achieves the original channel capacity therefore achieves it after processing as well. Values of $g$ outside reachable outputs are irrelevant.

Injectivity is sufficient rather than necessary. More precisely, for finite alphabets equality in capacity data processing holds exactly when there is an original capacity-achieving input law for which $X$ and $Y$ have conditional independence given $T$. Sufficiency follows from the displayed gap identity. For necessity, maximize $I(X;T)$ at an input law $p_{\ast }$; if its maximum equals $C_Y$, then $C_Y=I_{p_{\ast }}(X;T)\le I_{p_{\ast }}(X;Y)\le C_Y$, so both inequalities are equalities. Processing may discard output details unrelated to the input without losing channel capacity.

Each of the three input values has two possible outputs, so their union has at most six elements. The preceding union formula also gives this bound. Choose noise values $0,3$, whose two translated input alphabets are disjoint. With columns ordered $0,1,2,3,4,5$ the transition matrix isThus $|\mathcal{Y}|=6$. Every output determines its input, explicitly $X=Y\mathrm{mod}3$, so $H(X\mid Y)=0$. Consequently $I(X;Y)=H(X)\le {\log }_{2}3$, with equality for a uniform input. ThereforeThe extra uncertainty of which noise value occurred does not reduce information about the input: the two possible outputs for each input remain distinguishable from those of every other input.

Translate the output alphabet by $-\min (z_1,z_2)$ and put $d=|z_2-z_1|\ge 1$. The reachable outputs becomeFor $d=1$ the two sets overlap in two points; for $d=2$ in one; for $d\ge 3$ they are disjoint. In particular $|\mathcal{Y}|\ge 4$, and choosing noise values $0,1$ attains four.

With rows indexed by inputs $0,1,2$ and columns by outputs $0,1,2,3$, independence and uniform two-point noise giveEvery conditional output distribution has information entropy one bit, so $I(X;Y)=H(Y)-1\le {\log }_{2}4-1=1$. The input probability mass function $(1/2,0,1/2)$ makes all four outputs equiprobable, attaining that bound. ThusUsing a zero-probability input in a channel-capacity maximization is legitimate; it is unrelated to the strictly positive source weights needed for the tree-shape claims in Question 2.