# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## Poetry and Geometry: inside the donut

Nikolay Oleynikov was a Russian poet-absurdist. He was executed by Stalin’s regime in 1937. Here is my attempt to translate one of his short poems:

O donut, crafted by a baker!
You seem so simple, hiding secrets under cover:
The convoluted clockwork, the beauty of a flower.
A vulgar man will snap you in his hand.
He’s in a hurry for he cannot stand
Your rings. And, what a shame,
He’s bothered by the hole of mystic fame.
And we are contemplating donuts, their simple grace,
Like architecture of an ancient race,
Attempting to deduce or to recall
What this resembles all in all,
What all those curves are for, and what the circles mean, and all those ugmics?
In vain! The meaning of the donut is escaping us.

Well, it is really hard to study donuts without cutting them! I’ve been playing with Google SketchUp (a free 3D editor with a very intuitive UI, in case you didn’t know), and of course I couldn’t help contemplating some donuts.  Take a look at these cut tori:

The one on the left is a punctured torus. It demonstrates one of the mysteries of the donut (or rather of the torus): it has not one hole, but two. Let me explain what I mean. One of the holes is basically the interior of the torus. And the other one is what we call the donut hole. (And when we cut the surface, let’s not call those punctures and cuts “holes”, to avoid confusion). If you look at the punctured torus on the above picture, you can see that the two holes are no different.

The two other things in the above picture are tori with circular cuts. One of them is cut along a “parallel”, and the other one is cut along a “meridian”. These two cuts circle around the two different “holes”, but they both turn the torus into a cylinder.

But if those two holes are not different then how do we know that one of them is the interior? And how come one of those holes can be filled with yummy substance, while the other remains, well, a hole? What’s up with the donut?! This remains a mystery. (By the way, “untrue products” is an anagram of “punctured torus”)

It is well known that a punctured torus can be turned inside out.

Written by bbzippo

10/26/2011 at 10:02 pm

Posted in Uncategorized

## Hilbert’s 10th problem and incompleteness

The negative solution of Hilbert’s 10th problem is one of the most striking manifestations of the incompleteness of arithmetic. Undecidable propositions don’t have to look “paradoxical” like the Gödel statement. And they don’t have to involve unimaginably large structures like the Goodstein sequence.

There are undecidable statements that simply talk about existence of solutions of Diophantine equations.

The reason for that is even more striking: any question of the form “is there a natural number possessing the property P” can be formulated as “does this particular Diophantine equation have a solution”. Basically, any property of the natural numbers can be expressed as a polynomial equation. And we are not talking about some unimaginably huge polynomials here. First of all, they are effectively defined, i.e. we can really construct them. And also their size is bounded by some very reasonable constants. E.g. we know that we can use equations of the degree not greater than 4 with no more than 58 unknowns. Or we can limit the number of unknowns to 26 so we can use the letters of the alphabet, in which case we would need to allow the degree to go up to 24. Even 9 unknowns are sufficient, but then the degree would have to grow up to 1045 .

I can’t help noticing once again that arithmetic has way way more expressive power than we actually need.

Here is a nice paper by Yuri Matiyasevich which explains this stuff on a very popular level. Another text by Matiyasevich with a historical account of his collaboration with Julia Robinson.

The history of Hilbert’s 10th is as fascinating as its contents.

It is curious that Julia Robinson’s teacher was Alfred Tarski who strongly believed that there exist non-Diophantine enumerable sets. And Martin Davis who formulated the key conjecture was a student of Alonzo Church. Yuri Matiyasevich (who gave the final proof of that conjecture now known as the DPRM theorem) in one of his lectures mentioned that he had used the Russian word наглый to describe Davis’s conjecture. This word is actually much stronger than “bold”, it’s almost “arrogant-obnoxious-badass-bold”.

I find it remarkable that this astonishing solution of a genuine number-theoretical problem was achieved by logicians. BTW, the “P” in “DPRM” is Hilary Putnam who is more of a philosopher than a logician.

Wikipedia does a good job too. Here and here. One small addition. Some texts give the impression that the DPRM theorem solves Hilbert’s 10th “because undecidable sets are known to exist”. In fact we don’t need to know about undecidable sets or to invoke the halting argument. We can simply use the same Turing’s diagonalization trick as for the halting problem. Since we can enumerate all diophantine equations, we can diagonalize by feeding the n-th equation with n as the parameter to the “oracle”. Then, since the output is a diophantine set, its representation must be on the original list, and we can show that the “oracle” must lie…

Written by bbzippo

10/10/2011 at 6:11 am

Posted in math

## The chemistry Nobel Prize celebrates math

