text:
# The New AI: General & Sound & Relevant for Physics Technical Report IDSIA-04-03, Version 2.0, Nov 2003 (based on Version 1.0 [57], Feb 2003). To appear in B. Goertzel and C. Pennachin, eds.: , Artificial General Intelligence (accepted 2002)

## 1 Introduction

Remarkably, there is a theoretically optimal way of making predictions based on observations, rooted in the early work of Solomonoff and Kolmogorov . The approach reflects basic principles of Occam’s razor: simple explanations of data are preferable to complex ones.

The theory of universal inductive inference quantifies what simplicity really means. Given certain very broad computability assumptions, it provides techniques for making optimally reliable statements about future events, given the past.

Once there is an optimal, formally describable way of predicting the future, we should be able to construct a machine that continually computes and executes action sequences that maximize expected or predicted reward, thus solving an ancient goal of AI research.

For many decades, however, AI researchers have not paid a lot of attention to the theory of inductive inference. Why not? There is another reason besides the fact that most of them have traditionally ignored theoretical computer science: the theory has been perceived as being associated with excessive computational costs. In fact, its most general statements refer to methods that are optimal (in a certain asymptotic sense) but incomputable. So researchers in machine learning and artificial intelligence have often resorted to alternative methods that lack a strong theoretical foundation but at least seem feasible in certain limited contexts. For example, since the early attempts at building a “General Problem Solver”  much work has been done to develop mostly heuristic machine learning algorithms that solve new problems based on experience with previous problems. Many pointers to learning by chunking, learning by macros, hierarchical learning, learning by analogy, etc. can be found in Mitchell’s book  and Kaelbling’s survey .

Recent years, however, have brought substantial progress in the field of computable and feasible variants of optimal algorithms for prediction, search, inductive inference, problem solving, decision making, and reinforcement learning in very general environments. In what follows I will focus on the results obtained at IDSIA.

Sections 3, 4, 7 relate Occam’s razor and the notion of simplicity to the shortest algorithms for computing computable objects, and will concentrate on recent asymptotic optimality results for universal learning machines, essentially ignoring issues of practical feasibility—compare Hutter’s contribution  in this volume.

Section 5, however, will focus on our recent non-traditional simplicity measure which is not based on the shortest but on the fastest way of describing objects, and Section 6 will use this measure to derive non-traditional predictions concerning the future of our universe.

Sections 8, 9, 10 will finally address quite pragmatic issues and “true” time-optimality: given a problem and only so much limited computation time, what is the best way of spending it on evaluating solution candidates? In particular, Section 9 will outline a bias-optimal way of incrementally solving each task in a sequence of tasks with quickly verifiable solutions, given a probability distribution (the bias) on programs computing solution candidates. Bias shifts are computed by program prefixes that modify the distribution on their suffixes by reusing successful code for previous tasks (stored in non-modifiable memory). No tested program gets more runtime than its probability times the total search time. In illustrative experiments, ours becomes the first general system to learn a universal solver for arbitrary $`n`$ disk Towers of Hanoi tasks (minimal solution size $`2^n1`$). It demonstrates the advantages of incremental learning by profiting from previously solved, simpler tasks involving samples of a simple context free language. Sections 10 discusses how to use this approach for building general reinforcement learners.

Finally, Section 11 will summarize the recent Gödel machine , a self-referential, theoretically optimal self-improver which explicitly addresses the ‘Grand Problem of Artificial Intelligence’  by optimally dealing with limited resources in general reinforcement learning settings.

## 2 More Formally

What is the optimal way of predicting the future, given the past? Which is the best way to act such as to maximize one’s future expected reward? Which is the best way of searching for the solution to a novel problem, making optimal use of solutions to earlier problems?

Most previous work on these old and fundamental questions has focused on very limited settings, such as Markovian environments where the optimal next action, given past inputs, depends on the current input only .

We will concentrate on a much weaker and therefore much more general assumption, namely, that the environment’s responses are sampled from a computable probability distribution. If even this weak assumption were not true then we could not even formally specify the environment, leave alone writing reasonable scientific papers about it.

Let us first introduce some notation. $`B^{}`$ denotes the set of finite sequences over the binary alphabet $`B=\{0,1\}`$, $`B^{\mathrm{}}`$ the set of infinite sequences over $`B`$, $`\lambda `$ the empty string, $`B^{\mathrm{}}=B^{}B^{\mathrm{}}`$. $`x,y,z,z^1,z^2`$ stand for strings in $`B^{\mathrm{}}`$. If $`xB^{}`$ then $`xy`$ is the concatenation of $`x`$ and $`y`$ (e.g., if $`x=10000`$ and $`y=1111`$ then $`xy=100001111`$). For $`xB^{}`$, $`l(x)`$ denotes the number of bits in $`x`$, where $`l(x)=\mathrm{}`$ for $`xB^{\mathrm{}}`$; $`l(\lambda )=0`$. $`x_n`$ is the prefix of $`x`$ consisting of the first $`n`$ bits, if $`l(x)n`$, and $`x`$ otherwise ($`x_0:=\lambda `$). $`\mathrm{log}`$ denotes the logarithm with basis 2, $`f,g`$ denote functions mapping integers to integers. We write $`f(n)=O(g(n))`$ if there exist positive constants $`c,n_0`$ such that $`f(n)cg(n)`$ for all $`n>n_0`$. For simplicity let us consider universal Turing Machines  (TMs) with input alphabet $`B`$ and trinary output alphabet including the symbols “0”, “1”, and “ ” (blank). For efficiency reasons, the TMs should have several work tapes to avoid potential quadratic slowdowns associated with 1-tape TMs. The remainder of this paper assumes a fixed universal reference TM.

Now suppose bitstring $`x`$ represents the data observed so far. What is its most likely continuation $`yB^{\mathrm{}}`$? Bayes’ theorem yields

$$P(xyx)=\frac{P(xxy)P(xy)}{P(x)}P(xy)$$
(1)
where $`P(z^2z^1)`$ is the probability of $`z^2`$, given knowledge of $`z^1`$, and $`P(x)=_{zB^{\mathrm{}}}P(xz)𝑑z`$ is just a normalizing factor. So the most likely continuation $`y`$ is determined by $`P(xy)`$, the prior probability of $`xy`$. But which prior measure $`P`$ is plausible? Occam’s razor suggests that the “simplest” $`y`$ should be more probable. But which exactly is the “correct” definition of simplicity? Sections 3 and 4 will measure the simplicity of a description by its length. Section 5 will measure the simplicity of a description by the time required to compute the described object.

## 3 Prediction Using a Universal Algorithmic Prior Based on the Shortest Way of Describing Objects

Roughly fourty years ago Solomonoff started the theory of universal optimal induction based on the apparently harmless simplicity assumption that $`P`$ is computable . While Equation (1) makes predictions of the entire future, given the past, Solomonoff  focuses just on the next bit in a sequence. Although this provokes surprisingly nontrivial problems associated with translating the bitwise approach to alphabets other than the binary one — this was achieved only recently  — it is sufficient for obtaining essential insights. Given an observed bitstring $`x`$, Solomonoff assumes the data are drawn according to a recursive measure $`\mu `$; that is, there is a program for a universal Turing machine that reads $`xB^{}`$ and computes $`\mu (x)`$ and halts. He estimates the probability of the next bit (assuming there will be one), using the remarkable, well-studied, enumerable prior $`M`$

$$M(x)=\underset{\genfrac{}{}{0pt}{}{programprefixpcomputes}{outputstartingwithx}}{}2^{l(p)}.$$
(2)
$`M`$ is universal, dominating the less general recursive measures as follows: For all $`xB^{}`$,

$$M(x)c_\mu \mu (x)$$
(3)
where $`c_\mu `$ is a constant depending on $`\mu `$ but not on $`x`$. Solomonoff observed that the conditional $`M`$-probability of a particular continuation, given previous observations, converges towards the unknown conditional $`\mu `$ as the observation size goes to infinity , and that the sum over all observation sizes of the corresponding $`\mu `$-expected deviations is actually bounded by a constant. Hutter (on the author’s SNF research grant “”Unification of Universal Induction and Sequential Decision Theory”) recently showed that the number of prediction errors made by universal Solomonoff prediction is essentially bounded by the number of errors made by any other predictor, including the optimal scheme based on the true $`\mu `$ .

Recent Loss Bounds for Universal Prediction. A more general recent result is this. Assume we do know that $`p`$ is in some set $`P`$ of distributions. Choose a fixed weight $`w_q`$ for each $`q`$ in $`P`$ such that the $`w_q`$ add up to 1 (for simplicity, let $`P`$ be countable). Then construct the Bayesmix $`M(x)=_qw_qq(x)`$, and predict using $`M`$ instead of the optimal but unknown $`p`$. How wrong is it to do that? The recent work of Hutter provides general and sharp (!) loss bounds :

Let $`LM(n)`$ and $`Lp(n)`$ be the total expected unit losses of the $`M`$-predictor and the p-predictor, respectively, for the first $`n`$ events. Then $`LM(n)Lp(n)`$ is at most of the order of $`\sqrt{Lp(n)}`$. That is, $`M`$ is not much worse than $`p`$. And in general, no other predictor can do better than that! In particular, if $`p`$ is deterministic, then the $`M`$-predictor soon won’t make any errors any more.

If $`P`$ contains all recursively computable distributions, then $`M`$ becomes the celebrated enumerable universal prior. That is, after decades of somewhat stagnating research we now have sharp loss bounds for Solomonoff’s universal induction scheme (compare recent work of Merhav and Feder ).

Solomonoff’s approach, however, is uncomputable. To obtain a feasible approach, reduce M to what you get if you, say, just add up weighted estimated future finance data probabilities generated by 1000 commercial stock-market prediction software packages. If only one of the probability distributions happens to be close to the true one (but you do not know which) you still should get rich.

Note that the approach is much more general than what is normally done in traditional statistical learning theory, e.g., , where the often quite unrealistic assumption is that the observations are statistically independent.

## 4 Super Omegas and Generalizations of Kolmogorov Complexity & Algorithmic Probability

Our recent research generalized Solomonoff’s approach to the case of less restrictive nonenumerable universal priors that are still computable in the limit .

