Undecidability is weird, much weirder than quantum theory, which is benign by comparison. Let me give a simple example for something that may well be undecidable:
Take any natural number N. If it is even, divide it by two. If it is odd, then first multiply by three and add one before you also divide by two. This gives you a new number N1 which is either N/2 or (3N + 1)/2. Now repeat the same procedure over and over again, i.e. look at whether N1 is even or odd and get either N2 = N1/2 or - well you know what.
The about 60 years old Collatz conjecture by the German mathematician Lothar Collatz is the proposal that all numbers will result at some point in the number 1 via the just described procedure. Start with 11 for example: N1 = 17, N2 = 26, then 13, 20, 10, 5, 8, 4, 2, and finally 1, as promised. The number N = 27 will at some point grow to 4616 before finally reaching 1.
Nobody knows any counter example to this conjecture, but there is also no proof of it. There is a new claim of a proof spooking the media, but it is only a claim rather than a proof according to sober experts.
If you cannot prove it, then obviously you can never be sure of whether there is not some large number for which the procedure does not lead to 1. Maybe there is a number where the procedure leads to N itself after a number of iterations, thus cycling for ever instead of ending at 1.
The really intriguing aspect is: There is a generalization of this conjecture that is proven to be undecidable. Although the Collatz conjecture itself is not yet proven to be undecidable, it may well be. What would be weird about that?
Lets imagine for a moment that we have a conjecture C, one just like the Collatz conjecture, that claims “C is true for any number N”. What does it entail if it is proven to be undecidable, meaning that one can neither prove nor disprove this conjecture?
If you cannot prove it, then obviously you can never be sure of whether there is not some large number for which the conjecture is wrong. However, if there were even just one such number found, and it could be found any day if it existed, then obviously the conjecture would be disproved and thus decided. But undecidability is already proved, so this cannot happen. A counter example cannot possibly be found. However, this fact in turn is the proof of the conjecture itself, because it is precisely what the conjecture claims: that there is no such example where C is wrong.
So the undecidability kind of decides it although the undecidability itself is of course the proof that it cannot be decided. You may and should suspect that something here is impossible or plain wrong. Undecidability proofs are solid proofs, but they do tell us something about truth.
Much like quantum physics tells us that there is no naïve reality just decided “out there” in front of the door or our eyes, so undecidability teaches similar lessons about truth - well at least that it is a lot less "either this or that, period!" than we would like to believe.
Undecidability and related non-computability may be important at the very basis of fundamental physics, for example, at least according to Roger Penrose, whenever gravity may bring nonlinearity into quantum mechanics. These types of suggestions are at least from one perspective promising:
Generalizing the Collatz procedure to the complex plane results in the Collatz fractal, which reminds of the Mandelbrot set. Given the nature of related problems, undecidability is certainly suggested (not proved). These structures are the same in any universe – there is no multiverse of different mathematics as there may be for different viable physics. This may have deep implications for how we think about the universe if non-computability turned out to be a vital ingredient of fundamental physics.
Quantum mechanics has disproved local realism, a lay-person accessible proof of that you can find here. Crackpots insist on local realism, while most physicists insist on non-local realism, but the latter does not deal much better with the “weirdness” of quantum physics. The perhaps most advanced but unpopular is antirealism.
Undecidability/non-computability in physics is mostly put out by people who kind of like to keep the realism, as Roger Penrose does as far as I can tell (what else would “objective reduction” be motivating or motivated by). However, our ever finding non-computable physics would prove antirealism, which I will get back to at some point hopefully soon, so stay tuned.