Unsolvable Mathematics Problems.

Factual Questions
21

Incidentally, Goedel’s Incompleteness Theorem is actually really simple to prove; seeing this proof may, hopefully, wipe off the pseudomystical allure it is all too easy to misguidedly ascribe to the result.

The core idea is this: suppose Alice is a show-off, know-it-all who has an answer ready to go for any yes/no question you might want to toss at her. Let’s try and show that she has to get at least one question wrong.

One easy example is “What’s the opposite of Alice’s answer to this question?”. Obviously, any answer given by Alice to this will be wrong.

But you might object that it’s unfair to allow the term “this question” to appear in there. Alright. We’ll suppose Alice only works within a more restrictive language which doesn’t directly allow for such self-referential constructions. Can we still get the same effect by other means, by cleverly replacing “this question” by something else?

Yes, actually. For example, we can use “What’s the opposite of Alice’s answer to the result of substituting ‘What’s the opposite of Alice’s answer to the result of substituting _____ into its own blank?’ into its own blank?”. It’s a bit more longwinded, but it’s easy enough to see that it acts exactly the same way as the above question; once again, any answer given by Alice to this will be wrong.

[One alternative way to think about yes/no questions with blanks in them is as describing properties an object might have; for example, the question “Is ____ a male with children?” corresponds to the property of being a father. So, another way to formulate the above is as follows: let us say that a property-description is Alice-heterological if Alice says “No” when asked whether it holds of itself (for example, presumably “the property of being six words long” and “the property of being a palindrome” are Alice-heterological, while “the property of being seven words long” is not). A straightforward translation of the above paragraph yields that Alice cannot correctly answer the question as to whether “the property of being Alice-heterological” is Alice-heterological.]

What all did it take for us to be able to pull this off? Just that the language being used was capable of speaking about opposites in some way (e.g., logical negation), as well as about the question-answering method under investigation [specifically, a method purporting to be able to answer questions of the form “Does object X define a property which object Y has?”, where the two objects are of the same type]. Thus, we can basically conclude, no language L is capable of defining a method to correctly answer every question of the form “Does L-term X define a property which L-term Y doesn’t have?”.

For particular special languages (e.g., your favorite programming language), and particular definitions within those languages (e.g., your favorite mechanical theorem prover), this result has particular consequences, but it applies rather generally as well.

22

On the other hand, it’s also not really worth being treated as pillars-crumblingly strong, either; if Alice thinks she can eventually come to a definite position on any mathematical question put before her, nothing in Goedel’s theorem itself forces her to recant, any more than confronting “What’s the opposite of your answer to this question?” itself would [since, after all, the two are essentially equivalent]; if Alice’s response to the latter is that it is not a suitable “mathematical question”, then, presumably, she can legitimately have the same response to any attempt to formulate a Goedel-style statement for her (thinking her own positions to not be definable in whatever the appropriate language of mathematical statements is).

Not that I would myself take this perspective, mind you; just that it’s one which remains available for one who does want to adopt such a “We must know; we will know” worldview.

23

Yes, and the proof that this set of problems and the set of polynomial-time ones are not the same is a currently famous unsolved problem.

24

What’s the result of substituting ‘What’s the opposite of Alice’s answer to the result of substituting ______ into its own blank?’ into its own blank?

It’s this:

A: “What’s the opposite of Alice’s answer to the result of substituting ‘What’s the opposite of Alice’s answer to the result of substituting _____ into its own blank?’ into its own blank?”

Alice can’t answer A because it still has a blank that needs something substituted into it before it can be evaluated for truth.

Since this substitution process doesn’t end (once I do the substitution into the blank in A, I’ll still have a blank in the result of the process, and there will still be a blank in the next substitution result, and so on), Alice can’t answer the question.

Is that the idea?

If so, do we really need wording about opposites to Alice’s answers? Does the term “opposite” actually contribute anything to the unanswerability of the question for Alice?

-FrL-

25

Here’s a long list of unsolved problems in mathematics:

These are unsolved problems in the sense of being theorems that are generally suspected to be true (and are generally considered important), although no one has been able to prove them so far. They aren’t unsolved problems in the sense of being equations that no one can solve (which aren’t usually considered an important problems).

26

There still is no such thing as a truly random number generator, all current programs require a seed number for their algorithms to work on. A coin toss program for instance will generate odds incredibly close to 50 - 50 but they never will be 50 -50.

27