An object $`X`$ is formally describable if a finite amount of information completely describes $`X`$ and only $`X`$. More to the point, $`X`$ should be representable by a possibly infinite bitstring $`x`$ such that there is a finite, possibly never halting program $`p`$ that computes $`x`$ and nothing but $`x`$ in a way that modifies each output bit at most finitely many times; that is, each finite beginning of $`x`$ eventually converges and ceases to change. This constructive notion of formal describability is less restrictive than the traditional notion of computability , mainly because we do not insist on the existence of a halting program that computes an upper bound of the convergence time of $`p`$’s $`n`$-th output bit. Formal describability thus pushes constructivism  to the extreme, barely avoiding the nonconstructivism embodied by even less restrictive concepts of describability (compare computability in the limit  and $`\mathrm{\Delta }_n^0`$-describability \[31, p. 46-47\]).

The traditional theory of inductive inference focuses on Turing machines with one-way write-only output tape. This leads to the universal enumerable Solomonoff-Levin (semi) measure. We introduced more general, nonenumerable, but still limit-computable measures and a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity , suggesting that the “true” information content of some (possibly infinite) bitstring $`x`$ actually is the size of the shortest nonhalting program that converges to $`x`$ and nothing but $`x`$ on a Turing machine that can edit its previous outputs. In fact, this “true” content is often smaller than the traditional Kolmogorov complexity. We showed that there are Super Omegas computable in the limit yet more random than Chaitin’s “number of wisdom” Omega  (which is maximally random in a weaker traditional sense), and that any approximable measure of $`x`$ is small for any $`x`$ lacking a short description.

We also showed that there is a universal cumulatively enumerable measure of $`x`$ based on the measure of all enumerable $`y`$ lexicographically greater than $`x`$. It is more dominant yet just as limit-computable as Solomonoff’s . That is, if we are interested in limit-computable universal measures, we should prefer the novel universal cumulatively enumerable measure over the traditional enumerable one. If we include in our Bayesmix such limit-computable distributions we obtain again sharp loss bounds for prediction based on the mix .

Our approach highlights differences between countable and uncountable sets. Which are the potential consequences for physics? We argue that things such as uncountable time and space and incomputable probabilities actually should not play a role in explaining the world, for lack of evidence that they are really necessary . Some may feel tempted to counter this line of reasoning by pointing out that for centuries physicists have calculated with continua of real numbers, most of them incomputable. Even quantum physicists who are ready to give up the assumption of a continuous universe usually do take for granted the existence of continuous probability distributions on their discrete universes, and Stephen Hawking explicitly said: “Although there have been suggestions that space-time may have a discrete structure I see no reason to abandon the continuum theories that have been so successful.” Note, however, that all physicists in fact have only manipulated discrete symbols, thus generating finite, describable proofs of their results derived from enumerable axioms. That real numbers really exist in a way transcending the finite symbol strings used by everybody may be a figment of imagination — compare Brouwer’s constructive mathematics  and the Löwenheim-Skolem Theorem  which implies that any first order theory with an uncountable model such as the real numbers also has a countable model. As Kronecker put it: “Die ganze Zahl schuf der liebe Gott, alles Übrige ist Menschenwerk” (“God created the integers, all else is the work of man” ). Kronecker greeted with scepticism Cantor’s celebrated insight  about real numbers, mathematical objects Kronecker believed did not even exist.

Assuming our future lies among the few (countably many) describable futures, we can ignore uncountably many nondescribable ones, in particular, the random ones. Adding the relatively mild assumption that the probability distribution from which our universe is drawn is cumulatively enumerable provides a theoretical justification of the prediction that the most likely continuations of our universes are computable through short enumeration procedures. In this sense Occam’s razor is just a natural by-product of a computability assumption! But what about falsifiability? The pseudorandomness of our universe might be effectively undetectable in principle, because some approximable and enumerable patterns cannot be proven to be nonrandom in recursively bounded time.

The next sections, however, will introduce additional plausible assumptions that do lead to computable optimal prediction procedures.

## 5 Computable Predictions through the Speed Prior Based on the Fastest Way of Describing Objects

Unfortunately, while $`M`$ and the more general priors of Section 4 are computable in the limit, they are not recursive, and thus practically infeasible. This drawback inspired less general yet practically more feasible principles of minimum description length (MDL)  as well as priors derived from time-bounded restrictions  of Kolmogorov complexity . No particular instance of these approaches, however, is universally accepted or has a general convincing motivation that carries beyond rather specialized application scenarios. For instance, typical efficient MDL approaches require the specification of a class of computable models of the data, say, certain types of neural networks, plus some computable loss function expressing the coding costs of the data relative to the model. This provokes numerous ad-hoc choices.

Our recent work , however, offers an alternative to the celebrated but noncomputable algorithmic simplicity measure or Solomonoff-Levin measure discussed above . We introduced a new measure (a prior on the computable objects) which is not based on the shortest but on the fastest way of describing objects.

Let us assume that the observed data sequence is generated by a computational process, and that any possible sequence of observations is therefore computable in the limit . This assumption is stronger and more radical than the traditional one: Solomonoff just insists that the probability of any sequence prefix is recursively computable, but the (infinite) sequence itself may still be generated probabilistically.

Given our starting assumption that data are deterministically generated by a machine, it seems plausible that the machine suffers from a computational resource problem. Since some things are much harder to compute than others, the resource-oriented point of view suggests the following postulate.

###### Postulate 1

The cumulative prior probability measure of all $`x`$ incomputable within time $`t`$ by any method is at most inversely proportional to $`t`$.

This postulate leads to the Speed Prior $`S(x)`$, the probability that the output of the following probabilistic algorithm starts with $`x`$ :

> Initialize: Set $`t:=1.`$ Let the input scanning head of a universal TM point to the first cell of its initially empty input tape.
>
> Forever repeat: While the number of instructions executed so far exceeds $`t`$: toss an unbiased coin; if heads is up set $`t:=2t`$; otherwise exit. If the input scanning head points to a cell that already contains a bit, execute the corresponding instruction (of the growing self-delimiting program, e.g., ). Else toss the coin again, set the cell’s bit to 1 if heads is up (0 otherwise), and set $`t:=t/2.`$

Algorithm GUESS is very similar to a probabilistic search algorithm used in previous work on applied inductive inference . On several toy problems it generalized extremely well in a way unmatchable by traditional neural network learning algorithms.

With $`S`$ comes a computable method AS for predicting optimally within $`ϵ`$ accuracy . Consider a finite but unknown program $`p`$ computing $`yB^{\mathrm{}}`$. What if Postulate 1 holds but $`p`$ is not optimally efficient, and/or computed on a computer that differs from our reference machine? Then we effectively do not sample beginnings $`y_k`$ from $`S`$ but from an alternative semimeasure $`S^{}`$. Can we still predict well? Yes, because the Speed Prior $`S`$ dominates $`S^{}`$. This dominance is all we need to apply the recent loss bounds . The loss that we are expected to receive by predicting according to AS instead of using the true but unknown $`S^{}`$ does not exceed the optimal loss by much .

## 6 Speed Prior-Based Predictions for Our Universe

“In the beginning was the code.”

First sentence of the Great Programmer’s Bible

Physicists and economists and other inductive scientists make predictions based on observations. Astonishingly, however, few physicists are aware of the theory of optimal inductive inference . In fact, when talking about the very nature of their inductive business, many physicists cite rather vague concepts such as Popper’s falsifiability , instead of referring to quantitative results.

All widely accepted physical theories, however, are accepted not because they are falsifiable—they are not—or because they match the data—many alternative theories also match the data—but because they are simple in a certain sense. For example, the theory of gravitation is induced from locally observable training examples such as falling apples and movements of distant light sources, presumably stars. The theory predicts that apples on distant planets in other galaxies will fall as well. Currently nobody is able to verify or falsify this. But everybody believes in it because this generalization step makes the theory simpler than alternative theories with separate laws for apples on other planets. The same holds for superstring theory  or Everett’s many world theory , which presently also are neither verifiable nor falsifiable, yet offer comparatively simple explanations of numerous observations. In particular, most of Everett’s postulated many worlds will remain unobservable forever, but the assumption of their existence simplifies the theory, thus making it more beautiful and acceptable.

In Sections 3 and 4 we have made the assumption that the probabilities of next events, given previous events, are (limit-)computable. Here we make a stronger assumption by adopting Zuse’s thesis , namely, that the very universe is actually being computed deterministically, e.g., on a cellular automaton (CA) . Quantum physics, quantum computation , Heisenberg’s uncertainty principle and Bell’s inequality  do not imply any physical evidence against this possibility, e.g., .

But then which is our universe’s precise algorithm? The following method  does compute it:

> Systematically create and execute all programs for a universal computer, such as a Turing machine or a CA; the first program is run for one instruction every second step on average, the next for one instruction every second of the remaining steps on average, and so on.

This method in a certain sense implements the simplest theory of everything: all computable universes, including ours and ourselves as observers, are computed by the very short program that generates and executes all possible programs . In nested fashion, some of these programs will execute processes that again compute all possible universes, etc. . Of course, observers in “higher-level” universes may be completely unaware of observers or universes computed by nested processes, and vice versa. For example, it seems hard to track and interpret the computations performed by a cup of tea.

The simple method above is more efficient than it may seem at first glance. A bit of thought shows that it even has the optimal order of complexity. For example, it outputs our universe history as quickly as this history’s fastest program, save for a (possibly huge) constant slowdown factor that does not depend on output size.

Nevertheless, some universes are fundamentally harder to compute than others. This is reflected by the Speed Prior $`S`$ discussed above (Section 5). So let us assume that our universe’s history is sampled from $`S`$ or a less dominant prior reflecting suboptimal computation of the history. Now we can immediately predict:

1. Our universe will not get many times older than it is now  — essentially, the probability that it will last $`2^n`$ times longer than it has lasted so far is at most $`2^n`$.

2. Any apparent randomness in any physical observation must be due to some yet unknown but fast pseudo-random generator PRG  which we should try to discover. 2a. A re-examination of beta decay patterns may reveal that a very simple, fast, but maybe not quite trivial PRG is responsible for the apparently random decays of neutrons into protons, electrons and antineutrinos. 2b. Whenever there are several possible continuations of our universe corresponding to different Schrödinger wave function collapses — compare Everett’s widely accepted many worlds hypothesis  — we should be more likely to end up in one computable by a short and fast algorithm. A re-examination of split experiment data involving entangled states such as the observations of spins of initially close but soon distant particles with correlated spins might reveal unexpected, nonobvious, nonlocal algorithmic regularity due to a fast PRG.

