The Beauty of Computation

By March 17, 2017machinelearning

Lisa Randall wrote a New York Times book review of Carlo Rovelli’s Reality Is Not What It Seems with some interesting responses. I want to focus on a single sentence from Randall’s review.

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.

Source link