The beauty of physics lies in its precise statements, and that is what is essential to convey.I can't speak for physics but I couldn't disagree more when it comes to computation. It's nice we have formal models, like the Turing machine, for that gives computation a firm mathematical foundation. But computation, particularly a computable function, transcend the model and remain the same no matter what reasonable model of computation or programming language you wish to use. This is the Church-Turing thesis, exciting exactly because it doesn't have a formality that we can prove or disprove.
Likewise the P versus NP question remains the same under any reasonable computational model. Russell Impagliazzo goes further in his description of his world Algorithmica.
Algorithmica is the world in which P = NP or some moral equivalent, e.g. NP in BPP [probabilistic polynomial time].In other words the notion of easily finding checkable solutions transcends even a specifically stated mathematical question.
That's why I am not a huge fan of results that are so specific to a single model, like finding the fewest number of states for a universal Turing machine. I had an email discussion recently about the busy beaver function which I think of in general terms: a mapping from some notion of program size to program output as opposed to some precise definition. I find the concept incredibly interesting and important, no one should care about the exact values of the function.
We need the formal definitions to prove theorems but we really care about the conceptual meaning.
Maybe that's what separates us from the physicists. They want precise definitions to capture their conceptual ideas. We want conceptual ideas that transcend formal definitions.
Very nice, succinct, and articulate essay! I am mostly with you.
ReplyDeleteOne question, though: what you've said works nicely in the realm of computability (Church--Turing thesis) or even feasible computability (polynomial-time version of the C--T thesis). Does it work equally well when we speak of efficient computability? Our own notions of efficient has probably undergone changes over the past couple of decades, with the underwhelming progress in massively parallel (think SIMD) computing, surprising progress on "simple" distributed computing (MapReduce, Hadoop type stuff), streaming and sketching computations, etc. If somebody asks me the question "is maximum matching efficiently computable?" I am not sure I have a clear answer. Is that due to lack of sharpness in our models? I don't know.
Stephen Fenner and Lance Fortnow recently published a nice, sweet and short paper of barely 10 pages with the title "Compression Complexity". In section 2 Preliminaries they define a function BB(m) and a program p_m of length at most m which encodes BB(m). At least for me, the way they used the program p_m as a practically usable encoding of the natural number BB(m) felt very illuminating. This goes beyond the ideas I previously associated with the busy beaver function.
ReplyDeleteTheir encoding directly uses the time (i.e. the number of steps) till the Turing machine halts, but if we want to encode all natural numbers (and not just BB(m)) in such a practically useable and compact way, then it seems helpful to modify the precise definition of the Turing machine slightly. We give it an additional NOP operation (from the perspective of the Turing machine itself), which tells us to switch between counting the steps and not counting them. The default state (before the execution encounters the first NOP operation) is to count the steps. Now it is easy to produce encodings of N+1, N+M, N*M, and "1 if N<=M and 0 otherwise" from encodings of N and M. Even encodings of "logical formulas involving natural numbers and bounded quantification" giving 1 if they are true and 0 otherwise should be possible (if I am not mistaken).
But this elaboration already tries to leave the domain of computation and enter into the realm of logic, so it may be no surprise that precise definitions become desirable there.
Surely Lisa’s comment was intended to draw a distinction between science and the arts; when scientists make unsubstantiated claims or express hunches, they should be clear, especially when deviating substantially from what others in their field believe. I haven’t read Rovelli’s book, nor would I recognize such digressions, but it seems he took liberties that fall more on the artistic side of the divide than any of us would be comfortable with.
ReplyDelete> Maybe that's what separates us from the physicists.
To the contrary, leaps of faith and the desire to find general truths pervade physics. An example is the concept of “universality,” which takes notions like the equivalence under any reasonable computational model you write about to a whole new level. Yet we all can (and should) be precise and accurate about distinguishing what is known, believed, hoped for, or plausible.
I would also like to disagree somewhat with Lance. It is easier to do this if one adopts a Platonic stance: the great conceptual ideas exist out there. What we want is precise definitions that capture them. This is analogous to the physicists desire to capture the universal laws that the world obeys.
ReplyDelete