Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive programwhere rem is the remainder in the division of a by b, the unique natural number r such that for some natural number q,It is an algorithm from the remainder function rem, meaning that in computing its time complexity function cε, we assume that the values rem are provided on demand by some “oracle” in one “time unit”. It is easy to (...) prove thatMuch more is known about cε, but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's optimality among its peers—algorithms from rem:Conjecture. If an algorithm α computes gcd from rem with time complexity cα, then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα > r log2a. (shrink)

The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale (...) geometries of infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness. (shrink)

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is (...) set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. (shrink)

This paper provides algorithmic options for belief revision of a database receiving an infinite stream of inputs. At stage , the database is ¡£¢ , receiving the input ¤ ¢ . The revision algorithms for moving to the new database ¡ ¢¦¥¨§© ¡ ¢ ¤ ¢ take into account the history of previous revisions actually executed as well as possible revision options which were discarded at the time but may now be pursued. The appropriate methodology for carrying this out (...) is Labelled Deductive Systems. (shrink)

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive programwhere rem is the remainder in the division of a by b, the unique natural number r such that for some natural number q,It is an algorithm from the remainder function rem, meaning that in computing its time complexity function cε, we assume that the values rem are provided on demand by some “oracle” in one “time unit”. It is easy to (...) prove thatMuch more is known about cε, but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's optimality among its peers—algorithms from rem:Conjecture. If an algorithm α computes gcd from rem with time complexity cα, then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα > r log2a. (shrink)

An a priori semimeasure (also known as “algorithmic probability” or “the Solomonoff prior” in the context of inductive inference) is defined as the transformation, by a given universal monotone Turing machine, of the uniform measure on the infinite strings. It is shown in this paper that the class of a priori semimeasures can equivalently be defined as the class of transformations, by all compatible universal monotone Turing machines, of any continuous computable measure in place of the uniform measure. Some (...) consideration is given to possible implications for the association of algorithmic probability with certain foundational principles of statistics. (shrink)

A growing number of studies on fairness in artificial intelligence (AI) use the notion of intersectionality to measure AI fairness. Most of these studies take intersectional fairness to be a matter of statistical parity among intersectional subgroups: an AI algorithm is “intersectionally fair” if the probability of the outcome is roughly the same across all subgroups defined by different combinations of the protected attributes. This paper identifies and examines three fundamental problems with this dominant interpretation of intersectional fairness in (...) AI. First, the dominant approach is so preoccupied with the intersection of attributes/categories (e.g., race, gender) that it fails to address the intersection of oppression (e.g., racism, sexism), which is more central to intersectionality as a critical framework. Second, the dominant approach faces a dilemma between infinite regress and fairness gerrymandering: it either keeps splitting groups into smaller subgroups or arbitrarily selects protected groups. Lastly, the dominant view fails to capture what it really means for AI algorithms to be fair, in terms of both distributive and non-distributive fairness. I distinguish a strong sense of AI fairness from a weak sense that is prevalent in the literature, and conclude by envisioning paths towards strong intersectional fairness in AI. (shrink)

We prove various results connected together by the common thread of computability theory.First, we investigate a new notion of algorithmic dimension, the inescapable dimension, which lies between the effective Hausdorff and packing dimensions. We also study its generalizations, obtaining an embedding of the Turing degrees into notions of dimension.We then investigate a new notion of computability theoretic immunity that arose in the course of the previous study, that of a set of natural numbers with no co-enumerable subsets. We demonstrate how (...) this notion of $\Pi ^0_1$ -immunity is connected to other immunity notions, and construct $\Pi ^0_1$ -immune reals throughout the high/low and Ershov hierarchies. We also study those degrees that cannot compute or cannot co-enumerate a $\Pi ^0_1$ -immune set.Finally, we discuss a recently discovered truth-table reduction for transforming a Kolmogorov–Loveland random input into a Martin-Löf random output by exploiting the fact that at least one half of such a KL-random is itself ML-random. We show that there is no better algorithm relying on this fact, in the sense that there is no positive, linear, or bounded truth-table reduction which does this. We also generalize these results to the problem of outputting randomness from infinitely many inputs, only some of which are random.Abstract prepared by David J. Webb.E-mail: [email protected]: https://arxiv.org/pdf/2209.05659.pdf. (shrink)

