Information and Computation (Complexity: A Guided Tour)

What Is Information? Information is a widely used term referring to knowledge or facts, whether in newspapers, books, phone conversations, or digital communications. In complex systems, information pertains to the communication and processing of data. The precise definitions of information and computation were established in the 20th century, notably through a physics puzzle involving a hypothetical demon that led to significant insights about energy, work, and entropy.

Self-Organization: Complex systems often exhibit self-organization, where order emerges from disorder. Examples include the structured bridges built by army ants, the synchronized flashing of fireflies, and the development of specialized organs from stem cells. Understanding this entropy-defying self-organization is a key goal in complex systems science, which hinges on defining and measuring order, disorder, complexity, and simplicity through the concept of information.

Energy, Work, and Entropy: In physics, energy is the potential to do work, defined as the force applied to an object times the distance it moves. Entropy measures the energy in a system that cannot be converted into work, typically manifesting as heat loss. The two fundamental laws of thermodynamics state that energy is conserved and entropy always increases in isolated systems. These laws describe the unidirectional flow of time and the inevitability of increasing disorder.

Maxwell’s Demon: James Clerk Maxwell proposed a thought experiment to challenge the second law of thermodynamics. He imagined a demon that sorts fast and slow molecules between two halves of a box, seemingly decreasing entropy without doing work. This paradox puzzled scientists until Leo Szilard linked the demon’s act of measurement to an increase in entropy, thereby preserving the second law. Later refinements by Charles Bennett and Rolf Landauer showed that erasing the demon’s memory increases entropy, further validating the law.

Statistical Mechanics: Ludwig Boltzmann developed statistical mechanics to explain how macroscopic properties like heat emerge from microscopic behaviors of molecules. He introduced the concepts of microstates (exact configurations of molecules) and macrostates (observable properties like temperature). Boltzmann’s entropy quantifies the number of microstates corresponding to a macrostate, showing that systems naturally evolve towards states of higher entropy.

Shannon Information: Claude Shannon adapted Boltzmann’s ideas to communication systems, defining information in terms of message probabilities. Shannon’s theory, foundational to information theory, measures the information content or entropy of a source based on the predictability of its messages. This has applications in data compression, coding theory, cryptography, bioinformatics, and beyond.

Information theory provides a framework for understanding order and disorder in complex systems. Concepts like entropy, information content, and mutual information help define and measure complexity. While its impact on physics remains debated, information theory is central to various scientific and technological fields, offering insights into the behavior and organization of complex systems.

People often think of computation as what modern computers do: calculations, word processing, and other tasks performed by electronic devices. But in complex systems literature, computation appears in contexts like cell biology, immune systems, and financial markets. Understanding why these systems are described as computational requires a deep dive into the history and foundational concepts of computation.

What Is Computation and What Can Be Computed? In practical terms, information is analyzed, stored, combined, and used to produce results through computation. The definition of computation has evolved significantly, starting from manual calculations to what we now understand as electronic computing. Early 20th-century mathematicians tackled foundational questions about the limits of computation, leading to the development of electronic computers.

Hilbert’s Problems and Gödel’s Theorem: David Hilbert, a prominent mathematician, posed 23 significant mathematical problems in 1900, including whether mathematics is complete, consistent, and decidable. Kurt Gödel, in 1930, proved the incompleteness theorem, showing that in any consistent mathematical system, there are true statements that cannot be proved within that system. This was a groundbreaking result, revealing fundamental limitations in mathematics.

Turing Machines and Uncomputability: Alan Turing extended these ideas, addressing Hilbert’s third problem, the Entscheidungsproblem, which asks if there is a definite procedure to determine the truth of any mathematical statement. Turing’s concept of a Turing machine, an abstract computational device, laid the groundwork for modern computers and proved that some problems, like the Halting problem, are undecidable—no algorithm can determine if a given Turing machine will halt or run forever.

Definite Procedures and Universal Turing Machines: Turing defined “definite procedure” using Turing machines, which can simulate any computation process. A universal Turing machine can emulate any other Turing machine, akin to how modern computers run programs. Turing’s theoretical work paved the way for the development of electronic computers, showing both the potential and the inherent limitations of computation.

The Halting Problem: Turing’s Halting problem demonstrated that there is no universal procedure to determine if a given Turing machine will halt. This proof involved the concept of self-reference and led to the realization that some computational problems are inherently unsolvable, marking a significant limitation in the field of computation.

Impact and Legacy: The early 20th century saw a shift from the belief in limitless mathematical and scientific progress to recognizing inherent limits. Gödel’s and Turing’s work, while highlighting these limits, also led to the creation of electronic programmable computers, revolutionizing science and daily life. Their contributions underscore the balance between potential and limitation in the realm of computation.

Gödel and Turing: Different Paths: After their groundbreaking work, Gödel and Turing’s lives took different trajectories. Gödel continued his work in mathematical logic, despite struggling with mental health issues, eventually succumbing to paranoia and starvation. Turing, on the other hand, played a crucial role in breaking the German Enigma code during World War II, contributing significantly to the Allied victory. Post-war, Turing advanced the development of early computers and explored artificial intelligence. Tragically, he faced persecution for his homosexuality, leading to his untimely death.

References:

Complexity: A Guided Tour – Melanie Mitchel

YARPP List

Related posts:

1. Chapter 5: History’s Biggest Fraud (Sapiens)
2. How to Fail at Almost Everything and Still Win Big Summary (7/10)
3. Chapter 7: Sigmund Freud and Psychoanalysis (The Discovery of the Unconscious)
4. The Glass Cage Summary (6/10)