Vladimir Arnold on experimental mathematics

I'm happy to find that another big name mathematician, Vladimir Arnold, is a sympathizer of experimental mathematics.

Here's "On Teaching Mathematics"

Mathematics is a part of physics. Physics is an experimental science, a part of natural science. Mathematics is the part of physics where experiments are cheap.( Read more... )

V.I. Arnold

Is P Versus NP Formally Independent?

Scott Aaronson's Is P Versus NP Formally Independent? is interesting.

My feeling is that it couldn't go the way of the Continuum Hypothesis, because if P=NP, then there is an algorithm that we can find. The CH, OTOH, does not entail the existence of anything concrete, whether it's assumed to be true or false.

P=NP
<=>
exists P-time-algorithm a ( a solves SAT )

in other words:
P=NP
<=>
exists algorithm a, polynomial function f ( forall inputs i ( a halts after no more than f(size(i)) steps, outputting the answer to whether i is satisfiable) )

This is a Sigma_2 statement about Turing Machines. This means that it has an objective meaning, and must therefore be true or false. I suspect this also means that ZFC can decide it (if it can't, then ZFC is not "meaningful-statement complete", which is a bad thing).

The CH is a Sigma_n statement (maybe it can also be considered Pi_n, if there is no standard way to push negations), but it's not about Turing Machines. This means that the meaning of CH, to the extent that it has one, is dependent on "non-computable" axioms.

Can anyone help me formalize this argument?

Reading Section 6 ("Conclusion"), I see that Aaronson discusses this argument I just made, agreeing with it (but not formalizing it):

But in one crucial respect, P = NP is not at all like CH. It’s a Pi_2-sentence. It refers, not to a transfinite realm beyond human experience, but to machines, Boolean circuits, 1’s and 0’s.
Here’s a simple argument for why, if you accept the physical process criterion, then you should accept
that any Pi_alpha-sentence has a definite truth-value.
...

---

Aaronson's paper seems to suggest that formalization can't make a proof more credible. I disagree with that, of course, but maybe I read too much into what he said and made a straw man.

via patrissimo, I found this very nice post that debunks "hypercomputation".

going Bayesian

I'm now trying to show that ICA is totally useless for the Gaussian case. The idea being that ICA does not test for conditional independence.

Apparently, Peter has been imagining otherwise, since in the Gaussian case, a regression coefficient being close to 0 implies conditional independence.

I really pushed for my idea of Bayesianizing ICA, in order to deal with the more general case in which the structure of the problem is a general multi-level DAG, instead of the Cocktail Party Problem (CPP). He finally agreed that I could be right. To make sure, I'm now going to evaluate ShimizuSearch against a new method I'll name StupidSearch, which just spits out a random graph (OR an empty graph OR a random full DAG).

However, I'm still intending to follow his suggestion of studying multiple-indicator graphs and whether it's possible to get a unique maximum-likelihood latent values for each data point; and to read economics literature that uses time series.

Some ideas of where to look for linear systems:
* electrical circuits (we could apply this to debugging of circuits)
* traffic flow at large temporal scale (e.g. > 1 day)
* water flow in rivers and streams
* economics (no reason to be linear, but no-one will complain, since they've always been making the linearity assumption)