There can’t be such a thing as a random number generator program. By definition, a program is an algorithm and doesn’t produce random numbers. I don’t know what a coin-flipping program would be. A computer program doesn’t have any hands and can’t flip a coin.

28

Yes, but we could easily fabricate a metallic disc with “H” printed on one side and “T” on the other, build a waldo that would cause the computer to flip said disc, and write optical-recognition software that would cause allow the computer to determine which side hand landed facing upwards.

29

I wouldn’t call that a computer program in itself. I would call that a program that controlled a physical process. Arguably the physical process is creating random numbers, but the program certainly isn’t.

30

We can simplify the recognition routine by making one side of the disk so it will scatter and reflect a lot of light, and the other to absorb any light falling on it, and then we just need to find the disc and determine how much light it’s reflecting.

:smiley:

31

No need to look hard. Obviously we’re going to flip it in a tightly confined space, just enough so it has room to rotate freely while it’s flipping. We should also make the surface as dark as the non-reflective side of the coin.

32

That strikes me as a pointless distinction. All computer programs control a physical process. The program that controls my laptop converts my pressure on the keyboard into electronic impulses to cause particular outputs.

33

Lots of computer programs don’t control anything physical except for things inside the CPU itself. The program that reads your typing on your keyboard isn’t doing the typing by itself. The program isn’t generating what is being typed on your keyboard. In any case, without some outside physical process which is (supposedly) random, a program can’t create random numbers. A program is just an algorithm inside a CPU. It doesn’t create random numbers. A program can be used to monitor a physical process which can supposedly create random numbers.

34

The correct formulation is that “no deterministic algorithm can generate true random numbers”.

The Busy Beaver Function is something which is well defined, known to exist and yet is provably uncomputable.

35

Bonus points if you make it out of lego.

36

It’s true that A is “ungrounded” in that sense, but that’s not problematic for us. After all, Alice gives some answer, right or wrong, to every question, so, in particular, she does give some answer to the result of substituting “What’s the opposite of Alice’s answer to the result of substituting _____ into its own blank?” into its own blank. She does give some answer, and we are looking for whatever the opposite of that answer is.

Yes, because the problem which concerns us is not that A is “ungrounded”, but that the correct answer to A is automatically made into whatever the opposite of what Alice says the answer to A is. The wording of opposition ensures that Alice always answers A incorrectly.

If we left out the business about opposites, it’s true that Alice would have some potential freedom, as a result of the ungroundedness you’ve demonstrated; she might be able to correctly answer either “Yes” or “No” as suits her fancy, rather than being constrained to just one or the other by external conditions of truth. But we don’t want her to have even this freedom; we want to show that there is a question to which she cannot give any correct responses, no matter what she tries.

Going back to the original formulation with direct self-reference, compare “What is Alice’s answer to this question?” and “What is the opposite of Alice’s answer to this question?”. Both are equally ungrounded; trying directly to evaluate either results in un-ending recursion (at least, when we replace “Alice’s answer to” by “the correct answer to”). However, with the first, this just means that Alice can shoot out either “Yes” or “No” as she likes and still be right; her hand isn’t forced. But with the second, this becomes rather more problematically that Alice can’t say anything and be right; whatever she says is automatically the opposite of the correct answer, and therefore wrong.

37

Note, by the way, that there is still a correct answer to the question “What is the opposite of Alice’s answer to this question?”; it’s just that Alice cannot give that correct answer. Any other know-it-all could wait to hear what Alice says, and then reverse it, and so get the correct answer. But that other know-it-all also has an equivalent question that e cannot answer. No matter who claims to have all the answers, they cannot.

Of course, one could also have a specialized know-it-all. It might be that Alice is more modest, and only claims to be able to answer every question on a particular topic, and that topic is narrow enough that it doesn’t encompass questions like “What is the opposite to Alice’s answer to this question?”. One of the keys to Gödel’s theorem is that arithmetic is not a sufficiently narrow topic to allow for this: Any system sophisticated enough to encompass arithmetic must also be able to encompass questions like the paradoxical one asked of Alice.

38

Exactly, on both counts.

Well… if Alice uses an arithmetically definable method of answering questions (i.e., if the system being discussed is one which is itself arithmetically definable, then it cannot correctly answer all questions of arithmetic. So it must either say something false or fail to say something true.). But, as you note, it’s all language-relative; it’s not that there is no method of correctly answering all the questions of arithmetic. It’s just that the function which does so is not arithmetically definable (though, of course, it can be defined in some other language).