This article addresses “Creativity after Computation” by looking into the concept of artificial imagination, namely the machine’s ability to produce images that challenge artmaking and surprise human beings with the aid of machine learning algorithms. What is at stake is not only art and creativity but also the tension between the determination of machines and the freedom of human beings. This opposition restages Kant’s third antinomy in the contemporary technological condition. By referring to the debate on the question of imagination (...) in Kant, Heidegger, and Stiegler, the article suggests that imagination is always already artificial and that it is more productive to develop an organology of artificial imagination. It clarifies the notion of artificial imagination and offers an organological reading through a reinterpretation of Leibniz’s monadology, Kant’s sublime, and Schiller’s aesthetic education against the backdrop of recursive algorithms. (shrink)

This is a defense and extension of Stephen Yablo's claim that self-reference is completely inessential to the liar paradox. An infinite sequence of sentences of the form 'None of these subsequent sentences are true' generates the same instability in assigning truth values. I argue Yablo's technique of substituting infinity for self-reference applies to all so-called 'self-referential' paradoxes. A representative sample is provided which includes counterparts of the preface paradox, Pseudo-Scotus's validity paradox, the Knower, and other enigmas of the genre. (...) I rebut objections that Yablo's paradox is not a genuine liar by constructing a sequence of liars that blend into Yablo's paradox. I rebut objections that Yablo's liar has hidden self-reference with a distinction between attributive and referential self-reference and appeals to Gregory Chaitin's algorithmic information theory. The paper concludes with comments on the mystique of self-reference. (shrink)

Fractal art graphics are the product of the fusion of mathematics and art, relying on the computing power of a computer to iteratively calculate mathematical formulas and present the results in a graphical rendering. The selection of the initial value of the first iteration has a greater impact on the final calculation result. If the initial value of the iteration is not selected properly, the iteration will not converge or will converge to the wrong result, which will affect the accuracy (...) of the fractal art graphic design. Aiming at this problem, this paper proposes an improved optimization method for selecting the initial value of the Gauss-Newton iteration method. Through the area division method of the system composed of the sensor array, the effective initial value of iterative calculation is selected in the corresponding area for subsequent iterative calculation. Using the special skeleton structure of Newton’s iterative graphics, such as infinitely finely inlaid chain-like, scattered-point-like composition, combined with the use of graphic secondary design methods, we conduct fractal art graphics design research with special texture effects. On this basis, the Newton iterative graphics are processed by dithering and MATLAB-based mathematical morphology to obtain graphics and then processed with the help of weaving CAD to directly form fractal art graphics with special texture effects. Design experiments with the help of electronic Jacquard machines proved that it is feasible to transform special texture effects based on Newton's iterative graphic design into Jacquard fractal art graphics. (shrink)

The long-periodic/infinite discrete Gabor transform is more effective than the periodic/finite one in many applications. In this paper, a fast and effective approach is presented to efficiently compute the Gabor analysis window for arbitrary given synthesis window in DGT of long-periodic/infinite sequences, in which the new orthogonality constraint between analysis window and synthesis window in DGT for long-periodic/infinite sequences is derived and proved to be equivalent to the completeness condition of the long-periodic/infinite DGT. By using the (...) property of delta function, the original orthogonality can be expressed as a certain number of linear equation sets in both the critical sampling case and the oversampling case, which can be fast and efficiently calculated by fast discrete Fourier transform. The computational complexity of the proposed approach is analyzed and compared with that of the existing canonical algorithms. The numerical results indicate that the proposed approach is efficient and fast for computing Gabor analysis window in both the critical sampling case and the oversampling case in comparison to existing algorithms. (shrink)

This paper proposes an extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system. Chaitin's Ω is defined as the probability that the universal self-delimiting Turing machine U halts, and plays a central role in the development of algorithmic information theory. In the theory, there are two equivalent ways to define the program-size complexity H of a given finite binary string s. In the standard way, H is defined as the length of the (...) shortest input string for U to output s. In the other way, the so-called universal probability m is introduced first, and then H is defined as –log2m without reference to the concept of program-size.Mathematically, the statistics of outcomes in a quantum measurement are described by a positive operator-valued measure in the most general setting. Based on the theory of computability structures on a Banach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called a universal semi-POVM. We also give another characterization of Chaitin's Ω numbers by universal probabilities. Then, based on this characterization, we propose to define an extension of Ω as a sum of the POVM elements of a universal semi-POVM. The validity of this definition is discussed.In what follows, we introduce an operator version equation image of H in a Hilbert space of infinite dimension using a universal semi-POVM, and study its properties. (shrink)