3. Large scale quantum computation  will not work well, essentially because it would require too many exponentially growing computational resources in interfering “parallel universes” .

4. Any probabilistic algorithm depending on truly random inputs from the environment will not scale well in practice.

Prediction 2 is verifiable but not necessarily falsifiable within a fixed time interval given in advance. Still, perhaps the main reason for the current absence of empirical evidence in this vein is that few  have looked for it.

In recent decades several well-known physicists have started writing about topics of computer science, e.g., , sometimes suggesting that real world physics might allow for computing things that are not computable traditionally. Unimpressed by this trend, computer scientists have argued in favor of the opposite: since there is no evidence that we need more than traditional computability to explain the world, we should try to make do without this assumption, e.g., .

## 7 Optimal Rational Decision Makers

So far we have talked about passive prediction, given the observations. Note, however, that agents interacting with an environment can also use predictions of the future to compute action sequences that maximize expected future reward. Hutter’s recent AIXI model  (author’s SNF grant 61847) does exactly this, by combining Solomonoff’s $`M`$-based universal prediction scheme with an expectimax computation.

In cycle $`t`$ action $`y_t`$ results in perception $`x_t`$ and reward $`r_t`$, where all quantities may depend on the complete history. The perception $`x_t^{}`$ and reward $`r_t`$ are sampled from the (reactive) environmental probability distribution $`\mu `$. Sequential decision theory shows how to maximize the total expected reward, called value, if $`\mu `$ is known. Reinforcement learning  is used if $`\mu `$ is unknown. AIXI defines a mixture distribution $`\xi `$ as a weighted sum of distributions $`\nu `$, where $``$ is any class of distributions including the true environment $`\mu `$.

It can be shown that the conditional $`M`$ probability of environmental inputs to an AIXI agent, given the agent’s earlier inputs and actions, converges with increasing length of interaction against the true, unknown probability , as long as the latter is recursively computable, analogously to the passive prediction case.

Recent work  also demonstrated AIXI’s optimality in the following sense. The Bayes-optimal policy $`p^\xi `$ based on the mixture $`\xi `$ is self-optimizing in the sense that the average value converges asymptotically for all $`\mu `$ to the optimal value achieved by the (infeasible) Bayes-optimal policy $`p^\mu `$ which knows $`\mu `$ in advance. The necessary condition that $``$ admits self-optimizing policies is also sufficient. No other structural assumptions are made on $``$. Furthermore, $`p^\xi `$ is Pareto-optimal in the sense that there is no other policy yielding higher or equal value in all environments $`\nu `$ and a strictly higher value in at least one .

We can modify the AIXI model such that its predictions are based on the $`ϵ`$-approximable Speed Prior $`S`$ instead of the incomputable $`M`$. Thus we obtain the so-called AIS model. Using Hutter’s approach  we can now show that the conditional $`S`$ probability of environmental inputs to an AIS agent, given the earlier inputs and actions, converges to the true but unknown probability, as long as the latter is dominated by $`S`$, such as the $`S^{}`$ above.

## 8 Optimal Universal Search Algorithms

In a sense, searching is less general than reinforcement learning because it does not necessarily involve predictions of unseen data. Still, search is a central aspect of computer science (and any reinforcement learner needs a searcher as a submodule—see Sections 10 and 11). Surprisingly, however, many books on search algorithms do not even mention the following, very simple asymptotically optimal, “universal” algorithm for a broad class of search problems.

Define a probability distribution $`P`$ on a finite or infinite set of programs for a given computer. $`P`$ represents the searcher’s initial bias (e.g., $`P`$ could be based on program length, or on a probabilistic syntax diagram).

> Method Lsearch: Set current time limit T=1. While problem not solved do:
>
> > Test all programs $`q`$ such that $`t(q)`$, the maximal time spent on creating and running and testing $`q`$, satisfies $`t(q)<P(q)T`$. Set $`T:=2T.`$

Lsearch (for Levin Search) may be the algorithm Levin was referring to in his 2 page paper  which states that there is an asymptotically optimal universal search method for problems with easily verifiable solutions, that is, solutions whose validity can be quickly tested. Given some problem class, if some unknown optimal program $`p`$ requires $`f(k)`$ steps to solve a problem instance of size $`k`$, then Lsearch will need at most $`O(f(k)/P(p))=O(f(k))`$ steps — the constant factor $`1/P(p)`$ may be huge but does not depend on $`k`$. Compare \[31, p. 502-505\] and  and the fastest way of computing all computable universes in Section 6.

Recently Hutter developed a more complex asymptotically optimal search algorithm for all well-defined problems, not just those with with easily verifiable solutions . Hsearch cleverly allocates part of the total search time for searching the space of proofs to find provably correct candidate programs with provable upper runtime bounds, and at any given time focuses resources on those programs with the currently best proven time bounds. Unexpectedly, Hsearch manages to reduce the unknown constant slowdown factor of Lsearch to a value of $`1+ϵ`$, where $`ϵ`$ is an arbitrary positive constant.

Unfortunately, however, the search in proof space introduces an unknown additive problem class-specific constant slowdown, which again may be huge. While additive constants generally are preferrable over multiplicative ones, both types may make universal search methods practically infeasible.

Hsearch and Lsearch are nonincremental in the sense that they do not attempt to minimize their constants by exploiting experience collected in previous searches. Our method Adaptive Lsearch or Als tries to overcome this  — compare Solomonoff’s related ideas . Essentially it works as follows: whenever Lsearch finds a program $`q`$ that computes a solution for the current problem, $`q`$’s probability $`P(q)`$ is substantially increased using a “learning rate,” while probabilities of alternative programs decrease appropriately. Subsequent Lsearches for new problems then use the adjusted $`P`$, etc. A nonuniversal variant of this approach was able to solve reinforcement learning (RL) tasks  in partially observable environments unsolvable by traditional RL algorithms .

Each Lsearch invoked by Als is optimal with respect to the most recent adjustment of $`P`$. On the other hand, the modifications of $`P`$ themselves are not necessarily optimal. Recent work discussed in the next section overcomes this drawback in a principled way.

## 9 Optimal Ordered Problem Solver (OOPS)

Our recent Oops  is a simple, general, theoretically sound, in a certain sense time-optimal way of searching for a universal behavior or program that solves each problem in a sequence of computational problems, continually organizing and managing and reusing earlier acquired knowledge. For example, the $`n`$-th problem may be to compute the $`n`$-th event from previous events (prediction), or to find a faster way through a maze than the one found during the search for a solution to the $`n1`$-th problem (optimization).

Let us first introduce the important concept of bias-optimality, which is a pragmatic definition of time-optimality, as opposed to the asymptotic optimality of both Lsearch and Hsearch, which may be viewed as academic exercises demonstrating that the $`O()`$ notation can sometimes be practically irrelevant despite its wide use in theoretical computer science. Unlike asymptotic optimality, bias-optimality does not ignore huge constant slowdowns:

###### Definition 1 (Bias-Optimal Searchers)

Given is a problem class $``$, a search space $`𝒞`$ of solution candidates (where any problem $`r`$ should have a solution in $`𝒞`$), a task dependent bias in form of conditional probability distributions $`P(qr)`$ on the candidates $`q𝒞`$, and a predefined procedure that creates and tests any given $`q`$ on any $`r`$ within time $`t(q,r)`$ (typically unknown in advance). A searcher is $`n`$-bias-optimal ($`n1`$) if for any maximal total search time $`T_{max}>0`$ it is guaranteed to solve any problem $`r`$ if it has a solution $`p𝒞`$ satisfying $`t(p,r)P(pr)T_{max}/n`$. It is bias-optimal if $`n=1`$.

This definition makes intuitive sense: the most probable candidates should get the lion’s share of the total search time, in a way that precisely reflects the initial bias. Now we are ready to provide a general overview of the basic ingredients of oops :

Primitives. We start with an initial set of user-defined primitive behaviors. Primitives may be assembler-like instructions or time-consuming software, such as, say, theorem provers, or matrix operators for neural network-like parallel architectures, or trajectory generators for robot simulations, or state update procedures for multiagent systems, etc. Each primitive is represented by a token. It is essential that those primitives whose runtimes are not known in advance can be interrupted at any time.

Task-specific prefix codes. Complex behaviors are represented by token sequences or programs. To solve a given task represented by task-specific program inputs, oops tries to sequentially compose an appropriate complex behavior from primitive ones, always obeying the rules of a given user-defined initial programming language. Programs are grown incrementally, token by token; their beginnings or prefixes are immediately executed while being created; this may modify some task-specific internal state or memory, and may transfer control back to previously selected tokens (e.g., loops). To add a new token to some program prefix, we first have to wait until the execution of the prefix so far explicitly requests such a prolongation, by setting an appropriate signal in the internal state. Prefixes that cease to request any further tokens are called self-delimiting programs or simply programs (programs are their own prefixes). Binary self-delimiting programs were studied by  and  in the context of Turing machines  and the theory of Kolmogorov complexity and algorithmic probability . Oops, however, uses a more practical, not necessarily binary framework.

The program construction procedure above yields task-specific prefix codes on program space: with any given task, programs that halt because they have found a solution or encountered some error cannot request any more tokens. Given the current task-specific inputs, no program can be the prefix of another one. On a different task, however, the same program may continue to request additional tokens. This is important for our novel approach—incrementally growing self-delimiting programs are unnecessary for the asymptotic optimality properties of Lsearch and Hsearch, but essential for oops.

Access to previous solutions. Let $`p^n`$ denote a found prefix solving the first $`n`$ tasks. The search for $`p^{n+1}`$ may greatly profit from the information conveyed by (or the knowledge embodied by) $`p^1,p^2,\mathrm{},p^n`$ which are stored or frozen in special nonmodifiable memory shared by all tasks, such that they are accessible to $`p^{n+1}`$ (this is another difference to nonincremental Lsearch and Hsearch). For example, $`p^{n+1}`$ might execute a token sequence that calls $`p^{n3}`$ as a subprogram, or that copies $`p^{n17}`$ into some internal modifiable task-specific memory, then modifies the copy a bit, then applies the slightly edited copy to the current task. In fact, since the number of frozen programs may grow to a large value, much of the knowledge embodied by $`p^j`$ may be about how to access and edit and use older $`p^i`$ ($`i<j`$).

