Solomonoff's theory of inductive inference

Solomonoff's theory of inductive inference proves that, under its common sense assumptions (axioms), the best possible scientific model is the shortest algorithm that generates the empirical data under consideration. In addition to the choice of data, other assumptions are that, to avoid the post-hoc fallacy, the programming language must be chosen prior to the data and that the environment being observed is generated by an unknown algorithm. This is also called a theory of induction. Due to its basis in the dynamical (state-space model) character of Algorithmic Information Theory, it encompasses statistical as well as dynamical information criteria for model selection. It was introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes' rule and some universal prior, that is, a prior that assigns a positive probability to any computable theory. Solomonoff proved that this induction is incomputable (or more precisely, lower semi-computable), but noted that "this incomputability is of a very benign kind", and that it "in no way inhibits its use for practical prediction" (as it can be approximated from below more accurately with more computational resources). It is only "incomputable" in the benign sense that no scientific consensus is able to prove that the best current scientific theory is the best of all possible theories. However, Solomonoff's theory does provide an objective criterion for deciding among the current scientific theories explaining a given set of observations. Solomonoff's induction naturally formalizes Occam's razor by assigning larger prior credences to theories that require a shorter algorithmic description. == Origin == === Philosophical === The theory is based in philosophical foundations, and was founded by Ray Solomonoff around 1960. It is a mathematically formalized combination of Occam's razor and the Principle of Multiple Explanations. All computable theories which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories. Marcus Hutter's universal artificial intelligence builds upon this to calculate the expected value of an action. === Principle === Solomonoff's induction has been argued to be the computational formalization of pure Bayesianism. To understand, recall that Bayesianism derives the posterior probability P [ T | D ] {\displaystyle \mathbb {P} [T|D]} of a theory T {\displaystyle T} given data D {\displaystyle D} by applying Bayes rule, which yields P [ T | D ] = P [ D | T ] P [ T ] P [ D | T ] P [ T ] + ∑ A ≠ T P [ D | A ] P [ A ] {\displaystyle \mathbb {P} [T|D]={\frac {\mathbb {P} [D|T]\mathbb {P} [T]}{\mathbb {P} [D|T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D|A]\mathbb {P} [A]}}} where theories A {\displaystyle A} are alternatives to theory T {\displaystyle T} . For this equation to make sense, the quantities P [ D | T ] {\displaystyle \mathbb {P} [D|T]} and P [ D | A ] {\displaystyle \mathbb {P} [D|A]} must be well-defined for all theories T {\displaystyle T} and A {\displaystyle A} . In other words, any theory must define a probability distribution over observable data D {\displaystyle D} . Solomonoff's induction essentially boils down to demanding that all such probability distributions be computable. Interestingly, the set of computable probability distributions is a subset of the set of all programs, which is countable. Similarly, the sets of observable data considered by Solomonoff were finite. Without loss of generality, we can thus consider that any observable data is a finite bit string. As a result, Solomonoff's induction can be defined by only invoking discrete probability distributions. Solomonoff's induction then allows to make probabilistic predictions of future data F {\displaystyle F} , by simply obeying the laws of probability. Namely, we have P [ F | D ] = E T [ P [ F | T , D ] ] = ∑ T P [ F | T , D ] P [ T | D ] {\displaystyle \mathbb {P} [F|D]=\mathbb {E} _{T}[\mathbb {P} [F|T,D]]=\sum _{T}\mathbb {P} [F|T,D]\mathbb {P} [T|D]} . This quantity can be interpreted as the average predictions P [ F | T , D ] {\displaystyle \mathbb {P} [F|T,D]} of all theories T {\displaystyle T} given past data D {\displaystyle D} , weighted by their posterior credences P [ T | D ] {\displaystyle \mathbb {P} [T|D]} . === Mathematical === The proof of the "razor" is based on the known mathematical properties of a probability distribution over a countable set. These properties are relevant because the infinite set of all programs is a denumerable set. The sum S of the probabilities of all programs must be exactly equal to one (as per the definition of probability) thus the probabilities must roughly decrease as we enumerate the infinite set of all programs, otherwise S will be strictly greater than one. To be more precise, for every ϵ {\displaystyle \epsilon } > 0, there is some length l such that the probability of all programs longer than l is at most ϵ {\displaystyle \epsilon } . This does not, however, preclude very long programs from having very high probability. Fundamental ingredients of the theory are the concepts of algorithmic probability and Kolmogorov complexity. The universal prior probability of any prefix p of a computable sequence x is the sum of the probabilities of all programs (for a universal computer) that compute something starting with p. Given some p and any computable but unknown probability distribution from which x is sampled, the universal prior and Bayes' theorem can be used to predict the yet unseen parts of x in optimal fashion. == Mathematical guarantees == === Solomonoff's completeness === The remarkable property of Solomonoff's induction is its completeness. In essence, the completeness theorem guarantees that the expected cumulative errors made by the predictions based on Solomonoff's induction are upper-bounded by the Kolmogorov complexity of the (stochastic) data generating process. The errors can be measured using the Kullback–Leibler divergence or the square of the difference between the induction's prediction and the probability assigned by the (stochastic) data generating process. === Solomonoff's uncomputability === Unfortunately, Solomonoff also proved that Solomonoff's induction is uncomputable. In fact, he showed that computability and completeness are mutually exclusive: any complete theory must be uncomputable. The proof of this is derived from a game between the induction and the environment. Essentially, any computable induction can be tricked by a computable environment, by choosing the computable environment that negates the computable induction's prediction. This fact can be regarded as an instance of the no free lunch theorem. == Modern applications == === Artificial intelligence === Though Solomonoff's inductive inference is not computable, several AIXI-derived algorithms approximate it in order to make it run on a modern computer. The more computing power they are given, the closer their predictions are to the predictions of inductive inference (their mathematical limit is Solomonoff's inductive inference). Another direction of inductive inference is based on E. Mark Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a class S of computable functions, is there a learner (that is, recursive functional) which for any input of the form (f(0),f(1),...,f(n)) outputs a hypothesis (an index e with respect to a previously agreed on acceptable numbering of all computable functions; the indexed function may be required consistent with the given values of f). A learner M learns a function f if almost all its hypotheses are the same index e, which generates the function f; M learns S if M learns every f in S. Basic results are that all recursively enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of recursively enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards. A far reaching extension of the Gold’s approach is developed by Schmidhuber's theory of generalized Kolmogorov complexities, which are kinds of super-recursive algorithms.

Super-resolution optical fluctuation imaging

Super-resolution optical fluctuation imaging (SOFI) is a post-processing method for the calculation of super-resolved images from recorded image time series that is based on the temporal correlations of independently fluctuating fluorescent emitters. SOFI has been developed for super-resolution of biological specimen that are labelled with independently fluctuating fluorescent emitters (organic dyes, fluorescent proteins). In comparison to other super-resolution microscopy techniques such as STORM or PALM that rely on single-molecule localization and hence only allow one active molecule per diffraction-limited area (DLA) and timepoint, SOFI does not necessitate a controlled photoswitching and/ or photoactivation as well as long imaging times. Nevertheless, it still requires fluorophores that are cycling through two distinguishable states, either real on-/off-states or states with different fluorescence intensities. In mathematical terms SOFI-imaging relies on the calculation of cumulants, for what two distinguishable ways exist. For one thing an image can be calculated via auto-cumulants that by definition only rely on the information of each pixel itself, and for another thing an improved method utilizes the information of different pixels via the calculation of cross-cumulants. Both methods can increase the final image resolution significantly although the cumulant calculation has its limitations. Actually SOFI is able to increase the resolution in all three dimensions. == Principle == Likewise to other super-resolution methods SOFI is based on recording an image time series on a CCD- or CMOS camera. In contrary to other methods the recorded time series can be substantially shorter, since a precise localization of emitters is not required and therefore a larger quantity of activated fluorophores per diffraction-limited area is allowed. The pixel values of a SOFI-image of the n-th order are calculated from the values of the pixel time series in the form of a n-th order cumulant, whereas the final value assigned to a pixel can be imagined as the integral over a correlation function. The finally assigned pixel value intensities are a measure of the brightness and correlation of the fluorescence signal. Mathematically, the n-th order cumulant is related to the n-th order correlation function, but exhibits some advantages concerning the resulting resolution of the image. Since in SOFI several emitters per DLA are allowed, the photon count at each pixel results from the superposition of the signals of all activated nearby emitters. The cumulant calculation now filters the signal and leaves only highly correlated fluctuations. This provides a contrast enhancement and therefore a background reduction for good measure. As it is implied in the figure on the left the fluorescence source distribution: ∑ k = 1 N δ ( r → − r → k ) ⋅ ε k ⋅ s k ( t ) {\displaystyle \sum _{k=1}^{N}\delta ({\vec {r}}-{\vec {r}}_{k})\cdot \varepsilon _{k}\cdot s_{k}(t)} is convolved with the system's point spread function (PSF) U(r). Hence the fluorescence signal at time t and position r → {\displaystyle {\vec {r}}} is given by F ( r → , t ) = ∑ k = 1 N U ( r → − r → k ) ⋅ ε k ⋅ s k ( t ) . {\displaystyle F({\vec {r}},t)=\sum _{k=1}^{N}U({\vec {r}}-{\vec {r}}_{k})\cdot \varepsilon _{k}\cdot s_{k}(t).} Within the above equations N is the amount of emitters, located at the positions r → k {\displaystyle {\vec {r}}_{k}} with a time-dependent molecular brightness ε k ⋅ s k {\displaystyle \varepsilon _{k}\cdot s_{k}} where ε k {\displaystyle \varepsilon _{k}} is a variable for the constant molecular brightness and s k ( t ) {\displaystyle s_{k}(t)} is a time-dependent fluctuation function. The molecular brightness is just the average fluorescence count-rate divided by the number of molecules within a specific region. For simplification it has to be assumed that the sample is in a stationary equilibrium and therefore the fluorescence signal can be expressed as a zero-mean fluctuation: δ F ( r → , t ) = F ( r → , t ) − ⟨ F ( r → , t ) ⟩ t {\displaystyle \delta F({\vec {r}},t)=F({\vec {r}},t)-\langle F({\vec {r}},t)\rangle _{t}} where ⟨ ⋯ ⟩ t {\displaystyle \langle \cdots \rangle _{t}} denotes time-averaging. The auto-correlation here e.g. the second-order can then be described deductively as follows for a certain time-lag τ {\displaystyle \tau } : δ F ( r → , t ) = ⟨ δ F ( r → , t + τ ) ⋅ δ F ( r → , t ) ⟩ t {\displaystyle \delta F({\vec {r}},t)=\langle \delta F({\vec {r}},t+\tau )\cdot \delta F({\vec {r}},t)\rangle _{t}} From these equations it follows that the PSF of the optical system has to be taken to the power of the order of the correlation. Thus in a second-order correlation the PSF would be reduced along all dimensions by a factor of 2 {\displaystyle {\sqrt {2}}} . As a result, the resolution of the SOFI-images increases according to this factor. === Cumulants versus correlations === Using only the simple correlation function for a reassignment of pixel values, would ascribe to the independency of fluctuations of the emitters in time in a way that no cross-correlation terms would contribute to the new pixel value. Calculations of higher-order correlation functions would suffer from lower-order correlations for what reason it is superior to calculate cumulants, since all lower-order correlation terms vanish. == Cumulant-calculation == === Auto-cumulants === For computational reasons it is convenient to set all time-lags in higher-order cumulants to zero so that a general expression for the n-th order auto-cumulant can be found: A C n ( r → , τ 1 … n − 1 = 0 ) = ∑ k = 1 N U n ( r → − r → k ) ε k n w k ( 0 ) {\displaystyle AC_{n}({\vec {r}},\tau _{1\ldots n-1}=0)=\sum _{k=1}^{N}U^{n}({\vec {r}}-{\vec {r}}_{k})\varepsilon _{k}^{n}w_{k}(0)} w k {\displaystyle w_{k}} is a specific correlation based weighting function influenced by the order of the cumulant and mainly depending on the fluctuation properties of the emitters. Albeit there is no fundamental limitation in calculating very high orders of cumulants and thereby shrinking the FWHM of the PSF there are practical limitations according to the weighting of the values assigned to the final image. Emitters with a higher molecular brightness will show a strong increase in terms of the pixel cumulant value assigned at higher-orders as well as this performance can be expected from a diverse appearance of fluctuations of different emitters. A wide intensity range of the resulting image can therefore be expected and as a result dim emitters can get masked by bright emitters in higher-order images:. The calculation of auto-cumulants can be realized in a very attractive way in a mathematical sense. The n-th order cumulant can be calculated with a basic recursion from moments K n ( r → ) = μ n ( r → ) − ∑ i = 1 n − 1 ( n − 1 i ) K n − i ( r → ) μ i ( r → ) {\displaystyle K_{n}({\vec {r}})=\mu _{n}({\vec {r}})-\sum _{i=1}^{n-1}{\begin{pmatrix}n-1\\i\end{pmatrix}}K_{n-i}({\vec {r}})\mu _{i}({\vec {r}})} where K is a cumulant of the index's order, likewise μ {\displaystyle \mu } represents the moments. The term within the brackets indicates a binomial coefficient. This way of computation is straightforward in comparison with calculating cumulants with standard formulas. It allows for the calculation of cumulants with only little time of computing and is, as it is well implemented, even suitable for the calculation of high-order cumulants on large images. === Cross-cumulants === In a more advanced approach cross-cumulants are calculated by taking the information of several pixels into account. Cross-cumulants can be described as follows: C C n ( r → , τ 1 … n − 1 = 0 ) = ∏ j < l n U ( r → j − r → l n ) ⋅ ∑ i = 1 N U n ( r → i − ∑ k n r → k n ) ε i n w i ( 0 ) {\displaystyle CC_{n}({\vec {r}},\tau _{1\ldots n-1}=0)=\prod _{j

Sieve of Pritchard

In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound. Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds. Whereas the sieve of Eratosthenes marks off each non-prime for each of its prime factors, the sieve of Pritchard avoids considering almost all non-prime numbers by building progressively larger wheels, which represent the pattern of numbers not divisible by any of the primes processed thus far. It thereby achieves a better asymptotic complexity, and was the first sieve with a running time sublinear in the specified bound. Its asymptotic running-time has not been improved on, and it deletes fewer composites than any other known sieve. It was created in 1979 by Paul Pritchard. Since Pritchard has created a number of other sieve algorithms for finding prime numbers, the sieve of Pritchard is sometimes singled out by being called the wheel sieve (by Pritchard himself) or the dynamic wheel sieve. == Overview == A prime number is a natural number that has no natural number divisors other than the number 1 and itself. To find all the prime numbers less than or equal to a given integer N, a sieve algorithm examines a set of candidates in the range 2, 3, …, N, and eliminates those that are not prime, leaving the primes at the end. The sieve of Eratosthenes examines all of the range, first removing all multiples of the first prime 2, then of the next prime 3, and so on. The sieve of Pritchard instead examines a subset of the range consisting of numbers that occur on successive wheels, which represent the pattern of numbers left after each successive prime is processed by the sieve of Eratosthenes. For i > 0, the ith wheel Wi represents this pattern. It is the set of numbers between 1 and the product Pi = p1 · p2 ⋯ pi of the first i prime numbers that are not divisible by any of these prime numbers (and is said to have an associated length Pi). This is because adding Pi to a number does not change whether it is divisible by one of the first i prime numbers, since the remainder on division by any one of these primes is unchanged. So W1 = {1} with length P1 = 2 represents the pattern of odd numbers; W2 = {1,5} with length P2 = 6 represents the pattern of numbers not divisible by 2 or 3; etc. Wheels are so-called because Wi can be usefully visualized as a circle of circumference Pi with its members marked at their corresponding distances from an origin. Then rolling the wheel along the number line marks points corresponding to successive numbers not divisible by one of the first i prime numbers. The animation shows W2 being rolled up to 30. It is useful to define Wi → n for n > 0 to be the result of rolling Wi up to n. Then the animation generates W2 → 30 = {1,5,7,11,13,17,19,23,25,29}. Note that up to 52 − 1 = 24, this consists only of 1 and the primes between 5 and 25. The sieve of Pritchard is derived from the observation that this holds generally: for all i > 0, the values in Wi → (p2i+1 − 1) are 1 and the primes between pi+1 and p2i+1. It even holds for i = 0, where the wheel has length 1 and contains just 1 (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel W0 and builds successive wheels until the square of the wheel's first member after 1 is at least N. Wheels grow very quickly, but only their values up to N are needed and generated. It remains to find a method for generating the next wheel. Note in the animation that W3 = {1,5,7,11,13,17,19,23,25,29} − {5 · 1 , 5 · 5} can be obtained by rolling W2 up to 30 and then removing 5 times each member of W2.This also holds generally: for all i ≥ 0, Wi+1 = (Wi → Pi+1) − {pi+1 · w | w ∈ Wi}. Rolling Wi past Pi just adds values to Wi, so the current wheel is first extended by getting each successive member starting with w = 1, adding Pi to it, and inserting the result in the set. Then the multiples of pi+1 are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by pi+1. The sieve of Pritchard as originally presented does so by first skipping past successive members until finding the maximum one needed, and then doing the deletions in reverse order by working back through the set. This is the method used in the first animation above. A simpler approach is just to gather the multiples of pi+1 in a list, and then delete them. Another approach is given by Gries and Misra. If the main loop terminates with a wheel whose length is less than N, it is extended up to N to generate the remaining primes. The algorithm, for finding all primes up to N, is therefore as follows: Start with a set W = {1} and length = 1 representing wheel 0, and prime p = 2. As long as p2 ≤ N, do the following: if length < N, then extend W by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed p · length or N; increase length to the minimum of p · length and N. repeatedly delete p times each member of W by first finding the largest ≤ length and then working backwards. note the prime p, then set p to the next member of W after 1 (or 3 if p was 2). if length < N, then extend W to N by repeatedly getting successive members w of W starting with 1 and inserting length + w into W as long as it does not exceed N; On termination, the rest of the primes up to N are the members of W after 1. === Example === To find all the prime numbers less than or equal to 150, proceed as follows. Start with wheel 0 with length 1, representing all natural numbers 1, 2, 3...: 1 The first number after 1 for wheel 0 (when rolled) is 2; note it as a prime. Now form wheel 1 with length 2 × 1 = 2 by first extending wheel 0 up to 2 and then deleting 2 times each number in wheel 0, to get: 1 2 The first number after 1 for wheel 1 (when rolled) is 3; note it as a prime. Now form wheel 2 with length 3 × 2 = 6 by first extending wheel 1 up to 6 and then deleting 3 times each number in wheel 1, to get 1 2 3 5 The first number after 1 for wheel 2 is 5; note it as a prime. Now form wheel 3 with length 5 × 6 = 30 by first extending wheel 2 up to 30 and then deleting 5 times each number in wheel 2 (in reverse order), to get 1 2 3 5 7 11 13 17 19 23 25 29 The first number after 1 for wheel 3 is 7; note it as a prime. Now wheel 4 has length 7 × 30 = 210, so we only extend wheel 3 up to our limit 150. (No further extending will be done now that the limit has been reached.) We then delete 7 times each number in wheel 3 until we exceed our limit 150, to get the elements in wheel 4 up to 150: 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 The first number after 1 for this partial wheel 4 is 11; note it as a prime. Since we have finished with rolling, we delete 11 times each number in the partial wheel 4 until we exceed our limit 150, to get the elements in wheel 5 up to 150: 1 2 3 5 7 11 13 17 19 23 25 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 The first number after 1 for this partial wheel 5 is 13. Since 13 squared is at least our limit 150, we stop. The remaining numbers (other than 1) are the rest of the primes up to our limit 150. Just 8 composite numbers are removed, once each. The rest of the numbers considered (other than 1) are prime. In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times. == Pseudocode == The sieve of Pritchard can be expressed in pseudocode, as follows: algorithm Sieve of Pritchard is input: an integer N >= 2. output: the set of prime numbers in {1,2,...,N}. let W and Pr be sets of integer values, and all other variables integer values. k, W, length, p, Pr := 1, {1}, 2, 3, {2}; {invariant: p = pk+1 and W = Wk ∩ {\displaystyle \cap } {1,2,...,N} and length = minimum of Pk,N and Pr = the primes up to pk} while p2 <= N do if (length < N) then Extend W,length to minimum of plength,N; Delete multiples of p from W; Insert p into Pr; k, p := k+1, next(W, 1) if (length < N) then Extend W,length to N; return Pr ∪ {\displaystyle \cup } W - {1}; where next(W, w) is the next value in the ordered set W after w. procedure Extend W,length to n is {in: W = Wk and length = Pk and n > length} {out: W = Wk → {\displaystyle \rightarrow } n and length = n} integer w, x; w, x := 1, length+1; while x <= n do Insert x into W; w := next(W,w); x := length + w; length := n; procedure Delete multiples of p from W,length is integer w; w := p; while pw <= length do w := next(W,w); while w > 1 do w := prev(W,w); Remove pw from W; where prev(W, w) is the previous value in the ordered set W before w. The algorithm can be initialized with W0 instead of W1 at the minor complication of making next(W, 1) a special case when k = 0. This a

Transaction data

Transaction data or transaction information is a category of data describing transactions. Transaction data/information gather variables generally referring to reference data or master data – e.g. dates, times, time zones, currencies. Typical transactions are: Financial transactions about orders, invoices, payments; Work transactions about plans, activity records; Logistic transactions about deliveries, storage records, travel records, etc.. == Management == Recording and storing transactions is called records management. The record of the transaction is stored in a place where the retention can be guaranteed and where data is archived or removed following a retention period. Formats of recorded transactions can be digital data in databases and spreadsheets, or handwritten texts in physical documents like former bankbooks. Transaction processing systems are application software that generate transactions and manage transaction data/information, e.g. SAP and Oracle Financials. == Data warehousing == Transaction data can be summarised in a data warehouse, which helps accessibility and analysis of the data.

Algorithm

In mathematics and computer science, an algorithm ( ) is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning). In contrast, a heuristic is an approach to solving problems without well-defined correct or optimal results. For example, although social media recommender systems are commonly called "algorithms", they actually rely on heuristics as there is no truly "correct" recommendation. As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and input, a computation occurs at each step, eventually producing output and terminating. The transition between states can be non-deterministic; randomized algorithms incorporate random input. == Etymology == Around 825 AD, Persian scientist and polymath Muḥammad ibn Mūsā al-Khwārizmī wrote kitāb al-ḥisāb al-hindī ("Book of Indian computation") and kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Addition and subtraction in Indian arithmetic"). In the early 12th century, Latin translations of these texts involving the Hindu–Arabic numeral system and arithmetic appeared, for example Liber Alghoarismi de practica arismetrice, attributed to John of Seville, and Liber Algoritmi de numero Indorum, attributed to Adelard of Bath. Here, alghoarismi or algoritmi is the Latinization of Al-Khwarizmi's name; the text starts with the phrase Dixit Algoritmi, or "Thus spoke Al-Khwarizmi". The word algorism in English came to mean the use of place-value notation in calculations; it occurs in the Ancrene Wisse from circa 1225. By the time Geoffrey Chaucer wrote The Canterbury Tales in the late 14th century, he used a variant of the same word in describing augrym stones, stones used for place-value calculation. In the 15th century, under the influence of the Greek word ἀριθμός (arithmos, "number"; cf. "arithmetic"), the Latin word was altered to algorithmus. By 1596, this form of the word was used in English, as algorithm, by Thomas Hood. == Definition == One informal definition is "a set of rules that precisely defines a sequence of operations", which would include all computer programs, and any bureaucratic procedure or cook-book recipe. In general, a program is an algorithm only if it stops eventually. Formally, algorithm is an explicit set of instructions to produce an output, that can be followed by a computer or a human performing specific operations on symbols.. == History == === Ancient algorithms === Step-by-step procedures for solving mathematical problems have been recorded since antiquity. This includes in Babylonian mathematics (around 2500 BC), Egyptian mathematics (around 1550 BC), Indian mathematics (around 800 BC and later), the Ifa Oracle (around 500 BC), Greek mathematics (around 240 BC), Chinese mathematics (around 200 BC and later), and Arabic mathematics (around 800 AD). The earliest evidence of algorithms is found in ancient Mesopotamian mathematics. A Sumerian clay tablet found in Shuruppak near Baghdad and dated to c. 2500 BC describes the earliest division algorithm. During the Hammurabi dynasty c. 1800 – c. 1600 BC, Babylonian clay tablets described algorithms for computing formulas. Algorithms were also used in Babylonian astronomy. Babylonian clay tablets describe and employ algorithmic procedures to compute the time and place of significant astronomical events. Algorithms for arithmetic are also found in ancient Egyptian mathematics, dating back to the Rhind Mathematical Papyrus c. 1550 BC. Algorithms were later used in ancient Hellenistic mathematics. Two examples are the Sieve of Eratosthenes, which was described in the Introduction to Arithmetic by Nicomachus, and the Euclidean algorithm, which was first described in Euclid's Elements (c. 300 BC).Examples of ancient Indian mathematics included the Shulba Sutras, the Kerala School, and the Brāhmasphuṭasiddhānta. In the 9th century, Muḥammad ibn Mūsā al-Khwārizmī revolutionized the field by establishing the algorithm as a systematic, finite sequence of logical steps to solve mathematical problems. In his influential work, The Compendious Book on Calculation by Completion and Balancing, he moved beyond specific numerical solutions to introduce general procedures for algebraic reduction and balancing. This transformed mathematics into a 'mechanical' process of well-defined rules—a fundamental shift that laid the groundwork for modern algorithmic theory. The Latin translation of his arithmetic treatise, titled Algoritmi de numero Indorum, led to the term algorithm being derived from the Latinization of his name, Algoritmi, specifically to describe this new rule-based approach to mathematics. The first cryptographic algorithm for deciphering encrypted code was developed by Al-Kindi, a 9th-century Arab mathematician, in A Manuscript On Deciphering Cryptographic Messages. He gave the first description of cryptanalysis by frequency analysis, the earliest codebreaking algorithm. === Computers === ==== Weight-driven clocks ==== Weight-driven clocks were a key European invention in Middle Ages, specifically the verge escapement mechanism producing the tick of mechanical clocks. Accurate automatic machines led to mechanical automata in the 13th century and computational machines—the difference and analytical engines of Charles Babbage and Ada Lovelace in the mid-19th century. Lovelace designed the first algorithm intended for a computer, Babbage's analytical engine, the first real Turing-complete computer, more than the mechanical calculators of the time. Although the full implementation of Babbage's second device was only built decades after her lifetime, Lovelace has been called "history's first programmer". ==== Electromechanical relay ==== The Jacquard loom, a precursor to punch cards, and telephone switching machines led to the development of the first computers. By the mid-19th century, the telegraph, was in use throughout the world. By the late 19th century, ticker tape (c. 1870s) and punch cards (c. 1890) were developed. Then came the teleprinter (c. 1910) with its punched-paper use of Baudot code on tape. Telephone-switching networks of electromechanical relays were invented in 1835. These led to the invention of the digital adding device by George Stibitz in 1937. While working in Bell Laboratories, he observed the "burdensome" use of mechanical calculators with gears, prompting him to experiment create an experimental digital adder at home. === Formalization === In 1928, a partial formalization of the modern concept of algorithms began with attempts to solve David Hilbert's Entscheidungsproblem (decision problem). Later formalizations were framed as attempts to define "effective calculability" or "effective method". Those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's Formulation 1 of 1936, and Alan Turing's Turing machines of 1936–37 and 1939. === Modern Algorithms === For decades, it was assumed that algorithm evolution progresses from heuristics to formal algorithms. A Symbolic integration provides a classic illustration. In 1961, James Slagle’s program SAINT used heuristics to solve 52 of 54 freshman calculus exercises from an MIT textbook (≈96%). In 1967, Larry Moses’s SIN refined the heuristics and achieved 100% success, though it remained heuristic. Finally, in 1969, Robert Risch introduced the Risch Algorithm with formal guarantees. This trajectory defined the traditional path: heuristics evolving until a definitive, guaranteed algorithm emerged. However, the rise of transformer-based AI has inverted this sequence — classical algorithms are now being displaced by heuristics once again. Algorithms have evolved and improved in many ways as time goes on. Common uses of algorithms today include social media apps like Instagram and YouTube. Algorithms are used as a way to analyze what people like and push more of those things to the people who interact with them. Quantum computing uses quantum algorithm procedures to solve problems faster. More recently, in 2024, NIST updated their post-quantum encryption standards, which includes new encryption algorithms to enhance defenses against attacks using quantum computing. == Representations == Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, drakon-charts, programming languages or control tables. Natural language expressions of algorithms tend to be verbose and ambiguous and are rarely used for complex or technical algor

System Service Descriptor Table

The System Service Descriptor Table (SSDT) is an internal dispatch table within Microsoft Windows. == Function == The SSDT maps syscalls to kernel function addresses. When a syscall is issued by a user space application, it contains the service index as parameter to indicate which syscall is called. The SSDT is then used to resolve the address of the corresponding function within ntoskrnl.exe. In modern Windows kernels, two SSDTs are used: One for generic routines (KeServiceDescriptorTable) and a second (KeServiceDescriptorTableShadow) for graphical routines. A parameter passed by the calling userspace application determines which SSDT shall be used. == Hooking == Modification of the SSDT allows to redirect syscalls to routines outside the kernel. These routines can be either used to hide the presence of software or to act as a backdoor to allow attackers permanent code execution with kernel privileges. For both reasons, hooking SSDT calls is often used as a technique in both Windows kernel mode rootkits and antivirus software. In 2010, many computer security products which relied on hooking SSDT calls were shown to be vulnerable to exploits using race conditions to attack the products' security checks.

Weak stability boundary

Weak stability boundary (WSB), including low-energy transfer, is a concept introduced by Edward Belbruno in 1987. The concept explained how a spacecraft could change orbits using very little fuel. Weak stability boundary is defined for the three-body problem. This problem considers the motion of a particle P of negligible mass moving with respect to two larger bodies, P1, P2, modeled as point masses, where these bodies move in circular or elliptical orbits with respect to each other, and P2 is smaller than P1. The force between the three bodies is the classical Newtonian gravitational force. For example, P1 is the Earth, P2 is the Moon and P is a spacecraft; or P1 is the Sun, P2 is Jupiter and P is a comet, etc. This model is called the restricted three-body problem. The weak stability boundary defines a region about P2 where P is temporarily captured. This region is in position-velocity space. Capture means that the Kepler energy between P and P2 is negative. This is also called weak capture. == Background == This boundary was defined for the first time by Edward Belbruno of Princeton University in 1987. He described a Low-energy transfer which would allow a spacecraft to change orbits using very little fuel. It was for motion about Moon (P2) with P1 = Earth. It is defined algorithmically by monitoring cycling motion of P about the Moon and finding the region where cycling motion transitions between stable and unstable after one cycle. Stable motion means P can completely cycle about the Moon for one cycle relative to a reference section, starting in weak capture. P needs to return to the reference section with negative Kepler energy. Otherwise, the motion is called unstable, where P does not return to the reference section within one cycle or if it returns, it has non-negative Kepler energy. The set of all transition points about the Moon comprises the weak stability boundary, W. The motion of P is sensitive or chaotic as it moves about the Moon within W. A mathematical proof that the motion within W is chaotic was given in 2004. This is accomplished by showing that the set W about an arbitrary body P2 in the restricted three-body problem contains a hyperbolic invariant set of fractional dimension consisting of the infinitely many intersections Hyperbolic manifolds. The weak stability boundary was originally referred to as the fuzzy boundary. This term was used since the transition between capture and escape defined in the algorithm is not well defined and limited by the numerical accuracy. This defines a "fuzzy" location for the transition points. It is also due the inherent chaos in the motion of P near the transition points. It can be thought of as a fuzzy chaos region. As is described in an article in Discover magazine, the WSB can be roughly viewed as the fuzzy edge of a region, referred to as a gravity well, about a body (the Moon), where its force of gravity becomes small enough to be dominated by force of gravity of another body (the Earth) and the motion there is chaotic. A much more general algorithm defining W was given in 2007. It defines W relative to n-cycles, where n = 1,2,3,..., yielding boundaries of order n. This gives a much more complex region consisting of the union of all the weak stability boundaries of order n. This definition was explored further in 2010. The results suggested that W consists, in part, of the hyperbolic network of invariant manifolds associated to the Lyapunov orbits about the L1, L2 Lagrange points near P2. The explicit determination of the set W about P2 = Jupiter, where P1 is the Sun, is described in "Computation of Weak Stability Boundaries: Sun-Jupiter Case". It turns out that a weak stability region can also be defined relative to the larger mass point, P1. A proof of the existence of the weak stability boundary about P1 was given in 2012, but a different definition is used. The chaos of the motion is analytically proven in "Geometry of Weak Stability Boundaries". The boundary is studied in "Applicability and Dynamical Characterization of the Associated Sets of the Algorithmic Weak Stability Boundary in the Lunar Sphere of Influence". == Applications == There are a number of important applications for the weak stability boundary (WSB). Since the WSB defines a region of temporary capture, it can be used, for example, to find transfer trajectories from the Earth to the Moon that arrive at the Moon within the WSB region in weak capture, which is called ballistic capture for a spacecraft. No fuel is required for capture in this case. This was numerically demonstrated in 1987. This is the first reference for ballistic capture for spacecraft and definition of the weak stability boundary. The boundary was operationally demonstrated to exist in 1991 when it was used to find a ballistic capture transfer to the Moon for Japan's Hiten spacecraft. Other missions have used the same transfer type as Hiten, including Grail, Capstone, Danuri, Hakuto-R Mission 1 and SLIM. The WSB for Mars is studied in "Earth-Mars Transfers with Ballistic Capture" and ballistic capture transfers to Mars are computed. The BepiColombo mission of ESA should achieve ballistic capture at the WSB of Mercury in November 2026. The WSB region can be used in the field of Astrophysics. It can be defined for stars within open star clusters. This is done in "Chaotic Exchange of Solid Material Between Planetary Systems: Implications for the Lithopanspermia Hypothesis" to analyze the capture of solid material that may have arrived on the Earth early in the age of the Solar System to study the validity of the lithopanspermia hypothesis. Numerical explorations of trajectories for P starting in the WSB region about P2 show that after the particle P escapes P2 at the end of weak capture, it moves about the primary body, P1, in a near resonant orbit, in resonance with P2 about P1. This property was used to study comets that move in orbits about the Sun in orbital resonance with Jupiter, which change resonance orbits by becoming weakly captured by Jupiter. An example of such a comet is 39P/Oterma. This property of change of resonance of orbits about P1 when P is weakly captured by the WSB of P2 has an interesting application to the field of quantum mechanics to the motion of an electron about the proton in a hydrogen atom. The transition motion of an electron about the proton between different energy states described by the Schrödinger equation is shown to be equivalent to the change of resonance of P about P1 via weak capture by P2 for a family of transitioning resonance orbits. This gives a classical model using chaotic dynamics with Newtonian gravity for the motion of an electron.