In cinematic experience, a view from nowhere appears in an instituting moment – neither in time nor out of time, but part of time itself – when a camera reflex lifts the viewer’s perception out of somewhere and into the infinite time of the film. We argue that the view from nowhere found in Birt Acres’s film Rough Sea at Dover – a fifteen-second shot of waves breaking against a sea wall in Dover, England in 1895 – transcends all (...) attempts to turn it into a view from somewhere, as an empty space that carries the auratic trace of the past into the present through phase shifts of technical mediation. In Simondon’s terms, the view from nowhere opens up possibilities of becoming all ways at once in the reflexive capacity of the human organon. Following Stiegler’s organological technics, we identify the capture of perception by the apparatus of recording and playback in the digitally automated algorithm as a threat to the reflexive capability of the organon to see otherwise in the creative individuation opened up in the phase-shifting process. Our analysis triggers a switch from an anthropocentric to a neganthropic-ecological mode of seeing in which the auratic trace of the event of waves crashing against the pier is seen in an inhuman view from nowhere that carries the threat of automatized systems in which human noesis – self-reflexive capacity – is eclipsed by machines. By seeing otherwise, the eclipse by machines is reversed to reveal the complex becoming of the film in its materiality as a work of creative individuation. (shrink)

In classical propositional logic, a theory T is prime iff it is complete. In Łukasiewicz infinite-valued logic the two notions split, completeness being stronger than primeness. Using toric desingularization algorithms and the fine structure of prime ideal spaces of free ℓ -groups, in this paper we shall characterize prime theories in infinite-valued logic. We will show that recursively enumerable prime theories over a finite number of variables are decidable, and we will exhibit an example of an undecidable r.e. (...) prime theory over countably many variables. (shrink)

Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for each n (...) , the real $\Omega^A_M$ is $\textrm{high}_n$ for some universal Turing machine M by using the extended van Lambalgen's Theorem. (shrink)

This article enlarges classical syllogistic logic with assertions having to do with comparisons between the sizes of sets. So it concerns a logical system whose sentences are of the following forms: Allxareyand Somexarey, There are at least as manyxasy, and There are morexthany. Herexandyrange over subsets (not elements) of a giveninfiniteset. Moreover,xandymay appear complemented (i.e., as$\bar{x}$and$\bar{y}$), with the natural meaning. We formulate a logic for our language that is based on the classical syllogistic. The main result is a soundness/completeness theorem. (...) There are efficient algorithms for proof search and model construction. (shrink)

Aggregative consequentialism and several other popular moral theories are threatened with paralysis: when coupled with some plausible assumptions, they seem to imply that it is always ethically indifferent what you do. Modern cosmology teaches that the world might well contain an infinite number of happy and sad people and other candidate value-bearing locations. Aggregative ethics implies that such a world contains an infinite amount of positive value and an infinite amount of negative value. You can affect only (...) a finite amount of good or bad. In standard cardinal arithmetic, an infinite quantity is unchanged by the addition or subtraction of any finite quantity. So it appears you cannot change the value of the world. Modifications of aggregationism aimed at resolving the paralysis are only partially effective and cause severe side effects, including problems of “fanaticism”, “distortion”, and erosion of the intuitions that originally motivated the theory. Is the infinitarian challenge fatal? (shrink)

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines and (...) more). There are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds. (shrink)

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be (...) solved in the limit if, after some finite point in the sequence, all the guesses are correct and the same. Functions, sets, and functionals which are decidable by such infinite algorithms will be calledlimiting recursive. These, together with classes of objects which can beidentified in the limit, are the subjects of this report.Without qualification,setwill mean set of numbers;functionwill mean number-theoretic function of 1 variable, possibly partial;functionalswill take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional,xwill invariably stand for a numerical variable;φfor a function variable;gfor a guess ;nfor the numerical variable which indexes the guesses, referred to as thetime. (shrink)

