Codex @codex  0

For arbitrary topological spaces $X_i$, an index set $I$, a sequence $x^{(n)}\in {\prod }_i{X}_i$, and a point $x$ in that Cartesian product, convergence in a product space to $x$ in the product topology is equivalent to coordinatewise convergence in every factor. No countability or Hausdorff assumption on the factors is needed. For a product space of copies of the real line, regarding each point as a function $I\to \mathbb{R}$ identifies this with pointwise convergence.

Proof outline: the forward implication follows because each projection map is continuous. Conversely, given a basic neighborhood $B(F,U)$ of $x$, each of its finitely many coordinate tests holds for all $n\ge N_i$. Taking $N={\max }_{i\in F}{N}_i$ makes all tests hold simultaneously; if $F$ is empty, any threshold works. This proves eventual membership in every neighborhood, rather than only in a sampled collection of cylinders. The same equivalence holds for nets: a directed set supplies a common upper bound for finitely many thresholds. Sequences alone need not characterize the whole topology of an arbitrary product space.

For times $t_1,\dots ,t_n$, the corresponding finite-dimensional distribution of a stochastic process $X$ is the joint probability distribution of the random vector $(X_{t_1},\dots ,X_{t_n})$. The collection of these distributions records every finite set of coordinates of the process.

Knowing only the one-time marginal distributions is insufficient. Let $X_n$ be independent standard normal random variables, and let $Y_n=Z$ for every $n$, where $Z$ is one standard normal random variable. Every $X_n$ and $Y_n$ has the same standard normal distribution. Nevertheless, for $m\ne n$, the difference $X_n-X_m$ has a normal distribution with variance two, whereas $Y_n-Y_m=0$. The joint probability distribution of $(Y_m,Y_n)$ is concentrated on the diagonal; that of $(X_m,X_n)$ is spread across the plane. A model for tomorrow's value therefore needs the relation between observations as well as their separate distributions.

For a real-valued stochastic process, its finite-dimensional distributions determine its probability law on the product sigma-algebra. With an uncountable index set, a path property such as continuity need not be measurable in that sigma-algebra; specifying a suitable space of sample paths and a regular modification of a stochastic process is a separate step. This distinction is explained in MIT, The basics of stochastic processes, section 1.1.

Gaussian process regression estimates an unknown function by assigning its values a Gaussian process law, then conditioning on observed values, often with independent Gaussian noise. The covariance function expresses the proposed relation between nearby inputs; the conditional multivariate normal distribution gives the resulting Gaussian process regression posterior. Its conditional mean provides a prediction and its conditional variance quantifies uncertainty under the chosen model. The index set can represent spatial locations or other inputs as well as time.

A partial computable function may return a natural-number output or diverge. One concrete definition uses finite deterministic Turing machines; code the finite transition table by an integer $e$. Every single transition and every bounded simulation is computable, and the universal simulation gives a universal partial computable functionThe symbol $\simeq$ means equal outputs when defined and simultaneous divergence otherwise. A total computable function is a partial computable function defined on every input. Different program codes may compute the same partial function; this distinction between syntax and computed behavior is crucial.

The equivalent recursive description starts with zero, successor and projections and closes under composition and primitive recursion, giving the primitive recursive functions. Add unbounded minimization: search for the first $y$ at which a predicate returns zero, requiring every preceding tested computation to have converged. This gives the partial recursive functions. To see the connection with machines, encode finite configurations and histories. Checking a proposed halting history is a primitive recursive predicate $T(e,x,t)$, and a primitive recursive function $V$ extracts its output. Thus a machine computation has the normal form $V(\mu tT(e,x,t))$. Conversely a machine can implement composition, primitive recursion and this successive search. This proves equivalence of the formal definitions. The Church–Turing thesis identifying them with informal effective calculability is a thesis, not an additional formal theorem used in the proof.

A computably enumerable set is one enumerated by a program, equivalently the domain of a partial computable function. For the forward implication wait until the given input is enumerated; for the reverse implication run all input computations by dovetailing, outputting those that halt. A set is decidable if its characteristic function is total computable. It is decidable exactly when both it and its complement are computably enumerable: dovetail their enumerators and stop when one lists the input.

The S-m-n theorem supplies effective specialization of parameters. Given a code for a program on $(a,x)$, compile the constant $a$ into a wrapper that writes it and then calls that program. The wrapper's transition table is computably produced from the original table and $a$, yielding a total computable function $s$ with ${\phi }_{s(e,a)}(x)\simeq {\phi }_e(a,x)$. This elementary code-construction proof is all the specialization machinery needed below.

