Ulam Lectures - Cris Moore - Limits of Computers in Science and Society Part 1

Explore the fundamental limits of computation in this thought-provoking lecture from the 2018 Ulam Lecture Series at the Santa Fe Institute. Delve into the mathematical structures that determine problem complexity, from easy to hard to impossible, as SFI Professor Cristopher Moore examines the nature of computational challenges. Discover analogies between computation and evolution, and journey from simple puzzles to universal computation, Turing's halting problem, and the essence of mathematical truth and creativity. Gain insights into how computers tackle vast solution spaces, why some problems are quickly solvable while others remain intractable, and the implications for science and society. Engage with concepts such as Hamiltonian paths, complexity classes, paradoxes, and the foundations of artificial intelligence in this comprehensive exploration of computational limits.

Introduction
Hamiltonian Paths
Polynomials
Exponential Legend
Greedy Algorithms
Landscape
Local Optimum
Fitness Landscape
Hamiltonian Path
Complexity Classes
Possible Problems
Bits
And or gates
The 4colormap theorem
Im stuck
Cat Puzzle
Computing in Disguise
Impossible Problems
Crimefighting Team
Paradoxes
Empanada
The Barber
Julia Robinson
Alan Turing
Turing Patterns
Artificial Intelligence
Halting Problem
Prime Numbers
Odd Primes
Turings halting problem
Twisty mobius
strawberries and cream