Preface
As the 1968 film 2001: A Space Odyssey gave an enigmatic and scientifically accurate depiction of space flight, so Jeffrey O. Shallit and Ming-Wei Wang’s paper Automatic complexity of strings [ 15 ] from 2001 described what we can call a “state odyssey”: journeys through the states of a finite automaton that held the promise of further deep exploration.
While Kolmogorov complexity is only defined “up to an additive constant”, automatic complexity gives concrete values. When I start up the Complexity Guessing Game at http://math.hawaii.edu/wordpress/bjoern/software/web/complexity-guessing-game/ on November 14, 2021, I am presented with the string \(x=011000111001010\) of length 15, and asked to guess its complexity, from 1 to 8. As we shall see in this book, in particular in Chapter 5, the best bet is to choose the largest complexity offered (8 in this case) unless you spot something very special about \(x\). This is correct for our \(x\) and next I am asked about the length 25 word
and for a guess for its complexity, from 1 to 13. Again I choose the maximum, but in this case, the game responds that the complexity is 12 and that there is a complexity deficiency of 1.
The idea of complexity (or randomness) deficiency comes from the study of Kolmogorov complexity. However, automatic complexity is a more manageable (and computable) measure of irregularity. When we say “irregularity” here it is partly a pun: automatic complexity is based on finite automata, that accept regular languages, so irregularity indicates a failure of small finite automata to uniquely identify the string in a sense.
This research area was started by Jeff Shallit and Ming-Wei Wang in 2001 [ 15 ] . I independently made the same definition in 2009 while teaching the class Math 301 (Discrete Mathematics) at University of Hawai‘i. Subsequently, I have written several papers which are treated in this book. Moreover, Jordon and Moser wrote a paper on the topic in 2021 [ 6 ] . It is my hope that this book will stimulate further work in this area.
As a research tool, and incidentally as a method of cheating at the Complexity Guessing Game, I have created a web service to find the complexity of a given word, and an illustration of an automaton used in the associated proof [ 7 ] .
The Complexity Option Game [ 8 ] is a variation on the same idea, inviting the player implement an exercise policy for a complexity-based financial option. These games include graphical displays of millions of the relevant automata.
How to use this book.
Chapter 1, Chapter 2, Chapter 3, and Chapter 4 answer the question “What” by introducing the basics of state-counting and edge-counting automatic complexity. Chapter 5 answers the question “How” (do we work with automatic complexity), answering a question of Shallit and Wang by estimating the complexity of random words. Chapter 6 and Chapter 7 are an attempt to answer the question “Why”. Conditional automatic complexity gives a perspective on the length-conditional aspect of automatic complexity, and automatic complexity turns out to give an answer to the question, what does logical depth look like in practice.
Each chapter contains exercises, most of which come with solutions in the proof assistant Lean. Open research problems also appear in dedicated sections.
Acknowledgments.
I am grateful to many people.
Andrew J.I. Jones, Dag Normann, Theodore A. Slaman, and many others mentored me in computability and logic.
In a Discrete Mathematics class in Spring 2009, students Jason Axelson, Chris Ho and Aaron Kondo wrote a C program that calculated the complexity of all strings of length at most 7. The dedication they put into that program fueled my interest in automatic complexity.
Logan Axon wrote the first Python script for automatic complexity.
Kayleigh K. Hyde’s 2013 Master’s project and her proof of the sharp upper bound for nondeterministic automatic complexity sparked my interest in proving theorems in this area.
Students who have worked with me on automatic complexity include Samuel D. Birns, Calvin K. Bannister, Swarnalakshmi (Janani) Lakshmanan and Daylan K. Yogi.
Jeff Shallit, Achilles Beros, Nikolai Vereshchagin, Sasha Shen, André Nies, Frank Stephan and Angeliki Koutsoukou-Argyraki provided encouragement and interesting discussions.
This research was supported in part by a grant from Decision Research Corporation (University of Hawai‘i Foundation Account #129-4770-4). This work was partially supported by a grant from the Simons Foundation (#704836 to Bjørn Kjos-Hanssen).
While I have tried to keep this book akamai, errors may occur and are my responsibility. I would be grateful to receive reports at bjoernkh+acmoi@hawaii.edu.