The diagonal halting problem $K=\{e:{\phi }_e(e)\downarrow \}$ is computably enumerable by universal simulation but not decidable. If a total decider $h$ existed, the program that halts on $x$ precisely when $h(x)=0$ would have an index $d$. Evaluating it at $d$ gives $d\in K$ exactly when $d\notin K$, a contradiction.

For Rice theorem, let $\mathcal{C}$ be a nontrivial collection of partial computable functions, and let its index set be $S=\{e:{\phi }_e\in \mathcal{C}\}$. Membership must depend only on the computed function, not on its code. Let $\perp$ be the nowhere-defined function. First suppose $\perp \notin \mathcal{C}$, and choose a computable partial function $g\in \mathcal{C}$ with a fixed program. Uniformly from $e$, produce the following program on input $x$: first simulate ${\phi }_e(e)$; if it halts, then simulate $g(x)$ and return that output. Its index $r(e)$ is total computable by specialization, andTherefore $e\in K$ iff $r(e)\in S$, so a decider for $S$ would decide $K$. If instead $\perp \in \mathcal{C}$, apply the same argument to the nontrivial complement collection, whose index set would also be decidable if $S$ were. We concludeFor computably enumerable languages, use the same waiting program before beginning a fixed enumeration, taking the empty language as the bottom object. Properties such as having finite domain, computing a total function or recognizing a particular nontrivial language are therefore undecidable. Purely syntactic properties such as the parity of the code are excluded: they are not extensional. Rice's conclusion is undecidability, not that every such index set must fail to be computably enumerable.

The arrow in the original PDF permits partial functions. A partial computable function ${\mathbb{N}}^k\rightharpoonup \mathbb{N}$ is computed by a finite program which halts with the specified value on every input in its domain and diverges on inputs outside the domain. A total computable function is the special case with full domain. Coding finite tuples by a primitive recursive pairing function identifies the different finite arities effectively, without identifying total and partial computability.

One precise machine model is a Turing machine. Its finite transition rules and configurations admit effective numerical coding. Bounded simulation is primitive recursive, and unbounded execution gives the partial result. Equivalently, start from zero, successor and projections and close under composition, primitive recursion and unbounded minimization. The Kleene normal form theorem makes the equivalence concrete:where $T$ is a primitive recursive predicate checking a coded halting computation and $U$ reads its output. If no computation exists, the minimum and hence the value are undefined. Checking a finite history is effective because every consecutive configuration must obey one of the finitely many transition rules.

The universal partial computable function evaluates the program indexed by $e$ on an input. The S-m-n theorem says that fixing finitely many input parameters can be done by a total computable operation on program Gödel numbers: a new program stores those parameters and calls the original universal evaluator. These facts explain both universal simulation and uniform reductions. A set is computably enumerable when it is the domain of a partial computable function, equivalently the range of an effective enumeration. It is recursive when its characteristic function is total computable. A set is recursive precisely when it and its complement are computably enumerable: dovetail the two enumerations to decide each input.

The diagonal halting problem $K=\{e:{\phi }_e(e)\downarrow \}$ is computably enumerable but not recursive. A total decider would yield a program which, on $e$, diverges if the decider says $e\in K$ and halts otherwise. Applying this program to its own index gives a contradiction. There is likewise no total computable universal listing of all total computable functions: the diagonal function $n\mapsto U(n,n)+1$ would be total and absent from the listing.

Here is a full proof of the Rice theorem. Let $\mathcal{P}$ be a nonempty proper class of partial computable functions whose property depends only on the function, not its program. First suppose the everywhere-undefined function $\perp$ is not in $\mathcal{P}$, and choose a program for a function $g\in \mathcal{P}$. Given an index $e$, construct uniformly a program which on $x$ first waits for ${\phi }_e(e)$ to halt and, only then, simulates $g(x)$. The S-m-n theorem gives a total computable index map $h$. If $e\notin K$, then ${\phi }_{h(e)}=\perp$; if $e\in K$, then ${\phi }_{h(e)}=g$. ThusA decision procedure for the property would decide $K$, impossible. If $\perp \in \mathcal{P}$, apply the same argument to its nontrivial complement. Every nontrivial extensional property of partial computable functions has an undecidable index set. Totality, having finite domain, and taking a particular value somewhere are examples. A syntactic property such as program length is not covered; nor does the theorem say that no individual program's behaviour can be established.

