How can a math problem be unsolvable?
In: Mathematics
There is no such thing as an unsolvable math problem.
There is such a thing as an unsolved math problem. Usually, these problems require the invention of entirely new ways of even thinking about math to even generate the tools or framework you would need to solve the problem. Sometimes, the genius to see a way towards the solution before it exists is a bit beyond the mortals who have tried so far.
So, don’t think about it like “6×32+17 = ????” and just no one knows. It’s more like if I asked you “prove that there are no non-prime numbers larger than 10^17 that do not have at least 6 prime factors.” That’s a terrible example because I don’t know the extremely high-level math it would take to even know what the questions really look like (and in fact I once tried to look at the 7 unsolved prize problems and I literally couldn’t even understand the wikipedia pages explaining the terms they used to even summarize what the problem was), but they’re kind of like that in format just far more complex and far harder. The point is you’d have to learn some new things that the rest of humanity doesn’t even know yet in order to even develop a way to go about proving those things, and that’s just really, really hard.
1- The problem can have no solution(ex: “which natural number satisfies the equation 2 – 4 = x?)
2- The problem can be written in a form that makes no sense.
3- The problem can’t be solved with the definitions and axioms we have (this kinda falls in the same category of (2) )
4- The problem can’t be computed in a finite amount of time
There is also a different kind of unsolvable problem: one with infinitely many solutions. If you know x=4 then you can solve y=2*x.
However, you cannot solve y = 2*x + z because you do not know what z is. There are some cases where it is very difficult or impossible to know what z is making this problem unsolvable.
What is 2+2? Easy.
What is 4795736 + 74284759? Well that question is 8 times harder to solve.
Now imagine trying to add two numbers each with a trillion digits. It could take even a computer a while to do that.
With more complex formulas that’s sometimes what is happening, the complexity goes so high that you just don’t have the computer power available to solve it. Drag equations for example are computer limited. To a very significant degree.
I’ll assume that “unsolvable” and “unsolved” are effectively the same, as I am not aware of any problem for which we have a proof that it is solvable, but not a solution.
First of all, what is done in school as “maths” would be better described as calculating. While in higher years you might do some proofs, most of it is applying rules that you were told are correct.
In mathematics, you start with a set of Axioms, statements and rules that you consider true, and derive everything else from those. If you follow the rules correctly, than any statement you manage to arrive at is also true.
In this case, a “problem” is finding a proof for a statement or proving a stament is not true.
One example would be the [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture): You start with a any positive, whole number, if it is even, divide it by 2, if it is odd, multiply by three and add one. Then apply this rule to the resulting number. [relevant XKCD](https://xkcd.com/710/)
For all number we have tested, you will eventually end up at one, so it looks like this might be true for all numbers, but there are infinitly many numbers we have not tested yet (and there always will be).
So just continuing to test numbers might solve it, if we find one where this is not the case. Then we know for a fact that there is one number for which it isn’t true, therefore it cannot be true for all numbers.
The other option is that clever mathematicans figure out a way to apply the rules of maths to things we know are true in such a way that they end up at the statement above. Then we have the proof that it is true. Or they apply rules to that statement until they end up at a statement we know is wrong. Then we know that the statement we started at was wrong (proof by contradiction).
Until then, it is unsolved. And, as I said in the beginning, I do not know if we have a way of knowing wheter or not it can be solved, at all.
One example of how a problem can be unsolvable is [undecidability](https://en.wikipedia.org/wiki/Undecidable_problem).
When a problem is undecidable, it means there is no method (program, algorithm, formula, logical statement, etc) that will always lead to a correct answer. The most famous example is the [halting problem](https://en.wikipedia.org/wiki/Halting_problem) which Alan Turing proved to be undecidable: Given a computer program, determine whether the program halts at some point, or runs forever. Turing proved that there exist programs where it is impossible to determine a correct answer.
And this was huge. Because it meant that it’s possible problems like the [Goldbach Conjecture](https://en.wikipedia.org/wiki/Goldbach%27s_conjecture), or the [Collatz Conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture) are undecidable.
And with a little bit of work, using Turing’s result you can derive [Gödel’s results](https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems). Gödel proved that if mathematics is consistent, then it is incomplete: there will always be statements that are true but cannot be proven.
Mathematician here. The amount of bad mathematics happening in this thread is *extremely unsettling*.
There definitely do exist problems that are fundamentally unsolvable (not just unsolv**ed**). Do not listen to anyone who tells you otherwise. Godel’s incompleteness theorems state this explicitly.
To answer the OP:
It might help to understand that there are math problems that look *very* different from anything you would have seen in your high school (and potentially even early University) math classes. In high school pre-calculus and university intro calculus you learn how to do a bunch of different kinds of calculations. From 1+1=2 all the way up to finding the rates of change and computing integrals.
Mathematicians typically don’t do very many calculations. Instead, our interest focuses on a thing called *theorems*. A theorem is 1) a statement that is true and 2) requires mathematical proof. You may have heard about Pythagoras’s theorem: for a right angle triangle, the hypotenuse^2 = width^2 + height^2. This is a statement that is true. How do know its true? Someone proved it mathematically!
To prove something is true, you have to start with some other information that we know is also true. This could be theorems or a thing called *axioms*. Axioms are statements that we *assume* to be true, but we don’t require proof. Remember drawing points on graph paper in class? In geometry on flat paper (this is called Euclidean geometry), one axiom is that you can identify a point on the sheet of paper. Another axiom is that, if you have two points then you can connect them with a line. These statements are true, but we don’t really need to prove them, we just assume them.
So if you follow the chain of logic, all theorems are constructed using the basic axioms we assume. So the axioms we pick are really important. For a while, mathematicians were concerned with the minimum number of axioms needed to construct all of modern mathematics. How few assumptions can we make and still build all of the math we’re used to? (Spoiler alert: 10 gets you there. Although the 10th one is controversial). One set of assumptions that allows us to build all of math is called Zermelo-Fraenkel Set Theory (optionally including the Axiom of Choice, in which case we call it ZFC). If you look at the Wikipedia page for ZFC, it’ll show you the 9 axioms and then mention the 10th. These axioms are enough to be able to build all of modern math. Set Theory is usually a 4th year honours level university course, so you can imagine how much work goes into translating these axioms into everything else!
Now to answer your question! Godels incompleteness theorems (2 statements which are true and have been proven, mathematically) state: if an axiomatic system assumes enough axioms to be able to do arithmetic then there are statements in that system that 1) are true and 2) cannot be proven using those axioms.
In any field of math, we have axioms and do arithmetic. So in *every* field of math, there are statements that are fundamentally true but cannot be proven. This is what we mean when we talk about unsolvable problems. Mathematicians want to come up with things we think are true and then prove it. Sometimes the true things aren’t provable.
The object the problem ask you to find doesn’t exist. Generally only applies when the form of solutions you’re looking for is so general that it seems like it should exist.
That, in the most general sense, cover pretty much most sense of “unsolvable” problem. It includes:
– A solution doesn’t exist.
– An algorithm doesn’t exist.
– A proof doesn’t exist.
———————
First, let me explain how it is conceivable that there are unsolvable problems.
As a very basic example, imagine someone ask you to solve n^2 =3 where n is an integer. It’s easy to check that there are no solutions, so you just say there are no solutions.
What if the problem is slightly harder. Maybe they ask for rational n instead? Or maybe they ask for n being Gaussian rational? In each case, the question become harder and harder but you can eventually show that there are no solutions. All you need to do is to write down the form of n (say n=p/q or n=p/q+ir/s for p,q,r,s integers), then check the equations in these variables, and finally confirm that these equations have no solutions.
But now let’s up the difficulty. Supposed you’re asked to find a solution to x^5 -x+1=0 that can be written using rational numbers, arithmetic operations, and radical. What now?
It takes a lot more work, but it can eventually be solved that once again there are no solutions. That is, if you write down any numbers using rational numbers, arithmetic operations, and radical, then plug it in to x, you won’t get equality. But at this point, people generally said that the equation can’t be solved, unsolvable. Instead of saying it has no solutions. Why? Because the conditions “rational numbers, arithmetic operations, and radical” permits you to write out numbers with limitless complexity so people expected there to be a solution, so the fact that there is none put a damper to an entire approach. It’s hard to imagine how such a number even look like, much less how to prove none of them solve the equation, but the fact that x^5 -x+1=0 has no such solutions is as certain as certain n^2 =3 has no integer solutions. As an analogy, imagine you’re a bishop in chess standing on a black tile, you can make a lot of moves in very complicated manner, but no matter what you do you will never stand on a white tile.
But that isn’t the only type of solutions out there. Another well-known example is straightedge and compass construction. Once again, certain construction problem will ask for a construction procedure to produce a specific figure. The definition of a “construction procedure” also permit you to write very complicated procedure that it’s a bit unexpected when it turns out no matter how complicated they can be there are figure they can’t construct. Which is why those problems are also considered to be unsolvable.
Now, moving on to modern time. An “algorithm” is basically some program that can be programmed on a computer and always stop. Just a more complicated version of a construction procedure. And of course, certain problem ask for an algorithm: the problem want an algorithm such that for any input I the algorithm produce output O such that O satisfies some specific condition related to I. And once again, that endless potential complexity doesn’t mean there are problem they can’t solve. For certain problems, no matter what algorithm you try, it will always produce the wrong O, one that doesn’t satisfy the condition.
Now let’s go even more meta. Most math problem is basically a statement, and the problem is produce a proof that the statement is true, or the statement is false. But at a meta level, a proof is also an object with very specific form. A proof is just a string of logical symbol, arranged in a way that satisfy logical rule, start with a list of axioms, and end with the statement you want to prove. Proof can be extremely complicated, sure, but it still have limitation. Sometimes, it just so happen that there are no strings of logical symbols arranged according to logical rule that start at a list of axioms can end at either the statement nor its negation.
——————–
Second, let me explain how one can prove there are no solutions/problem is unsolvable.
For the simple example I provided at the beginning, it’s a matter of writing out the form of the solution, plug in and check. That seems easy enough.
For solving x^5 -x+1=0, what you need is an invariant. The bishop analogy is really good here. The color of the tile of the bishop is an invariant, something that can’t be change with a move. This is why, no matter how complicated the bishop move, it never changes its tile color, and so you can prove that there are tiles the bishop can’t move to. Similarly, here, you can show that there is an invariant associated with a number that can’t change by taking roots or doing arithmetic operations. That way, no matter what complicated number you get, this invariant holds. And solutions to x^5 -x+1=0 doesn’t satisfy this invariant.
The same method also works on straightedge and compass construction. If you want to look into it, it’s Galois group.
Next, we go to algorithm. As we allow our solution to have even more complexity, things get even more difficult, and the invariant method don’t work. In fact, we know very little about what algorithm are capable of, but luckily enough, this very fact allow us to know certain limitation of algorithm, by allowing an algorithm to defeat itself! Imagine yourself in the shoe of an oracle from Delta. If you tell some guy that he will fall into a river and die, he will just not come near a river, defeating your prophecy. Back to algorithm, this reason is why predicting what an algorithm do is difficult, but it’s also why there are no algorithms to predict what other algorithm do.
Next, onto proof. Proof is just as terrible as algorithm. They can potentially be too complicated for us to understand. In fact, this is why we never fully know if a proof doesn’t exist, instead we settle for “equiconsistency”, the idea that if we assume certain proof doesn’t exist, then some other proof can’t either.
Latest Answers