Ergodic theory is concerned with dynamical systems -- collections of points together with a rule governing how the system changes over time. Much of the theory is concerned with the long term behavior of typical points-- how points behave over time, ignoring anomalous behavior from a small number of exceptional points. Computability theory has a family of precise notions of randomness: a point is "algorithmically random'' if no computable test can demonstrate that it is not random. These notions capture something essential about the informal notion of randomness: algorithmically random points are precisely the ones that have typical orbits in computable dynamical systems. For computable dynamical systems with or without assumptions of ergodicity, the measure 0 set of exceptional points for various theorems (such as Poincaré's Recurrence Theorem or the pointwise ergodic theorem) are precisely the Schnorr or Martin-Löf random points identified in algorithmic randomness.

We discuss the different contexts in which relativization occurs in randomness and the effect that the relativization chosen has on the results we can obtain. We study several characterizations of the K-trivials in terms of concepts ranging from cuppability to density, and we consider a uniform relativization for randomness that gives us more natural results for computable randomness, Schnorr randomness, and Kurtz randomness than the classical relativization does (the relativization for Martin-Löf randomness is unaffected by this change). We then evaluate the relativizations we have considered and suggest some avenues for further work.

Algorithmic randomness lies at the intersection between computability theory and probability theory. In order to fully explore this interaction, one naturally needs a computable version of measurable functions. While several such notions appear in the literature, most of them do not interact well with algorithmic randomness because they are only defined up to a null set. Therefore, we need a computable notion of measurable function which is well defined on algorithmically random points, and this is what layerwise computability precisely does. This article is a survey about this notion. We give the main definitions, the most important properties, and several applications of this notion. We prioritize motivating this framework and explaining its salient features.

This chapter treats the general concept of pattern matching and the specific functions available to do this. In addition, the chapter explains the syntax of regular expressions, the notation used to describe the patterns we want to match.

This chapter covers the advanced topic of functional programming in Python, introducing the general notion of function programming and then the various tools available in Python to approximate it.

This chapter explains how to install Python and basic methods for interacting with the language: the interactive environment, Idle, programs executed on the command line, and Jupyter notebooks. The focus is on simple things one can do with Python in the interactive environment. The chapter concludes with several small programs that can be run at the command line.

The field of algorithmic randomness studies the various ways to define the inherent randomness of individual points in a space (for example, the Cantor space or Euclidean space). Classically, this quest seems quixotic. However, the theory of computing allows us to give mathematically meaningful notions of random points. In the past few decades, algorithmic randomness has been extended to make use of resource-bounded (e.g., time or space) computation. In this survey we survey these developments as well as their applications to other parts of mathematics.

As a starting point we study finite-state automata, which represent the simplest devices for recognizing languages. The theory of finite-state automata has been described in numerous textbooks both from a computational and an algebraic point of view. Here we immediately look at the more general concept of a monoidal finite-state automaton, and the focus of this chapter is general constructions and results for finite-state automata over arbitrary monoids and monoidal languages. Refined pictures for the special (and more standard) cases where we only consider free monoids or Cartesian products of monoids will be given later.

The aim of this chapter is twofold. First, we recall a collection of basic mathematical notions that are needed for the discussions of the following chapters. Second, we have a first, still purely mathematical, look at the central topics of the book: languages, relations and functions between strings, as well as important operations on languages, relations and functions. We also introduce monoids, a class of algebraic structures that gives an abstract view on strings, languages, and relations.

Classical finite-state automata represent the most important class of monoidal finite-state automata. Since the underlying monoid is free, this class of automaton has several interesting specific features. We show that each classical finite-state automaton can be converted to an equivalent classical finite-state automaton where the transition relation is a function. This form of ‘deterministic’ automaton offers a very efficient recognition mechanism since each input word is consumed on at most one path. The fact that each classical finite-state automaton can be converted to a deterministic automaton can be used to show that the class of languages that can be recognized by a classical finite-state automaton is closed under intersections, complements, and set differences. The characterization of regular languages and deterministic finite-state automata in terms of the ‘Myhill–Nerode equivalence relation’ to be introduced in the chapter offers an algebraic view on these notions and leads to the concept of minimal deterministic automata.

A fundamental task in natural language processing is the efficient representation of lexica. From a computational viewpoint, lexica need to be represented in a way directly supporting fast access to entries, and minimizing space requirements. A standard method is to represent lexica as minimal deterministic (classical) finite-state automata. To reach such a representation it is of course possible to first build the trie of the lexicon and then to minimize this automaton afterwards. However, in general the intermediate trie is much larger than the resulting minimal automaton. Hence a much better strategy is to use a specialized algorithm to directly compute the minimal deterministic automaton in an incremental way. In this chapter we describe such a procedure.

This chapter describes a special construction based on finite-state automata with important applications: the Aho–Corasick algorithm is used to efficiently find all occurrences of a finite set of strings (also called pattern set, or dictionary) in a given input string, called the ‘text’. Search is ‘online’, which means that the input text is neither fixed nor preprocessed in any way. This problem is a special instance of pattern matching in strings, and other automata constructions are used to solve other pattern matching tasks. From an automaton point of view, the Aho–Corasick algorithm comes in two variants. We first present the more efficient version where a classical deterministic finite-state automaton is built for text search. The disadvantage of this first construction is that the resulting automaton can become very large, in particular for large pattern alphabets. Afterwards we present the second version, where an automaton with additional transitions of a particular kind is built, yielding a much smaller device for text search.