It’s true that Goedel’s Incompleteness Theorem is often stated in the particular context of arithmetic, but I think this is merely an unfortunately common red herring. Of course, one of the reasons people do it is because it is common to focus attention on what can be done by computer programs (taken to formalize the notion of “formal” itself), and it is straightforward enough to show that every computable function is arithmetically definable (for suitable notions of the language of arithmetic), so we see that there is no computable method of solving all the questions of arithmetic.

But that’s not the fundamental, interesting thing. The fundamental, interesting thing is that computer programs cannot correctly answer all the (negative) questions about computer programs, and arithmetically definable procedures cannot correctly answer all the (negative) questions about arithmetically definable procedures, and hyper-Martian definable methods cannot correctly determine everything about hyper-Martian definable methods, and so on. The fact that “computable” is subsumed under “definable in the first-order language of natural number addition and multiplication” is just a parlor trick on top of this, not something essential; it’s not like, if it had turned out that this subsumption failed, the theorem would be sapped of all vitality; we’d just talk about it directly in terms of computer programs and questions about computer programs, instead of referring to the latter by proxy through questions about arithmetic. Or, better yet, we’d keep the fully relative perspective around by default (not even thinking GIT had something essentially to do with computation and the corresponding notion of formality), only specializing to particular languages when particular applications called for it.

[It’s also worth noting that the effort of showing that “computable” is subsumed under “arithmetically definable” (for appropriate notions of arithmetic), is, while straightforward enough, also ultra-tedious, and for almost no gain in most applications of Goedel’s incompleteness theorem. Indeed, the simple argument with Alice that was outlined above can be considered a complete proof of Goedel’s incompleteness theorem in its general form; the additional ultra-tedious work regarding formal arithmetic establishes a separate, quite detached result, which just happens contingently to have been associated with the incompleteness phenomenon by the inertia of history]

39

To illustrate why I have come to dislike talk of “strong enough” and “too narrow” when it comes to the incompleteness/indefinability results: it is sometimes said that, for example, the first-order theory of natural number arithmetic with only addition (Presburger arithmetic) is too narrow for Goedellian phenomena to apply. After all, there exists an axiomatic theory which correctly answers all questions about Presburger arithmetic. Is this not in stark contrast to the situation with Peano Arithmetic (addition and multiplication)?

No. After all, there exists an axiomatic theory which correctly answers all questions about Peano Arithmetic too (we can always trivially take as axioms every true statement). It just isn’t a computable axiomatization.

But Goedelian phenomena applies equally well to both languages: the procedure which answers questions about Presburger arithmetic cannot, itself, be defined in the language of Presburger arithmetic, and the procedure which answers questions about Peano arithmetic cannot, itself, be defined in the language of Peano arithmetic.

As it happens, the language of Peano arithmetic suffices to define every computational procedure, while the language of Presburger arithmetic does not, so we see that questions in the language of Peano Arithmetic cannot generally be computably decided, while questions in the language of Presburger Arithmetic, as it turns out, can be computably decided, but, whatever; if Presburger arithmetic sufficed to define everything computable, we’d just talk a lot more about Presburger arithmetic. If arithmetic explicitly augmented with exponentiation was necessary, we’d talk a lot more about that. But all of this is orthogonal to the essential Goedelian phenomenon itself (indeed, computability itself is orthogonal to the essence of the phenomenon; the point is, no language is capable of defining a general procedure to answer negated questions in itself in a certain way, whether or not that language suffices to capture computability).

40

It occurs to me that perhaps there may be some question as to whether A is even actually a well-formed question in the language Alice is dealing with (after all, it only makes sense to ask A iff it makes sense to ask about the opposite of Alice’s answer to A, which occurs iff it makes sense for Alice to answer A, which occurs iff it makes sense to ask A, which …).

This can be clarified by explicitly noting that the language of phrases Alice responds to may contain nonsense and syntactically malformed gibberish in addition to legitimate questions; we still assume that Alice offers a “Yes” or “No” response no matter what she’s given, but this may involve her following a convention such as “Always say ‘No’ if the query nonsense”.

Incidentally, note that once we’ve set this convention, the question A is automatically meaningful (i.e., not nonsense), since it is now clear that it must make sense to ask A, since it must make sense to ask about the opposite of Alice’s answer to A, since it must makes sense to ask about Alice’s answer to A, since Alice answers all queries. Setting the convention just allows us to ensure that this bootstrapping of well-formedness is not, itself, a point of worry.