Stereotypically, computation involves intrinsic changes to the medium of representation: writing new symbols, erasing old symbols, turning gears, flipping switches, sliding abacus beads. Perspectival computation leaves the original inscriptions untouched. The problem solver obtains the output by merely alters his orientation toward the input. There is no rewriting or copying of the input inscriptions; the output inscriptions are numerically identical to the input inscriptions. This suggests a loophole through some of the computational limits apparently imposed by physics. There can be (...) symbol manipulation without inscription manipulation because symbols are complex objects that have manipulatable elements besides their inscriptions. Since a written symbol is an ordered pair of consisting of a shape and the reader's orientation to that inscription, the symbol can be changed by changing the orientation rather than inscription. Although there are the usual physical limits associated with reading the answer, the computation is itself instantaneous. This is true even when the sub-calculations are algorithmically complex, exponentially increasing or even infinite. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all (...) physical systems can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf (...) 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

Quantum computer is considered as a generalization of Turing machine. The bits are substituted by qubits. In turn, a "qubit" is the generalization of "bit" referring to infinite sets or series. It extends the consept of calculation from finite processes and algorithms to infinite ones, impossible as to any Turing machines (such as our computers). However, the concept of quantum computer mets all paradoxes of infinity such as Gödel's incompletness theorems (1931), etc. A philosophical reflection on how quantum (...) computer might implement the idea of "infinite calculation" is the main subject. (shrink)

The paper introduces the notion of size of countable sets, which preserves the Part-Whole Principle. The sizes of the natural and the rational numbers, their subsets, unions, and Cartesian products are algorithmically enumerable as sequences of natural numbers. The method is similar to that of Numerosity Theory, but in comparison it is motivated by Bolzano’s concept of infinite series, it is constructive because it does not use ultrafilters, and set sizes are uniquely determined. The results mostly agree, but some (...) differ, such as the size of rational numbers. However, set sizes are only partially, not linearly, ordered. Quid pro quo. (shrink)

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅. We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C ≥ |x|-c. The ‘only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results (...) on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

A set of infinite binary sequences ${\cal C} \subseteq 2$ℕ is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of ${\rm{\Pi }}_1^0 $ classes. In this paper, we introduce the notion of depth for ${\rm{\Pi }}_1^0 $ classes, which is a stronger form of negligibility. Whereas a negligible ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that (...) one cannot probabilistically compute a member of ${\cal C}$ with positive probability, a deep ${\rm{\Pi }}_1^0 $ class ${\cal C}$ has the property that one cannot probabilistically compute an initial segment of a member of ${\cal C}$ with high probability. That is, the probability of computing a length n initial segment of a deep ${\rm{\Pi }}_1^0 $ class converges to 0 effectively in n.We prove a number of basic results about depth, negligibility, and a variant of negligibility that we call tt-negligibility. We provide a number of examples of deep ${\rm{\Pi }}_1^0 $ classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, examine the relationship between deep classes and certain lowness notions in algorithmic randomness, and establish a relationship between members of deep classes and the amount of mutual information with Chaitin’s Ω. (shrink)

The connections between forms of code and coding and the many crises that currently afflict the contemporary world run deep. Code and crisis in our time mutually define, and seemingly prolong, each other in ‘infinite branching graphs’ of decision problems. There is a growing academic literature that investigates digital code and software from a wide range of perspectives –power, subjectivity, governmentality, urban life, surveillance and control, biopolitics or neoliberal capitalism. The various strands in this literature are reflected in the (...) papers that comprise this special issue. They address topics ranging from social networks, mass media, financial markets and academic plagiarism to highway engineering in relation to the dynamics and diversity of crises. Against this backdrop, the purpose of this essay is to highlight and explore some of the underlying themes connecting codes and codings and the production and apprehension of ‘crisis’. We analyse how the ever-increasing intermediation of contemporary life by codes of various kinds has been closely shadowed by a proliferation of crises. We discuss three related aspects of the coupling of code and crisis (signification, performativity and excess) running across these seemingly diverse topics. We and the other contributors in this special issue seek to go beyond the restricted (and often restricting) understanding of code as the language of machines. Rather, we view code qua programs and algorithms as epitomizing a much broader phenomenon. The codes that we live, and that we live by, also tell us about the ways in which the ‘will to power’ and the 'will to knowledge' tend to be enacted in the contemporary world. (shrink)

The traditional use of ergodic theory in the foundations of equilibrium statistical mechanics is that it provides a link between thermodynamic observables and microcanonical probabilities. First of all, the ergodic theorem demonstrates the equality of microcanonical phase averages and infinite time averages (albeit for a special class of systems, and up to a measure zero set of exceptions). Secondly, one argues that actual measurements of thermodynamic quantities yield time averaged quantities, since measurements take a long time. The combination of (...) these two points is held to be an explanation why calculating microcanonical phase averages is a successful algorithm for predicting the values of thermodynamic observables. It is also well-known that this account is problematic.