Bias. The searcher’s initial bias is embodied by initial, user-defined, task dependent probability distributions on the finite or infinite search space of possible program prefixes. In the simplest case we start with a maximum entropy distribution on the tokens, and define prefix probabilities as the products of the probabilities of their tokens. But prefix continuation probabilities may also depend on previous tokens in context sensitive fashion.

Self-computed suffix probabilities. In fact, we permit that any executed prefix assigns a task-dependent, self-computed probability distribution to its own possible continuations. This distribution is encoded and manipulated in task-specific internal memory. So unlike with Als  we do not use a prewired learning scheme to update the probability distribution. Instead we leave such updates to prefixes whose online execution modifies the probabilities of their suffixes. By, say, invoking previously frozen code that redefines the probability distribution on future prefix continuations, the currently tested prefix may completely reshape the most likely paths through the search space of its own continuations, based on experience ignored by nonincremental Lsearch and Hsearch. This may introduce significant problem class-specific knowledge derived from solutions to earlier tasks.

Two searches. Essentially, oops provides equal resources for two near-bias-optimal searches (Def. 1) that run in parallel until $`p^{n+1}`$ is discovered and stored in non-modifiable memory. The first is exhaustive; it systematically tests all possible prefixes on all tasks up to $`n+1`$. Alternative prefixes are tested on all current tasks in parallel while still growing; once a task is solved, we remove it from the current set; prefixes that fail on a single task are discarded. The second search is much more focused; it only searches for prefixes that start with $`p^n`$, and only tests them on task $`n+1`$, which is safe, because we already know that such prefixes solve all tasks up to $`n`$.

Bias-optimal backtracking. Hsearch and Lsearch assume potentially infinite storage. Hence they may largely ignore questions of storage management. In any practical system, however, we have to efficiently reuse limited storage. Therefore, in both searches of oops, alternative prefix continuations are evaluated by a novel, practical, token-oriented backtracking procedure that can deal with several tasks in parallel, given some code bias in the form of previously found code. The procedure always ensures near-bias-optimality (Def. 1): no candidate behavior gets more time than it deserves, given the probabilistic bias. Essentially we conduct a depth-first search in program space, where the branches of the search tree are program prefixes, and backtracking (partial resets of partially solved task sets and modifications of internal states and continuation probabilities) is triggered once the sum of the runtimes of the current prefix on all current tasks exceeds the prefix probability multiplied by the total search time so far.

In case of unknown, infinite task sequences we can typically never know whether we already have found an optimal solver for all tasks in the sequence. But once we unwittingly do find one, at most half of the total future run time will be wasted on searching for alternatives. Given the initial bias and subsequent bias shifts due to $`p^1,p^2,\mathrm{},`$ no other bias-optimal searcher can expect to solve the $`n+1`$-th task set substantially faster than oops. A by-product of this optimality property is that it gives us a natural and precise measure of bias and bias shifts, conceptually related to Solomonoff’s conceptual jump size of .

Since there is no fundamental difference between domain-specific problem-solving programs and programs that manipulate probability distributions and thus essentially rewrite the search procedure itself, we collapse both learning and metalearning in the same time-optimal framework.

An example initial language. For an illustrative application, we wrote an interpreter for a stack-based universal programming language inspired by Forth , with initial primitives for defining and calling recursive functions, iterative loops, arithmetic operations, and domain-specific behavior. Optimal metasearching for better search algorithms is enabled through the inclusion of bias-shifting instructions that can modify the conditional probabilities of future search options in currently running program prefixes.

Experiments. Using the assembler-like language mentioned above, we first teach oops something about recursion, by training it to construct samples of the simple context free language $`\{1^k2^k\}`$ ($`k`$ 1’s followed by $`k`$ 2’s), for $`k`$ up to 30 (in fact, the system discovers a universal solver for all $`k`$). This takes roughly 0.3 days on a standard personal computer (PC). Thereafter, within a few additional days, oops demonstrates incremental knowledge transfer: it exploits aspects of its previously discovered universal $`1^k2^k`$-solver, by rewriting its search procedure such that it more readily discovers a universal solver for all $`k`$ disk Towers of Hanoi problems—in the experiments it solves all instances up to $`k=30`$ (solution size $`2^k1`$), but it would also work for $`k>30`$. Previous, less general reinforcement learners and nonlearning AI planners tend to fail for much smaller instances.

Future research may focus on devising particularly compact, particularly reasonable sets of initial codes with particularly broad practical applicability. It may turn out that the most useful initial languages are not traditional programming languages similar to the Forth-like one, but instead based on a handful of primitive instructions for massively parallel cellular automata , or on a few nonlinear operations on matrix-like data structures such as those used in recurrent neural network research . For example, we could use the principles of oops to create a non-gradient-based, near-bias-optimal variant of Hochreiter’s successful recurrent network metalearner . It should also be of interest to study probabilistic Speed Prior-based oops variants  and to devise applications of oops-like methods as components of universal reinforcement learners (see below). In ongoing work, we are applying oops to the problem of optimal trajectory planning for robotics in a realistic physics simulation. This involves the interesting trade-off between comparatively fast program-composing primitives or “thinking primitives” and time-consuming “action primitives”, such as stretch-arm-until-touch-sensor-input.

## 10 OOPS-Based Reinforcement Learning

At any given time, a reinforcement learner  will try to find a policy (a strategy for future decision making) that maximizes its expected future reward. In many traditional reinforcement learning (RL) applications, the policy that works best in a given set of training trials will also be optimal in future test trials . Sometimes, however, it won’t. To see the difference between searching (the topic of the previous sections) and reinforcement learning (RL), consider an agent and two boxes. In the $`n`$-th trial the agent may open and collect the content of exactly one box. The left box will contain $`100n`$ Swiss Francs, the right box $`2^n`$ Swiss Francs, but the agent does not know this in advance. During the first 9 trials the optimal policy is “open left box.” This is what a good searcher should find, given the outcomes of the first 9 trials. But this policy will be suboptimal in trial 10. A good reinforcement learner, however, should extract the underlying regularity in the reward generation process and predict the future tasks and rewards, picking the right box in trial 10, without having seen it yet.

The first general, asymptotically optimal reinforcement learner is the recent AIXI model  (Section 7). It is valid for a very broad class of environments whose reactions to action sequences (control signals) are sampled from arbitrary computable probability distributions. This means that AIXI is far more general than traditional RL approaches. However, while AIXI clarifies the theoretical limits of RL, it is not practically feasible, just like Hsearch is not. From a pragmatic point of view, what we are really interested in is a reinforcement learner that makes optimal use of given, limited computational resources. In what follows, we will outline one way of using oops-like bias-optimal methods as components of general yet feasible reinforcement learners.

We need two oops modules. The first is called the predictor or world model. The second is an action searcher using the world model. The life of the entire system should consist of a sequence of cycles 1, 2, … At each cycle, a limited amount of computation time will be available to each module. For simplicity we assume that during each cyle the system may take exactly one action. Generalizations to actions consuming several cycles are straight-forward though. At any given cycle, the system executes the following procedure:

1. For a time interval fixed in advance, the predictor is first trained in bias-optimal fashion to find a better world model, that is, a program that predicts the inputs from the environment (including the rewards, if there are any), given a history of previous observations and actions. So the $`n`$-th task ($`n=1,2,\mathrm{}`$) of the first oops module is to find (if possible) a better predictor than the best found so far.
2. Once the current cycle’s time for predictor improvement is used up, the current world model (prediction program) found by the first oops module will be used by the second module, again in bias-optimal fashion, to search for a future action sequence that maximizes the predicted cumulative reward (up to some time limit). That is, the $`n`$-th task ($`n=1,2,\mathrm{}`$) of the second oops module will be to find a control program that computes a control sequence of actions, to be fed into the program representing the current world model (whose input predictions are successively fed back to itself in the obvious manner), such that this control sequence leads to higher predicted reward than the one generated by the best control program found so far.
3. Once the current cycle’s time for control program search is used up, we will execute the current action of the best control program found in step 2. Now we are ready for the next cycle.

The approach is reminiscent of an earlier, heuristic, non-bias-optimal RL approach based on two adaptive recurrent neural networks, one representing the world model, the other one a controller that uses the world model to extract a policy for maximizing expected reward . The method was inspired by previous combinations of nonrecurrent, reactive world models and controllers .

At any given time, until which temporal horizon should the predictor try to predict? In the AIXI case, the proper way of treating the temporal horizon is not to discount it exponentially, as done in most traditional work on reinforcement learning, but to let the future horizon grow in proportion to the learner’s lifetime so far . It remains to be seen whether this insight carries over to oops-rl.

Despite the bias-optimality properties of oops for certain ordered task sequences, however, oops-rl is not necessarily the best way of spending limited time in general reinforcement learning situations. On the other hand, it is possible to use oops as a proof-searching submodule of the recent, optimal, universal, reinforcement learning Gödel machine  discussed in the next section.

## 11 The Gödel Machine

The Gödel machine  explicitly addresses the ‘Grand Problem of Artificial Intelligence’  by optimally dealing with limited resources in general reinforcement learning settings, and with the possibly huge (but constant) slowdowns buried by AIXI$`(t,l)`$  in the somewhat misleading $`O()`$-notation. It is designed to solve arbitrary computational problems beyond those solvable by plain oops, such as maximizing the expected future reward of a robot in a possibly stochastic and reactive environment (note that the total utility of some robot behavior may be hard to verify—its evaluation may consume the robot’s entire lifetime).

How does it work? While executing some arbitrary initial problem solving strategy, the Gödel machine simultaneously runs a proof searcher which systematically and repeatedly tests proof techniques. Proof techniques are programs that may read any part of the Gödel machine’s state, and write on a reserved part which may be reset for each new proof technique test. In an example Gödel machine  this writable storage includes the variables proof and switchprog, where switchprog holds a potentially unrestricted program whose execution could completely rewrite any part of the Gödel machine’s current software. Normally the current switchprog is not executed. However, proof techniques may invoke a special subroutine check() which tests whether proof currently holds a proof showing that the utility of stopping the systematic proof searcher and transferring control to the current switchprog at a particular point in the near future exceeds the utility of continuing the search until some alternative switchprog is found. Such proofs are derivable from the proof searcher’s axiom scheme which formally describes the utility function to be maximized (typically the expected future reward in the expected remaining lifetime of the Gödel machine), the computational costs of hardware instructions (from which all programs are composed), and the effects of hardware instructions on the Gödel machine’s state. The axiom scheme also formalizes known probabilistic properties of the possibly reactive environment, and also the initial Gödel machine state and software, which includes the axiom scheme itself (no circular argument here). Thus proof techniques can reason about expected costs and results of all programs including the proof searcher.