The discovery of quasicrystals is deeply rooted in math. Not only because it’s all about symmetries. It appears that aperiodic tilings were discovered (not by Penrose!) as a result of studying a decidability problem!

Written by bbzippo

10/05/2011 at 11:58 pm

Posted in Uncategorized

## Doubting the Consistency: infinite vs. unimaginably large

“The consistency of P remains an open problem.”

Ed Nelson.

“There was also a Beaver, that paced on the deck,
Or would sit making lace in the bow:
And had often (the Bellman said) saved them from wreck,
Though none of the sailors knew how.”

L. Carroll, “The Hunting of the Snark”.

So, how could anyone doubt the consistency of PA? Isn’t $\mathbb{N}$ a model of PA, which is almost “material” and can be used to verify the truth of all the axioms? And didn’t Gentzen prove the consistency of PA using induction up to $\varepsilon_0$, which is obviously true because it simply says that finite trees can be well-ordered?

If you believe in all those “true” and “exists” above (which most people and mathematicians do), then you have no reason to doubt the consistency of PA. But there are people who study foundations of math in more depth than regular mathematicians do. They learn that the structure of the natural numbers is far more complex and mysterious than even what Gödel uncovered. They run into stuff that makes them doubt all those “true” and “exists”. Or I should rather say, to doubt that the current established formalism justifies all those “true” and “exists”.

I’d like to give a few examples.

You can avoid Gödel’s Second Incompleteness theorem by doing away with the 2nd Hilbert-Bernays condition , which is so subtle that no one cares about it. And you don’t even need to change anything in PA, you just need to change the numbering in the proof of Gödel’s 1st Theorem. After that the formula “PA is consistent” will become provable in PA. That would be a slightly different formula than the G statement, but its meaning will be almost exactly the same. (I believe this was first noticed by Solomon Feferman). [this particular fact is not related to Nelson’s attempt to prove inconsistency, I just want to demonstrate how subtle the 2nd Theorem is]

For any n, you can easily define an inconsistent theory in which the shortest proof of a contradiction has the length of the order $2^{2^n}$ .

For any n, you can (not so easily) define an inconsistent theory in which the shortest proof of a contradiction has the length of the order $2^{2^{2}...^2}$ with exponentiation repeated 2n times. (The latter result is due to George Boolos, I believe). This number is so unimaginably large, that this theory would be consistent for all practical purposes not only of gods themselves, but of creators of creators of gods as well.

You don’t need no induction. For any computable property P of natural numbers, there exists a number B such that if $P(0) \wedge P(1) \wedge \dots \wedge P(B)$ then $\forall n : P(n)$. Seriously, it is always sufficient to check if the property holds for a finite segment of the naturals in order to prove that it holds for all naturals. But it is not possible to compute (derive in a mechanical manner) the numbers B or their upper bounds. Some lower bounds are known, and guess what – they are unimaginably large  (See http://en.wikipedia.org/wiki/Busy_beaver#Applications). See also this popular essay by Scott Aaronson http://www.scottaaronson.com/writings/bignumbers.html

Those are some of the facts that make me believe that there might be indeed something wrong with Peano Axioms. This believe is a reason to be excited and not a reason to be worried. I am not an ultrafinitist for two reasons: I believe in Church Thesis (and even more in the informal Church-Turing Thesis) and I think that to be an ultrafinitist one needs to possess way more knowledge about the Foundations of math than I do.

Written by bbzippo

10/03/2011 at 6:12 am

Posted in math

## Nelson withdraws his claim

Edward Nelson has withdrawn his proof of inconsistency of Arithmetic.

http://www.cs.nyu.edu/pipermail/fom/2011-October/015832.html

Written by bbzippo

10/01/2011 at 5:25 pm

Posted in Uncategorized

## Note on proofs of inconsistency

There are many discussions going on around the web in the wake of E. Nelson’s claim about inconsistency of PA . While I can’t contribute on a professional level, I’d like to make a trivial note:

Nelson is not trying to prove the statement “the theory is inconsistent” within the theory itself. Such a proof would not have any consequences regarding actual consistency of the theory.

I wrote about this more than once already: there are consistent theories that prove own inconsistency . The reason being that consistency is not a very strong condition. Consistent theories may potentially lie. Consistent theories cannot prove Π-falsehoods, but they can prove Σ-falsehoods. I outlined the relationships between consistency and soundness here.

Now, what Nelson is doing is really straightforward. He is simply deriving a contradiction within the theory. Not something like “0=1” of course (though if he is right, then a proof of “0=1” does indeed exist).

Stay tuned, to be continued…

Written by bbzippo

10/01/2011 at 12:13 am

Posted in math