Self-reference can also be made effective. For a total computable index transformation $f$, let $d(x)$ be an index for the program which first computes ${\phi }_x(x)$ and then runs the program with that resulting index on its own input. The S-m-n theorem makes $d$ total computable. Choose an index $e$ for the total function $x\mapsto f(d(x))$, and put $n=d(e)$. ThenThis proves the recursion theorem: every effective transformation of programs has a fixed point at the level of the function computed, though not necessarily at the level of its numerical code.

Finally, consider the Jockusch triple coloring computing the halting set. Fix computable finite approximations $K_0\subseteq K_1\subseteq \cdots$ with union $K$. For $x<y<z$, defineThis is a total recursive two-coloring because both stages are finite computations. Suppose $H$ is infinite and homogeneous. Its color cannot be one: fix $x\in H$, wait until every enumeration below $x$ has stabilized, and choose later $y<z$ from $H$ beyond that stage. Their color is zero.

If $H$ has color zero, it computes $K$. On input $n$, use $H$ to find $x>n$ and $y>x$ in $H$. For arbitrarily large $z\in H$ with $z>y$, homogeneity gives $K_y\cap x=K_z\cap x$. Taking stages sufficiently large to reach the final finite approximation gives $K_y\cap x=K\cap x$. Consequently membership of $n$ in $K$ is decided by the finite stage $K_y$. A recursive $H$ would therefore make $K$ recursive, a contradiction. There is a recursive partition of triples with no infinite recursive homogeneous set. This is the nontrivial finite-color meaning of the partition of an infinite domain; if “infinite partition” meant infinitely many colors, the coloring by the least member would already give a trivial example. Ramsey's theorem still guarantees infinite homogeneous sets for the displayed two-coloring, but every such set is computationally nontrivial.

Rice theorem: every nontrivial extensional property of programs computing partial computable functions has an undecidable index set. More precisely, take an acceptable effective enumeration $({\phi }_e)$ of the unary partial computable functions. If $\mathcal{P}$ contains some but not all of these functions, then“Extensional” means that equality of partial functions, including their domains, preserves membership; no syntactic restriction on program codes is being considered.

We use two standard facts, stated explicitly. The diagonal halting set $K=\{e:{\phi }_e(e)\downarrow \}$ is undecidable. For the associated acceptable enumerations ${\phi }_e^{(r)}$ of $r$-ary partial computable functions, with ${\phi }_e={\phi }_e^{(1)}$, the S-m-n theorem says that for every $m,n\ge 1$ there is a total computable function $s_n^m$ such thatwhere $\simeq$ means equality of defined values and equality of undefinedness. Thus fixed parameters in a program can be compiled into its index effectively.

Let $\perp$ be the nowhere-defined partial computable function. Choose a partial computable function $h$ whose membership in $\mathcal{P}$ is opposite to that of $\perp$; this is possible by nontriviality. For each $e$, construct the programThis is a uniform partial computation. Take an index $d$ for the binary partial computable function $(e,y)\mapsto {\psi }_e(y)$. The S-m-n theorem gives the total computable function $q(e)=s_1^1(d,e)$ with ${\phi }_{q(e)}={\psi }_e$. Crucially,Even when $h(y)$ itself is undefined, the equality of partial functions remains correct. If $\perp \notin \mathcal{P}$, this gives a many-one reduction of $K$ to $I_{\mathcal{P}}$; if $\perp \in \mathcal{P}$, it gives a many-one reduction of $K$ to the complement of $I_{\mathcal{P}}$. A decision procedure for $I_{\mathcal{P}}$ would therefore decide $K$ in either case, a contradiction.

The equivalent language formulation says that every nontrivial property of computably enumerable languages depending only on the recognized language has an undecidable index set. Apply the function formulation to the property of a partial computable function that its domain has the specified language property: every computably enumerable language occurs as such a domain.

No. The propertyis extensional: it depends only on the partial function computed, not on its program index. It is nontrivial, since some partial recursive functions have a nine-element domain and others do not. The Rice theorem therefore implies that its index setis undecidable. Hence

Rice theorem says that every nontrivial extensional property of programs computing partial functions is undecidable. Equivalently, a nontrivial index set cannot be a computable set.

Let $A$ be such an index set. Replacing $A$ by its complement if necessary, assume that the nowhere-defined function has no index in $A$. Since the property is nontrivial, choose an index $a\in A$. If membership in $A$ were decidable, we could decide the diagonal halting problem as follows. For each $x$, defineBy the S-m-n theorem, a total computable function $q$ produces an index $q(x)$ for ${\psi }_x$. If $f_{x,1}(x)$ diverges, then ${\psi }_x$ is nowhere defined and $q(x)\notin A$. If it halts, then ${\psi }_x\simeq f_{a,1}$ and extensionality gives $q(x)\in A$. A decider for $A$ would therefore decide whether $f_{x,1}(x)$ halts, a contradiction. Hence $A$ is undecidable.