Once check() has identified a provably good switchprog, the latter is executed (some care has to be taken here because the proof verification itself and the transfer of control to switchprog also consume part of the typically limited lifetime). The discovered switchprog represents a globally optimal self-change in the following sense: provably none of all the alternative switchprogs and proofs (that could be found in the future by continuing the proof search) is worth waiting for.

There are many ways of initializing the proof searcher. Although identical proof techniques may yield different proofs depending on the time of their invocation (due to the continually changing Gödel machine state), there is a bias-optimal and asymptotically optimal proof searcher initialization based on a variant of oops  (Section 9). It exploits the fact that proof verification is a simple and fast business where the particular optimality notion of oops is appropriate. The Gödel machine itself, however, may have an arbitrary, typically different and more powerful sense of optimality embodied by its given utility function.

## 12 Conclusion

Recent theoretical and practical advances are currently driving a renaissance in the fields of universal learners and optimal search . A new kind of AI is emerging. Does it really deserve the attribute “new,” given that its roots date back to the 1930s, when Gödel published the fundamental result of theoretical computer science  and Zuse started to build the first general purpose computer (completed in 1941), and the 1960s, when Solomonoff and Kolmogorov published their first relevant results? An affirmative answer seems justified, since it is the recent results on practically feasible computable variants of the old incomputable methods that are currently reinvigorating the long dormant field. The “new” AI is new in the sense that it abandons the mostly heuristic or non-general approaches of the past decades, offering methods that are both general and theoretically sound, and provably optimal in a sense that does make sense in the real world.

We are led to claim that the future will belong to universal or near-universal learners that are more general than traditional reinforcement learners / decision makers depending on strong Markovian assumptions, or than learners based on traditional statistical learning theory, which often require unrealistic i.i.d. or Gaussian assumptions. Due to ongoing hardware advances the time has come for optimal search in algorithm space, as opposed to the limited space of reactive mappings embodied by traditional methods such as artificial feedforward neural networks.

It seems safe to bet that not only computer scientists but also physicists and other inductive scientists will start to pay more attention to the fields of universal induction and optimal search, since their basic concepts are irresistibly powerful and general and simple. How long will it take for these ideas to unfold their full impact? A very naive and speculative guess driven by wishful thinking might be based on identifying the “greatest moments in computing history” and extrapolating from there. Which are those “greatest moments”? Obvious candidates are:

1. 1623: first mechanical calculator by Schickard starts the computing age (followed by machines of Pascal, 1640, and Leibniz, 1670).
2. Roughly two centuries later: concept of a programmable computer (Babbage, UK, 1834-1840).
3. One century later: fundamental theoretical work on universal integer-based programming languages and the limits of proof and computation (Gödel, Austria, 1931, reformulated by Turing, UK, 1936); first working programmable computer (Zuse, Berlin, 1941).

(The next 50 years saw many theoretical advances as well as faster and faster switches—relays were replaced by tubes by single transistors by numerous transistors etched on chips—but arguably this was rather predictable, incremental progress without radical shake-up events.)
4. Half a century later: World Wide Web (UK’s Berners-Lee, Switzerland, 1990).

This list seems to suggest that each major breakthrough tends to come roughly twice as fast as the previous one. Extrapolating the trend, optimists should expect the next radical change to manifest itself one quarter of a century after the most recent one, that is, by 2015, which happens to coincide with the date when the fastest computers will match brains in terms of raw computing power, according to frequent estimates based on Moore’s law. The author is confident that the coming 2015 upheaval (if any) will involve universal learning algorithms and Gödel machine-like, optimal, incremental search in algorithm space —possibly laying a foundation for the remaining series of faster and faster additional revolutions culminating in an “Omega point” expected around 2040.

## 13 Acknowledgments

Hutter’s frequently mentioned work was funded through the author’s SNF grant 2000-061847 “Unification of universal inductive inference and sequential decision theory.” Over the past three decades, numerous discussions with Christof Schmidhuber (a theoretical physicist) helped to crystallize the ideas on computable universes—compare his notion of “mathscape” .


format: text

text:
# Instability of the Fermi-liquid fixed point in an extended Kondo model

## I Introduction

One of the most striking properties discovered in Heavy-Fermion systems these last years is the existence of a non-Fermi-liquid behavior  in the disordered phase close to the magnetic quantum critical point with a temperature dependence of the physical quantities which differs from that of a standard Fermi-liquid. Recent results obtained in $`CeCu_{5.9}Au_{0.1}`$ by inelastic neutron scattering experiments  have shown the existence of anomalous $`\omega /T`$ scaling law for the dynamical spin susceptibility at the antiferromagnetic wavevector which persists over the entire Brillouin zone. This indicates that the spin dynamics are critical not only at large length scales as in the itinerant magnetism picture  but also at atomic length scales. It strongly suggests the presence of locally critical modes beyond the standard spin-fluctuation theory. Alternative theories have then been proposed to describe such a local quantum critical point. In this direction, we will mention recent calculations  based on dynamical mean field theory (DMFT) which seem to lead to encouraging results such as the prediction of a scaling law for the dynamical susceptibility. The other approach which has been put forward to describe the local QCP is based on supersymmetric theory  in which the spin is described in a mixed fermionic-bosonic representation. The interest of the supersymmetric approach is to describe the quasiparticles and the local moments on an equal footing through the fermionic and the bosonic part of the spin respectively. It appears to be specially well-indicated in the case of the locally critical scenario in which the magnetic temperature scale $`T_N`$, and the Fermi scale $`T_K`$ (the Kondo temperature) below which the quasiparticles die, vanish at the same point $`\delta _C`$.

Let us now emphasize another aspect in the discussion of the breakdown of the Fermi-liquid theory. It has to do with the question of the instability of the strong coupling (SC) fixed point. A stable SC fixed point is usually associated with a local Fermi-liquid behavior. On the contrary, an instability of the SC fixed point is an indication for the existence of an intermediate coupling fixed point with non-Fermi-liquid behavior. The traditional source of instability of the SC fixed point in the Kondo model is the presence of several channels for the conduction electrons with the existence of two regimes, the underscreened and the overscreened ones with very different associated behavior. In the one-channel antiferromagnetic single-impurity Kondo model, it is well known from renormalization group arguments, that the system flows to a stable SC fixed point  with a behavior of the system identified with that of a local Fermi liquid . The situation is rather different in the case of the multichannel Kondo model with a number $`K`$ of channels for the conduction electrons ($`K>1`$) . In the underscreened regime when $`K<2S`$ (where $`S`$ is the value of the spin in $`SU(2)`$), the SC fixed point is stable. It becomes unstable in the other regime $`K>2S`$ named as the overscreened regime. The underscreened regime corresponds to the one-stage Kondo effect with the formation of an effective spin $`(S1/2)`$ resulting from the screening of the impurity spin by the conduction electrons located on the same site. The system described by the SC fixed point behaves as a local Fermi liquid. The instability of the SC fixed point in the overscreened regime is associated with a multi-stage Kondo effect in which successively the impurity spin is screened by conduction electrons on the same site, and then the dressed impurity is screened by conduction electrons on the neighboring site and so forth. The overscreened regime leads to the existence of an intermediate coupling fixed point with non-Fermi-liquid excitation spectrum and an anomalous residual entropy at zero temperature. It has been recently put forward  that other sources of instability of the SC fixed point may exist else but the multiplicity of the conduction electron channels. Recent works have shown that the presence of a more general Kondo impurity where the spin symmetry is extended from $`SU(2)`$ to $`SU(N)`$, and the impurity has mixed symmetry, may also lead to an unstability of the SC fixed point already in the one-channel case. In the large $`N`$ limit, Coleman et al.  have found that the SC fixed point becomes unstable as soon as the impurity parameter $`q`$ (defined below) is larger than $`N/2`$ whatever the value of $`2S`$ (defined below) is, giving rise to a two-stage Kondo effect. This result opens the route for the existence of an intermediate coupling fixed point with eventually non-Fermi-liquid behavior.

It is worth noticing that the supersymmetry theory, or more specifically the taking into account of general Kondo impurities appears to offer valuable insights into the two issues raised by the breakdown of the Fermi liquid theory that we have summarized above, i.e. both the existence of locally critical modes and the question of the instability of the SC fixed point. Somehow it seems that the consideration of general Kondo impurities captures the physics present in real systems with the coexistence of the screening of the spin by conduction electrons responsible for the formation of quasiparticles, and the formation of localized magnetic moment that persists and eventually leads to a phase transition as the coupling to other impurities becomes dominant.

The aim of this work is to study the $`SU(N)`$, extended single-impurity Kondo model in the one-channel case . We would like to investigate how the system behaves when not only the values of the parameters $`(2S,q)`$ of the representation vary, but also the number $`n_d`$ of conduction electrons on the neighboring site does. We want to discuss the effect of $`n_d`$ on the stability of the SC fixed point and to further understand the nature of the screening with the possibility of achieving either a one-stage, two-stage or multi-stage Kondo effect depending on the regime considered. Implications for the behavior of physical quantities will be given.

## II Extended $`SU(N)`$ single-impurity Kondo model

We consider a generalized, single-impurity, Kondo model with one channel of conduction electrons and a spin symmetry group extended from $`SU(2)`$ to $`SU(N)`$. An impurity spin, $`𝐒`$, is placed at the origin (site $`0`$). We deal with impurities that can be realized by a combination of $`2S`$ bosonic ($`b_\alpha ^{}`$) and $`q1`$ fermionic ($`f_\alpha ^{}`$) operators. The hamiltonian describing the model is written as