This survey intends to show that ergodic theory nevertheless may have important roles to play, and it explores three other uses of ergodic theory. Particular attention is paid, firstly, to the relevance of specific interpretations of probability, and secondly, to the way in which the concern with systems in thermal equilibrium is translated into probabilistic language. With respect to the latter point, it is argued that equilibrium should not be represented as a stationary probability distribution as is standardly done; instead, a weaker definition is presented. (shrink)

These lectures on logic, more specifically proof theory, are basically intended for postgraduate students and researchers in logic. The question at stake is the nature of mathematical knowledge and the difference between a question and an answer, i.e., the implicit and the explicit. The problem is delicate mathematically and philosophically as well: the relation between a question and its answer is a sort of equality where one side is ``more equal than the other'': one thus discovers essentialist blind spots. Starting (...) with Godel's paradox --so to speak, the incompleteness of answers with respect to questions--the book proceeds with paradigms inherited from Gentzen's cut-elimination. Various settings are studied: sequent calculus, natural deduction, lambda calculi, category-theoretic composition, up to geometry of interaction, all devoted to explicitation, which eventually amounts to inverting an operator in a von Neumann algebra. Mathematical language is usually described as referring to a preexisting reality. Logical operations can be given an alternative procedural meaning: typically, the operators involved in GoI are invertible, not because they are constructed according to the book, but because logical rules are those ensuring invertibility. Similarly, the durability of truth should not be taken for granted: one should distinguish between imperfect and perfect modes. The procedural explanation of the infinite thus identifies it with the unfinished, i.e., the perennial. But is perenniality perennial? This questioning yields a possible logical explanation for algorithmic complexity. This highly original course on logic by one of the world's leading proof theorists challenges mathematicians, computer scientists, physicists, and philosophers to rethink their views and concepts on the nature of mathematical knowledge in an exceptionally profound way. (shrink)

We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the learning type InfEx_\iso, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures is InfEx_\iso-learnable if and only if the structures can be distinguished in terms of their \Sigma^2_inf-theories. We apply this characterization to familiar cases and we show the following: there is an (...) class='Hi'>infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:A Just Share: Justice and Fairness in Resource Allocation*Pat Milmoe Mccarrick (bio) and Martina Darragh (bio)Each of us has some basic sense of what the words “fair” or “just” or “fairness” or “justice” mean. Each of us probably also has an idea of what is “fair” in health care. The attempt by the state of Oregon in the mid-1980s to quantify this notion made a previously private exercise a (...) public one. This transition has been chronicled in the bioethics literature that focuses on resource allocation. These works examine both theories of justice and concepts of “health”; the fair distribution of health resources has been of continuing interest since the beginning of bioethics in the 1960s. Early writing on justice includes authors Tom L. Beauchamp, Robert H. Blank, James F. Childress, H. Tristram Engelhardt, Paul T. Menzel, Paul Ramsey, and Robert M. Veatch (VII).During the 1980s, bioethicists such as Daniel Callahan and Norman Daniels proposed thinking of health care decisions not as moments of personal crisis but as choices that span a lifetime, possibly involving tradeoffs in other areas of one’s life, e.g., education. The Oregon experience added another dimension to the discussion. The initial rank-ordering of health services by cost produced a skewed list—for example, surgery for life-threatening conditions ranked below minor, elective procedures. For the project to make sense, the ranking algorithm could not be based on cost alone, but rather on a combination of costs and benefits both to individuals and to the community—“concatenations of individual and group goods” (I, Jecker and Jonsen 1995). Various metaphors have been used in the literature to facilitate discussion of this shift from individual to individual/community trade-offs: medical services as a “commons” (I, Asch 1995, Jecker and Jonsen 1995, Michels 1994); resource allocation as a “lifeboat” (I, Campbell 1995; III, Kaveny 1994); medical care as “shares” in a community health (III, Nelson 1992, Ford and Kissick 1995; II, Anderson 1993); and rationing as traveling through the desert with one jug of water for two people (a story from the Halachah literature) (I, Zoloth-Dorfman 1995). [End Page 81]Such metaphors do not promote any one “theory of justice” but rather draw from the work of a number of bioethicists as well as from theological, sociological, economic, and business literature. The five major conceptions of justice that are referenced most frequently are: “(1) a libertarian conception, which takes liberty to be the ultimate political ideal; (2) a socialist conception, which takes equality to be the ultimate political ideal; (3) a welfare liberal conception, which takes contractual fairness or maximal utility to be the ultimate political ideal; (4) a communitarian conception, which takes the common good to be the ultimate political ideal; and (5) a feminist conception, which takes a gender-free society to be the ultimate political ideal” (I, Sterba 1995).The use of new metaphors also draws on expanded concepts of “health.” “As health care is currently practiced, the most powerful symbols for public and professional alike are those that promise the defeat of time” (I, Campbell 1995). When medical care is perceived as an unrelated series of individual cures, the fact that health care resources are finite cannot be addressed.Reflections concerning the difficulties in limiting the use of health care resources have an ancient lineage and reveal a tight bond with the obsession to postpone death at all costs. Plato in Book 3 of the Republic recognizes the quandary of infinite expectations and finite resources that characterizes the challenge of health care choices. (I, Engelhardt 1996)The proliferation of expensive medical technologies and the loss of autonomy by health care professionals further complicates perceptions of the crucial issues at hand. Some have said that Americans place too much emphasis on individualism to address these issues. Daniels et al. believe that this is too pessimistic a view and that the American commitment to protecting equal opportunity for all provides a firm basis for developing a public consensus on what is fair in health care (III, Daniels, Light, and Caplan 1996). Finally, several authors suggest that the nature of all four principles of medical ethics, not justice alone, must be... (shrink)

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics as K4, S4, S4.1, K4.3, GL, or Grz are undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4,K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, if.

