Undecidability
Busy Beaver
In theoretical computer science, the Busy beaver game aims at finding a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.
- The Busy Beaver Frontier
- Busy beavers and Kolmogorov complexity
- Problems in number theory from busy beaver competition
- On Logical Depth and the Running Time of Shortest Programs
- The “paradox” of computability and a recursive relative version of the busy beaver function
- Relativizing an incompressible number and an incompressible function through subrecursive extensions of Turing machines
- The Busy Beaver Competition: a historical survey
- Busy beavers gone wild
- Bounds on the rates of growth and convergence of all physical processes
- Friedman’s “Long Finite Sequences”: The End of the Busy Beaver Contest
- Turing Completeness and Sid Meier’s Civilization
- Problems in number theory from busy beaver competition
Undecidability of learning
In the last few years a series of articles studied computable aspects of learning theory.
- 2023 - From Undecidability of Non-Triviality and Finiteness
- 2023 - Find a witness or shatter: the landscape of computable PAC learning
- 2023 - On Computable Online Learning
- 2022 - Private and Online Learnability are Equivalent
- 2022 - On characterizations of learnability with computable learners
- 2021 - On computable learning of continuous features
- 2020 - Decidability of Sample Complexity of PAC Learning in finite setting
- 2020 - On Learnability with Computable Learners
- 2017 - On a learning problem that is independent of the set theory ZFC axioms
- 2015 - PAC Learning, VC Dimension, and the Arithmetic Hierarchy
- 2013 - Learning theory in the arithmetic hierarchy
- 2008 - Statistical Learning of Arbitrary Computable Classifiers
Undecidability of tiling
Tiling is the task of covering the plane by matching shapes.
M. C. Escher is known for his tiling art.
Play with Tilings:
Introductory articles:
Undecidability - Slides, Tutorials
Tiling can be undecidable - as hard as the halting problem.
Undecidability - Articles
- Aperiodic tilings (tutorial slides)
- The Domino Problem of the Hyperbolic Plane Is Undecidable
- Hard Tiling Problems with Simple Tiles
- Undecidable Translational Tilings
- Undecidability and Nonperiodicity for Tilings
- The undecidability of the infinite ribbon problem
- Decidability and Periodicity of Low Complexity Tilings
- Perfectly quilted rectangular snake tilings
- Domino Snake Problems on Groups
Complexity - Articles
Quantification of undecidability can be given by Kolmogorov complexity.
Tilings and Groups
Tilings have a lot to do with symmetry hence the connection with groups.