$$H=\underset{𝐤,\alpha }{}\epsilon _𝐤c_{𝐤,\alpha }^{}c_{𝐤,\alpha }+J\underset{A}{}𝐒^A\underset{\alpha ,\beta }{}c_\alpha ^{}(0)\tau _{\alpha \beta }^Ac_\beta (0),$$
(1)
where $`c_{𝐤,\alpha }^{}`$ is the creation operator of a conduction electron with momentum $`𝐤`$, and $`SU(N)`$ spin index $`\alpha =a,b,\mathrm{},r_N`$, $`c_\alpha ^{}(0)=\frac{1}{\sqrt{N_S}}_𝐤c_{𝐤,\alpha }^{}`$ , where $`N_S`$ is the number of sites, and $`\tau _{\alpha \beta }^A`$ ($`A=1,\mathrm{},N^21`$) are the generators of the $`SU(N)`$ group in the fundamental representation, with $`Tr[\tau ^A\tau ^B]=\delta _{AB}/2`$. The conduction electrons interact with the impurity spin $`𝐒^A`$ ($`A=1,\mathrm{},N^21`$), placed at the origin, via Kondo coupling, $`J>0`$. When the impurity is in the fundamental representation, we recover the Coqblin-Schrieffer model  describing conduction electrons in interaction with an impurity spin of angular momentum $`j`$, ($`N=2j+1`$, $`a=j,b=j1,\mathrm{},r_N=j`$), resulting from the combined spin and orbit exchange scattering.

### A Strong-coupling fixed point

We consider the case where $`J\mathrm{}`$ and we can neglect the kinetic energy in Eq. 1. In this limit the model can be solved exactly in terms of the invariants associated to the spin of the electrons and of the impurities . The eigenvalues are of the form

$`E_{SC}={\displaystyle \frac{J}{2}}\left[𝒞_2(R_{SC})𝒞_2(I)𝒞_2(Y)\right]`$ (2)
where $`I`$ denotes the impurity spin, $`Y`$ the spin of the $`n_c`$ conduction electrons coupled to the impurity at the origin, and $`R_{SC}`$ the spin of the resulting SC state at the impurity site. The quantities $`𝒞_2`$ are the $`SU(N)`$ generalization of the $`SU(2)`$ eigenvalues, $`S(S+1)`$, and can be readily evaluated (for details, see Ref. ).

The ground state corresponds to having $`n_c=(Nq)`$ electrons at the origin, partially screening the impurity. It can be written explicitely as the action of $`(2S1)`$ bosonic operators on a singlet state. For instance the highest spin state can be written as

$$|GS_{\{a\}aa}^{[2S1]}=\frac{1}{\sqrt{\left(2S1\right)!}}(b_a^{})^{2S1}\left[\frac{1}{\gamma }𝒜(b_{i_1}^{}(\underset{\alpha =i_2}{\overset{i_q}{}}f_\alpha ^{})(\underset{\beta =i_{q+1}}{\overset{i_N}{}}c_\beta ^{}))\right]|0$$
(3)
with $`\gamma \sqrt{(2S+N1)C_{N1}^{q1}}`$. Here, $`c_\alpha ^{}c_\alpha ^{}(0)`$. We denote the ground state energy by $`E_0`$.

The effect of the kinetic term in Eq. 1 is, to lowest order in perturbation theory, to mix the ground state with excited states where the number of electrons changes by one. There are three such states, which we denote by $`|GS+1^S`$, $`|GS+1^A`$ and $`|GS1`$. The labels S(A) indicate that the additional electron is coupled symmetrically(antisymmetrically) to the ground state. The states are readily obtained by deriving the relevant SU(N) Clebsch-Gordan coefficients .

### B Stability of the strong coupling fixed point

In order to better understand the low-energy physics of the system, we should consider the finite Kondo coupling, allowing virtual hopping from and to the impurity site. These processes generate interactions between the composite at site 0 and the conduction electrons on neighboring sites, that can be treated as perturbations of the SC fixed point. The energy shifts due to the perturbation can be reproduced by introducing an interaction between the spin at the impurity site and the spin of the electrons on the neighboring site, with effective coupling $`J_{eff}`$. Applying an analysis similar to that of Nozières and Blandin  to the nature of the excitations, we can argue whether or not the SC fixed point remains stable once virtual hopping is allowed.

Thus, if the coupling between the effective spin at the impurity site and that of the electrons on site 1 is ferromagnetic we know, from the scaling analysis at weak coupling, that the perturbation is irrelevant, and the low energy physics is described by a SC fixed point. That is, an underscreened, effective impurity weakly coupled to a gas of free electrons with a phase shift indicating that there are already $`(Nq)`$ electrons screening the original impurity.

If, on the contrary, the effective coupling is antiferromagnetic, the perturbation is relevant, the SC fixed point is unstable and the low-energy physics of the model corresponds to some intermediate coupling fixed point, to be identified.

We explicitely calculate the effects of hopping on the SC fixed point to the lowest order in perturbation theory, that is, second order in $`t`$. We consider the case with an arbitrary number $`n_d`$ of conduction electrons in site 1 generalizing the case $`n_d=1`$ considered in ref. .

Adding $`n_d`$ electrons on site 1 leads to two different states, that we will call symmetric (S) and antisymmetric (A). These states, degenerate in the SC limit, acquire energy shifts, $`\mathrm{\Delta }E_0^A`$ and $`\mathrm{\Delta }E_0^S`$ due to the perturbation given, in the large-N limit, by

$`\mathrm{\Delta }E_0^A=\left({\displaystyle \frac{2t^2}{J}}\right)\left[\left({\displaystyle \frac{Nq}{q}}\right){\displaystyle \frac{n_d}{N}}\left({\displaystyle \frac{N(N2q)}{q(Nq)}}\right)\right],`$ (4)
$`\mathrm{\Delta }E_0^S\mathrm{\Delta }E_0^A`$ $`=`$ $`\left({\displaystyle \frac{2S+n_d1}{2S+Nq}}\right)\left({\displaystyle \frac{2t^2}{JN}}\right)\left({\displaystyle \frac{N(N2q)}{q(Nq)}}\right),`$ (5)
$`=`$ $`{\displaystyle \frac{J_{eff}}{2}}(2S+n_d1).`$ (6)
Notice that the behavior of both Eq. 4 and Eq. 5 are controlled by the same factor. This result has the immediate following physical consequence. The change of sign of $`J_{eff}`$ (Fig. 1, Right) -and hence of the stability of the SC fixed point- is directly connected to the change in the behavior of $`\mathrm{\Delta }E_0^A\mathrm{\Delta }E_0^S`$ with $`n_d`$. In particular, when $`\mathrm{\Delta }E_0^S=\mathrm{\Delta }E_0^A`$, $`\mathrm{\Delta }E_0^A=(2t^2/J)`$ independently ***This is true for arbitrary values of $`N`$, and $`2S`$. of $`n_d`$, $`q`$ or $`2S`$. In the regime where the SC fixed point is stable, $`q/N<1/2`$, $`J_{eff}<0`$, the lowest energy corresponds to $`n_d=1`$, whereas for $`q/N>1/2`$, $`J_{eff}>0`$, the energy expressed in Eq. (4) is minimized for $`n_d=(N1)`$ (Fig. 1, Left). This is precisely the mechanism behind the two-stage quenching. The accumulation of electrons on site 1 is not related to $`J_{eff}`$ which is independent of $`n_d`$, but results from the dependence of $`\mathrm{\Delta }E_0^A\mathrm{\Delta }E_0^S`$ with $`n_d`$.

We finish by making some remarks on the physical properties of the model in the different regimes. As is common to all models with an antiferromagnetic Kondo coupling, there will be a crossover from weak coupling above a given Kondo scale, $`T_K`$, to a low-energy regime. When the SC fixed point is stable, we should expect for $`TT_K`$ a weak coupling of the effective impurity at site-0 with the rest of the electrons. The physical properties at low temperature are controlled by the degeneracy of the effective impurity, $`d([2S1])=C_{N+2S2}^{N1}`$. Thus, we should expect a residual entropy $`𝒮^i\mathrm{ln}C_{N+2S2}^{N1}`$ and a Curie susceptibility, $`\chi ^iC_{N+2S2}^{N1}/T`$, with logarithmic corrections . This is the result that we would expect for a purely symmetric impurity. Contrary to the purely bosonic case, only $`(Nq)`$ electrons are allowed at the origin in the SC limit, instead of $`(N1)`$. Thus, we would expect to find different results for quantities that involve the scattering phase shift of electrons off the effective impurity.

In the $`q>N/2`$, we do not have access to the intermediate coupling fixed point that determines the low-energy behavior. Nevertheless, it is reasonable to think that there would be a magnetic contribution to the entropy, and a Curie-like contribution to the susceptibility, since the impurity remains unscreened. This behavior is different from that of the multichannel Kondo model, which is also characterized by an intermediate coupling fixed point, but where the impurity magnetic degrees of freedom are completely quenched. The degeneracy of the true ground state is an open question, but we can assume that the entropy will be smaller than that of the SC fixed point . It is in the scattering properties that we might be able to see the anomalous features of this new fixed point more clearly.

## III Conclusions

We have studied a Kondo model where the spin of the impurity has mixed symmetry, as a way of incorporating the phenomena of local moment screening and magnetic correlation that is observed in some heavy fermion compounds. Such model is naturally realized by extending the spin symmetry to $`SU(N)`$, and it displays a rich phase diagram. We find that as long as the bosonic component of spin is of order $`N`$, there is a transition around the point where the fermionic component of the impurity is $`q=N/2`$. At this particular point, the energy shift is, to lowest order in perturbation theory around the SC fixed point, equal to $`2t^2/J`$, independent of the impurity parameters, $`q`$, $`S`$ and $`N`$. When $`q<N/2`$, the low-energy physics corresponds to the SC fixed point. For $`q>N/2`$ the SC fixed point is unstable and anomalous behavior is expected, in particular, the two-stage quenching effect. This phase diagram is not accidental, but is due to the relation of the effective impurity site in the SC regime to the conduction electrons in neighboring sites, as our study of the dependence of the energy shifts on $`n_d`$ reveals. If $`q<N/2`$, the energy is minimized when the dressed impurity repeals the electrons on the next site. That is, when $`n_d=1`$. At $`q=N/2`$, the energy shift is also independent of $`n_d`$. Finally, the lowest energy shift for $`q>N/q`$ corresponds to a maximal $`n_d`$, indicating the accumulation of electrons leading to the two-stage Kondo quenching.