We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations (...) and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations . This contrasts with the well-known fact that usual Kolmogorov complexity does not depend on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (shrink)

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics asK4,S4,S4.1,K4.3,GL, orGrzare undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4, K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, ifl1andl2are classes of transitive frames such that their depth cannot (...) be bounded by any fixedn< ω, then the logic of the class {5ℑ1× ℑ2∣ ℑ1∈l1, ℑ2, ∈l2} is undecidable. (On the contrary, the product of, say,K4and the logic of all transitive Kripke frames of depth ≤n, for some fixedn< ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π11-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics. (shrink)

Quantum mechanics (QM) predicts probabilities on the fundamental level which are, via Born probability law, connected to the formal randomness of infinite sequences of QM outcomes. Recently it has been shown that QM is algorithmic 1-random in the sense of Martin–Löf. We extend this result and demonstrate that QM is algorithmic $$\omega$$ -random and generic, precisely as described by the ’miniaturisation’ of the Solovay forcing to arithmetic. This is extended further to the result that QM becomes Zermelo–Fraenkel Solovay random (...) on infinite-dimensional Hilbert spaces. Moreover, it is more likely that there exists a standard transitive ZFC model M, where QM is expressed in reality, than in the universe V of sets. Then every generic quantum measurement adds to M the infinite sequence, i.e. random real $$r\in 2^{\omega }$$, and the model undergoes random forcing extensions M[r]. The entire process of forcing becomes the structural ingredient of QM and parallels similar constructions applied to spacetime in the quantum limit, therefore showing the structural resemblance of both in this limit. We discuss several questions regarding measurability and possible practical applications of the extended Solovay randomness of QM. The method applied is the formalization based on models of ZFC; however, this is particularly well-suited technique to recognising randomness questions of QM. When one works in a constant model of ZFC or in axiomatic ZFC itself, the issues considered here remain hidden to a great extent. (shrink)

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what (...) follows, we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general. (shrink)

Recently, megastable systems have grabbed many researchers’ interests in the area of nonlinear dynamics and chaotic systems. In this paper, the oscillatory terms’ coefficients of the simplest megastable oscillator are forced to blink in time. The forced system can generate an infinitive number of hidden attractors without changing parameters. The behavior of these hidden attractors can be chaotic, tori, and limit cycle. The attractors’ topology of the system seems unique and looks like picture frames. Besides, the existence of different coexisting (...) attractors with different kinds of behaviors reflects the system's high sensitivity. Using the sample entropy algorithm, the system’s complexity for different initial values is assessed. In addition, the circuit of the introduced forced system is designed, and the possibility of implicating the system with analog elements is investigated. (shrink)