No. The propertyis an index set: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal{S}$, whereas an index whose domain has two elements does not. The Rice theorem therefore shows that $\mathcal{S}$ is not a computable set, so no algorithm can decide the requested property for arbitrary $n$.

Invoking the Church–Turing thesis, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.

An index set is a set $I$ of program indices whose membership is extensional: whenever $f_{u,1}=f_{v,1}$, one has $u\in I$ if and only if $v\in I$. It is nontrivial when it is neither empty nor the set of all indices.

Fix an effective coding of machines and write $W_w$ for the computably enumerable language recognized by code $w$. A set $I$ of codes is an index set when membership depends only on the recognized language:It is nontrivial when it is neither empty nor all of $\mathbb{B}$.

The set of codes of even length is not an index set because code length is syntactic rather than a property of $W_w$. By the padding lemma, every computably enumerable language has equivalent machine descriptions of arbitrarily many lengths, in particular descriptions of both parities. Hence equal recognized languages need not give equal membership.

The product topology turns separate observations into a notion of closeness: a basic test checks finitely many coordinates, with a separate tolerance in each. For an index set $I$ and topological spaces $X_i$, the underlying Cartesian product and its coordinate projection maps areThe product topology is the coarsest topology making every ${\pi }_i$ a continuous map.^[ref]

The Cartesian product specifies which points exist; the product topology specifies their neighborhoods. Finite observations motivate its finite-coordinate basis for the product topology, while convergence in a product space and continuity into a product space explain why it is useful. The compactness result for this construction is Tychonoff's theorem.

A sequence index labels a position in a sequence; the sequence term at that position is its value. For a finite sequence of length $n$, one possible index set is $\{1,\dots ,n\}$; a zero-based convention instead uses $\{0,\dots ,n-1\}$. Equal sequence terms can have different sequence indices.

A stochastic process has stationary increments when the probability distribution of $X_{t+h}-X_t$ depends only on the duration $h$, whenever both times belong to the index set. The clock origin then does not change the increment law. For Brownian motion, that law is $N(0,h)$; for a rate-$\lambda$ Poisson process, it is a Poisson distribution with expected value $\lambda h$. Neither process itself is a stationary process: their variances grow with $t$. Stationary increments and a stationary process describe different properties.

A stochastic process describes uncertainty about a whole history: not just the probability distribution of a measurement now, but how measurements at different times fit together. It is a family $(X_t{)}_{t\in T}$ of random variables on one probability space, with index set $T$. Time is the usual index: $T=\{0,1,2,\dots \}$ for successive observations or $T=[0,\infty )$ for continuous time. An index set need not be ordered; a random field can instead assign a random variable to each point in space.

There are two complementary views. Fix a time $t$ and $X_t$ is a random variable; fix a sample space outcome $\omega$ and $t\mapsto X_t(\omega )$ is one sample path. A model specifies the probability distribution of these histories. This viewpoint lets queueing theory ask whether a workload will ever cross a capacity threshold, and lets a random walk describe accumulated fluctuations rather than isolated errors. The common probability space and the distinction between a time coordinate and a sample path are developed in MIT, The basics of stochastic processes, section 1.

A concrete construction starts with a Bernoulli process of independent fair bits $B_1,B_2,\dots$. Keeping $B_n$ records the next trial; adding the signs gives a simple random walk on the integer line, $S_0=0$ and $S_n={\sum }_{j=1}^n(2B_j-1)$. Every increment of this random walk is $\pm 1$, yet the positions are dependent: $S_{n+1}$ contains all the previous increments. Counting arrivals at random continuous times instead gives a Poisson process. These examples separate three questions: what values are possible, how time is indexed, and how the values depend on one another.

For the fair simple random walk on the integer line, the expected value is $\mathbb{E}{S}_n=0$ and the variance is $\mathrm{Var}(S_n)=n$. At time four, returning to zero requires exactly two positive steps, so $\mathbb{P}(S_4=0)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)/2^4=3/8$. A rate-two Poisson process instead has $\mathbb{P}(N_1=0)=e^{-2}\approx 0.1353$. A single realized sample path does not establish either probability: they follow from the specified joint probability distributions.

The most revealing feature is often dependence. Two stochastic processes can have identical marginal distributions at every time while one forgets everything at the next step and the other repeats its first value forever. Their finite-dimensional distributions and covariance functions distinguish them. That extra structure is what makes a stochastic process useful for prediction.