###### Acknowledgements.

We would like to thank V. Zlatic and A. Hewson for organizing this very interesting meeting. We are most grateful to N. Andrei for continuous encouragement and discussions. We also thank S. Burdin, P. Coleman, Ph. Nozières, and C. Pépin for helpful discussions.

Also at the Centre National de la Recherche Scientifique (CNRS).


text:
# Anomalies and non-log-normal tails in one-dimensional localization with power-law disorder

(February 2003)

## Abstract

Within a general framework, we discuss the wave function statistics in the Lloyd model of Anderson localization on a one-dimensional lattice with a Cauchy distribution for the random on-site potential. We demonstrate that already in leading order in the disorder strength, there exists a hierarchy of anomalies in the probability distributions of the wave function, the conductance, and the local density of states, for every energy which corresponds to a rational ratio of wave length to the lattice constant. We also show that these distribution functions do have power-law rather then log-normal tails and do not display universal single-parameter scaling. These peculiarities persist in any model with power-law tails of the disorder distribution function.

Wave function localization in one spatial dimension has attracted enormous attention since the pioneering work by Anderson.Anderson  Much of our present understanding of this phenomenon is based on the original Anderson model taken on a one-dimensional lattice

$$t(\mathrm{\Psi }_{n+1}+\mathrm{\Psi }_{n1})+V_n\mathrm{\Psi }_n=E\mathrm{\Psi }_n,$$
(1)
with a white-noise disorder $`V_nV_m\delta _{nm}`$, $`V_n=0`$, and fixed hopping element $`t`$. The potential $`V_n`$ at each site takes real values according to a probability density $`P_V(V)`$. Most of the theoretical investigations of Anderson localization assume a finite variance $`\mathrm{var}V2D<\mathrm{}`$, and then consider the weak-disorder limit $`Dt^2`$. This condition is a prerequisite for single-parameter scaling, ATAF  in which the product $`L\xi ^1`$ of system length $`L`$ and inverse localization length $`\xi ^1=lim_n\mathrm{}\frac{1}{n}\mathrm{ln}|\mathrm{\Psi }_n|`$ is the only free parameter in the universal distribution function of the Lyapunov exponents $`\alpha =\frac{1}{n}\mathrm{ln}|\mathrm{\Psi }_n|`$ for finite $`n`$. This carries over to universal distribution functions of the dimensionless conductance $`g`$ and the local density of states $`\nu `$. For $`L/\xi 1`$ these distribution functions follow log-normal laws — the paradigm for large fluctuations. On the other hand, in many realistic applications the distribution function $`P_V(V)`$ displays power-law tails, with $`D=\mathrm{}`$, such that in a sense disorder never really is weak. The most prominent example is the localization of wave functions in the momentum space of the kicked rotator. FGP  This dynamical problem has been mapped onto the Anderson model in the seminal works FGP, ; Shepelyanskii, , with an effectively random Cauchy-distributed potential

$$P_{V,\mathrm{Cauchy}}(V)=\frac{1}{\pi }\mathrm{Im}\frac{1}{Vi\delta },\delta >0.$$
(2)
Equation (1) with the disorder distribution function given by Eq. (2) has been proposed for the first time by Lloyd. Lloyd  In this model the localization length can be computed analytically for arbitrary $`\delta `$, Thouless ; Ishii  and the variance of the Lyapunov exponents $`\alpha `$ has been analyzed very recently in Ref. DLA, .

A beautiful experimental realization of the kicked rotator is the dynamics of atoms driven by a regular train of laser pulses. Raizen ; Raizen2  In these experiments, the probability distribution function in momentum space is seen to relax from an initial Gaussian into an exponential profile, demonstrating the absence of diffusion in momentum direction. However, since the wave function statistics in localization is a prototypical example of large fluctuations, the localization length of the eigenstates can be quantitatively inferred from moments of the wave function (like the measured mean probability) only if the full shape of the distribution function is known, including its tails. The impact of the tails of the probability density $`P_V(V)`$ on the statistics of the wave functions has been already mentioned by Halperin,Halperin  but has not been analyzed, let alone sufficiently appreciated, in the literature.

In this paper we address the fluctuations of the wave function $`\mathrm{\Psi }`$ and related quantities for distributions $`P_V(V)`$ with power-law tails, by going beyond the mean $`\xi ^1`$ of $`\alpha `$ and its variance, studied so far. Thouless ; Ishii ; DLA  We first set out a general framework for arbitrary $`P_V(V)`$, which then is applied to the Lloyd model with $`P_V(V)`$ given by Eq. (2). The fluctuations turn out to be highly non-universal, with an anomalous energy dependence \[reflecting also the spatial discreetness of the Anderson model (1)\] and non-log-normal tails that strongly affect the behavior of the moments of $`\mathrm{\Psi }`$, $`g`$, and $`\nu `$ even in the weak-disorder limit $`\delta t`$, and even for low fractional orders of the moments. These characteristics of the wave function statistics are in striking contrast to the universality for models with $`Dt^2`$ and single-parameter scaling.

The central quantity of interest in our calculation is the generating function $`\mu (\lambda )`$ of the cumulants of $`\mathrm{ln}\mathrm{\Psi }`$. As pointed out by Borland Borland  and Thouless, Thouless1979  instead of solving Eq. (1) as a boundary-value problem it suffices to investigate the specific solution $`\mathrm{\Phi }_n`$ of the initial-value problem $`\mathrm{\Phi }_0=a`$, $`\mathrm{\Phi }_1=b`$. At large distances $`n1`$ this solution exponentially increases as $`\mathrm{\Phi }_n\mathrm{exp}(\alpha n)`$ for almost all values of $`a`$ and $`b`$, which statistically is equivalent to the inverse wave-function decay $`\mathrm{\Psi }_n\mathrm{\Phi }_n^1`$ in the original problem. The cumulant-generating function

$$\mu (\lambda )=\underset{n\mathrm{}}{lim}\frac{1}{n}\mathrm{ln}\left|\mathrm{\Phi }_n\right|^\lambda =\underset{k=1}{\overset{\mathrm{}}{}}\frac{c_k}{k!}\lambda ^k$$
(3)
accounts for the details of convergence of the Lyapunov exponent $`\alpha `$ to its mean value $`c_1=\xi ^1`$. The coefficients $`c_k`$ with $`k2`$ are numerical constants which characterize the deviations of $`\alpha `$ from $`c_1`$. As follows from Eq. (3) the cumulants of $`\alpha `$ vanish according to the law dictated by the generalized central-limit theorem

$$\alpha ^kc_kn^{1k}\text{for }n\xi .$$
(4)
The coefficients $`c_k`$ do not depend on the initial conditions for $`\mathrm{\Phi }_n`$ and capture the universal information about the fluctuations of many essential quantities in the localized regime, such as the dimensionless conductance $`g`$ of a finite sample of the length $`L`$ and the local density of statesSTBB  $`\nu `$ in a semi-infinite wire at a distance $`L`$ to an open boundary. Both quantities do strongly fluctuate even in the localized regime $`L\xi `$, unlike the Lyapunov exponent. However, the fluctuations of their logarithms can be expressed through the same coefficients $`c_k`$ by

$$\underset{L\mathrm{}}{lim}\frac{1}{L}\left(\mathrm{ln}g\right)^k=\underset{L\mathrm{}}{lim}\frac{1}{L}\left(\mathrm{ln}\nu \right)^k=2^kc_k.$$
(5)
Each coefficient may be used to define a length scale $`\xi _k=c_k^1`$, and the question for single-parameter scaling can be posed as whether these length scales are independent quantities or not. ST2003b

We now set out a general approach to calculate the generating function $`\mu (\lambda )`$ and the coefficients $`c_k`$ for arbitrary form of $`P_V(V)`$. We built up on the formalism previously used to calculate the inverse localization length $`\xi ^1=c_1`$. LGP ; Derrida ; Bovier  The Anderson model (1) can be written in terms of new variables $`z_n=\mathrm{\Psi }_{n+1}/\mathrm{\Psi }_n`$, $`r_n=\mathrm{ln}|\mathrm{\Psi }_n|`$ in the simple way

$$z_n=v_n1/z_{n1},r_n=r_{n1}+\mathrm{ln}|z_{n1}|,$$
(6)
where $`v_n(V_nE)/t`$. We seek the specific solution of the initial-value problem $`z_0=b/a`$, $`r_0=\mathrm{ln}|a|`$. Iterating the map (6) we observe that $`z_n`$ and $`r_n`$ take real values $`z`$ and $`r`$ with a probability density $`P_n(z,r)`$, which obeys

$`P_n(z,r)`$ $`=`$ $`{\displaystyle _{\mathrm{}}^{\mathrm{}}}F(v)𝑑v{\displaystyle _{\mathrm{}}^{\mathrm{}}P_{n1}(z^{},r^{})𝑑z^{}𝑑r^{}}`$ (7)
$`\times `$ $`\delta (zv+1/z^{})\delta (rr^{}\mathrm{ln}|z^{}|),`$
with $`F(v)=tP_V(vt+E)`$ the probability density of $`v`$.

It is convenient to introduce the function

$$h_n(z,\lambda )=|z|^\lambda _{\mathrm{}}^{\mathrm{}}e^{r\lambda }P_n(z,r)𝑑r$$
(8)
and rewrite Eq. (7) as

$$h_n(z,\lambda )=|z|^\lambda _{\mathrm{}}^{\mathrm{}}F(z+1/z^{})h_{n1}(z^{},\lambda )𝑑z^{}.$$
(9)
According to Eqs. (3) and (8) we have

$$\mu (\lambda )=\underset{n\mathrm{}}{lim}\frac{1}{n}\mathrm{ln}\left[_{\mathrm{}}^{\mathrm{}}𝑑zh_{n1}(z,\lambda )\right].$$
(10)
If the function $`\mu (\lambda )`$ exists, the solution to Eq. (9) at large $`n`$ must fulfill the relation $`h_n(z,\lambda )=e^{\mu (\lambda )}h_{n1}(z,\lambda )`$. Thus Eq. (9) is transformed into the functional eigenvalue problem

