Incoming links: Undecidable problem
A:
- decidable problem is to a decision problem
- like a computable problem is to a function problem
The canonical undecidable problem.
One of the most simple to state undecidable problems.
The reason that it is undecidable is that you can repeat each matrix any number of times, so there isn't a finite number of possibilities to check.
Ciro Santilli intends to move his beauty list here little by little: github.com/cirosantilli/mathematics/blob/master/beauty.md
The most beautiful things in mathematics are results that are:
- simple to state but hard to prove:
- Fermat's Last Theorem
- transcendental number conjectures, e.g. is transcendental?
- basically any conjecture involving prime numbers:
- many combinatorial game questions, e.g.:
- surprising results: we had intuitive reasons to believe something as possible or not, but a theorem shatters that conviction and brings us on our knees, sometimes via pathological counter-examples. General surprise themes include:Lists:
- classification of potentially infinite sets like: compact manifolds, etc.
- problems that are more complicated in low dimensions than high like:
- generalized Poincaré conjectures. It is also fun to see how in many cases complexity peaks out at 4 dimensions.
- classification of regular polytopes
- unpredictable magic constants:
- why is the lowest dimension for an exotic sphere 7?
- why is 4 the largest degree of an equation with explicit solution? Abel-Ruffini theorem
- undecidable problems, especially simple to state ones:
- mortal matrix problem
- sharp frontiers between solvable and unsolvable are also cool:
- attempts at determining specific values of the Busy beaver function for Turing machines with a given number of states and symbols
- related to Diophantine equations:
- applications: make life easier and/or modeling some phenomena well, e.g. in physics. See also: explain how to make money with the lesson
Good lists of such problems Lists of mathematical problems.
Whenever Ciro Santilli learns a bit of mathematics, he always wonders to himself:Unfortunately, due to how man books are written, it is not really possible to reach insight without first doing a bit of memorization. The better the book, the more insight is spread out, and less you have to learn before reaching each insight.
Am I achieving insight, or am I just memorizing definitions?