$`e^{\mu (\lambda )\lambda \mathrm{ln}|z|}h(z,\lambda )=[h](z,\lambda ),`$ (11a)
$`[h](z,\lambda ){\displaystyle _{\mathrm{}}^{\mathrm{}}}F(z+1/z^{})h(z^{},\lambda )𝑑z^{}.`$ (11b)
This is the central general equation of this paper. In any practical case it has to be solved perturbatively in $`\lambda `$. We expand the function $`h(z,\lambda )`$ in a series

$$h(z,\lambda )=\underset{k=0}{\overset{\mathrm{}}{}}\frac{\lambda ^k}{k!}h_k(z)$$
(12)
and introduce the notation $`\stackrel{~}{c}_1(z)c_1\mathrm{ln}|z|`$. Equation (11) is transformed into the following set of equations

$`[h_0]h_0=0,`$ (13a)
$`[h_1]h_1=\stackrel{~}{c}_1h_0,`$ (13b)
$`[h_2]h_2=(\stackrel{~}{c}_1^2+c_2)h_0+2\stackrel{~}{c}_1h_1,`$ (13c)
$`[h_3]h_3=(\stackrel{~}{c}_1^3+3\stackrel{~}{c}_1c_2+c_3)h_0`$
$`+3(\stackrel{~}{c}_1^2+c_2)h_1+3\stackrel{~}{c}_1h_2,\text{ etc.}`$ (13d)
Equation (13a) delivers the stationary distribution function of $`z`$ and has been used before LGP ; Derrida ; Bovier  to calculate the localization length $`\xi =c_1^1`$ from

$$c_1=_{\mathrm{}}^{\mathrm{}}h_0(z)\mathrm{ln}|z|dz.$$
(14)
So far we have shown that Eq. (13a) can be considered as just the first member of a hierarchy of equations that determine the complete wave function statistics for finite $`n\xi `$.

The integrals $`_{\mathrm{}}^{\mathrm{}}𝑑z`$ of the left-hand sides of Eqs. (13) equal zero. Equation (14) indeed can be derived by integrating both sides of Eq. (13b) along the real axis. Once the distribution function $`h_0(z)`$ and the mean Lyapunov exponent $`c_1`$ are known (as is analytically the case in the Lloyd model), one can construct the solution to Eq. (13b) iteratively byfootnote

$`h_1(z)=𝒦[\stackrel{~}{c}_1h_0](z),`$ (15a)
$`𝒦[f](z)f(z){\displaystyle _{\mathrm{}}^{\mathrm{}}}K(z,z^{})f(z^{})𝑑z^{}.`$ (15b)
The second coefficient $`c_2`$ in the cumulant expansion is readily found by integrating Eq. (13c) along the real axis,

$$c_2=_{\mathrm{}}^{\mathrm{}}[h_0(z)(\mathrm{ln}|z|c_1)+2h_1(z)](\mathrm{ln}|z|c_1)𝑑z.$$
(16)
This procedure can be repeated recursively to calculate all other coefficients $`c_k`$.

For the Lloyd model, the scheme developed above allows us to obtain the coefficients $`c_k`$ analytically. The stationary distribution function of the variable $`z`$ is readily found by the exact solution of the integral equation (13a), Lloyd ; LGP

$$h_0(z)=\frac{1}{\pi }\mathrm{Im}\frac{1}{zs},s+\frac{1}{s}=\frac{E+i\delta }{t},\mathrm{Im}s>0.$$
(17)
The integral (14) yields the well-known result

$$c_1=\mathrm{ln}|s|.$$
(18)
The kernel function $`K(z,z^{})`$ can be obtained by iterative application of the operator $`[h]`$,

$`K(z,z^{})={\displaystyle \frac{1}{\pi }}\mathrm{Im}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left({\displaystyle \frac{1}{zp_n(z^{})}}{\displaystyle \frac{1}{zr_n}}\right),`$ (19a)
$`p_n(z)={\displaystyle \frac{(s^ns^n)z(s^{n+1}s^{(n+1)})}{(s^{n1}s^{(n1)})z(s^ns^n)}},`$ (19b)
$`r_n=p_n(\pm \mathrm{}),`$ (19c)
where the second term in the parenthesis on the right hand side of Eq. (19a) is added to provide a better convergence of the intermediate expressions.footnote

Applying the result (19) to Eqs. (15) and (16) and performing the summation one recovers the result of Ref. DLA, ,

$`c_2=\mathrm{Re}\left[\mathrm{Li}_2(\mathrm{s}^2)\mathrm{Li}_2(|\mathrm{s}|^2)\right]+\mathrm{arg}(s)(\pi \mathrm{arg}(s))`$
$`+\mathrm{ln}|s|^2\left[\mathrm{ln}(|s|^21)\mathrm{ln}|s^21|\right],`$ (20)
where $`\mathrm{Li}_n(z)=_{k=1}^{\mathrm{}}z^k/k^n`$ is the polylogarithmic function. As has been shown in Ref. DLA, , in the limit $`\delta 0`$ the ratio $`c_2/c_1`$ equals $`2`$ (not $`1`$ as for conventional weak disorder) inside the band (it vanishes outside the band). This energy-insensitivity has encouraged the authors of Ref. DLA,  to conclude that single-parameter scaling is fulfilled, and to introduce a novel criterion for single-parameter scaling. As we will discuss now, these findings do not carry over to the fluctuations beyond the variance, characterized by $`c_k`$ with $`k3`$.

The coefficient $`c_3`$ can be found from Eq. (13d) as

$`c_3`$ $`=`$ $`3{\displaystyle _{\mathrm{}}^{\mathrm{}}}𝑑z\mathrm{ln}\left|{\displaystyle \frac{s}{z1/s}}\right|\left[c_2\mathrm{ln}^2\left|{\displaystyle \frac{s}{z}}\right|\right]h_0(z)`$ (21a)
$`+`$ $`3{\displaystyle _{\mathrm{}}^{\mathrm{}}}𝑑z\mathrm{ln}\left|{\displaystyle \frac{s}{z}}\right|\left[\mathrm{ln}\left|{\displaystyle \frac{s}{z}}\right|2\mathrm{ln}\left|{\displaystyle \frac{s}{z1/s}}\right|\right]\mathrm{\Sigma }(z),`$
$`\mathrm{\Sigma }(z)`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}\mathrm{Im}{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left[{\displaystyle \frac{1}{zs}}{\displaystyle \frac{1}{zp_n(s^{})}}\right]\mathrm{ln}{\displaystyle \frac{s^{}}{p_n^1(z)}},`$ (21b)
where the function $`p_n^1(z)`$ stands for the inverse of $`p_n(z)`$. The ratio $`c_3/c_1`$ is plotted at Fig. (1) versus the energy. The plot clearly displays a sequence of sharp dips, which appear exactly at energies $`E=2t\mathrm{cos}(\pi p/q)`$ where $`p`$ and $`q`$ are integer, and become more narrow in the limit $`\delta 0`$. The anomaly in the band center is the biggest one and reaches about $`3`$% of the absolute value of the ratio $`c_3/c_1`$ in the limit $`\delta 0`$. The existence of such anomalies for the inverse localization length $`\xi ^1=c_1`$ has been pointed out by Lambert, Lambert  but for this quantity they only show up in higher orders of the expansion in the disorder strength, with exception of the band edge $`|E|=2`$ and the band center $`E=0`$. Lambert ; Derrida ; KW  For conventional weak disorder with $`Dt^2`$ the other anomalies should be seen in the higher coefficients $`c_k`$ with $`k3`$. However, those cumulants are themselves suppressed by orders of $`D/t^2`$ (see Table 1), again with the exception of the band edge and the band center, where they are of the same order as $`c_1`$ and $`c_2`$. ST2002 ; ST2003a ; ST2003b ; DEL

In striking contrast, in the Lloyd model the coefficients $`c_k`$ increase very rapidly with increasing index $`k`$. In the limit $`\delta 0`$ we indeed observe $`c_2/c_1=2`$, $`c_3/c_1=5`$, $`c_4/c_120`$, $`c_5/c_1100`$ for $`p/q`$ irrational. The analysis of Eqs. (13) for the Lloyd model demonstrates that the generating function $`\mu (\lambda )`$ exists only for $`\lambda <\lambda _c`$, where the convergence radius $`\lambda _c<1`$, which implies a factorial growth of the ratios $`c_k/c_1`$ for large $`k`$. Such a behavior is consistent with a power-law tail in the conductance distribution function $`P_g(g)g^{(2\lambda _c)/2}`$ for $`g0`$. For a general power law $`P_V(V)|V|^\beta `$ for $`|V|\mathrm{}`$, $`\lambda _c<\beta 1`$ must be expected to depend on $`\beta `$, implying that the precise form of the tail in $`P_g(g)`$ is not universal. The power-law tail in $`P_g(g)`$ is certified by the numerical result for the conductance distribution function for Cauchy disorder, shown for $`L/\xi =6`$ in Fig. 2. The probability to find a vanishing conductance in the Lloyd model is strongly enhanced as compared to the case of conventional weak disorder, which displays log-normal tails. In this case, the generating function $`\mu (\lambda )`$ is well-defined for all $`\lambda `$ in the whole energy range. Moreover, far from the band edges ($`\epsilon 2t|E|D^{2/3}t^{1/3}`$) and far from the band center ($`ED/t`$), it acquires a universal parabolic form $`\mu (\lambda )=\xi ^1(\lambda +\lambda ^2/2)`$, since $`c_1=c_2=D/(4t^2E^2)`$, while all other coefficients can be disregarded in the limit $`Dt^2`$ (see Table 1).

In conclusion, we have studied analytically the statistics of localized wave functions in the Lloyd model, which is frequently used to analyze dynamical localization. We have found that the distribution functions of the conductance $`g`$ and of the local density of states $`\nu `$ do not have a log-normal form. Moreover, even in the limit of vanishing disorder these distribution functions reveal sharp anomalies at energies $`E=2t\mathrm{cos}(\pi p/q)`$, with $`p/q`$ a rational number. These specific features can be attributed to the power-law decay of the disorder distribution function. They sensitively affect the moments (including fractional moments) of $`g`$ and $`\nu `$ and demonstrate that for such distribution functions the wave-function statistics are highly non-universal. It would be striking to see similar effects for the prelocalized states in the diffusive regime $`L\xi `$ of multichannel systems. AKL

We thank B. L. Altshuler and S. Fishman for illuminating discussions.