I am currently at the NKS 2010 summer program at the University of Vermont – a great experience as always, with lots of bright enthusiastic people. A topic of continual discussion is breaking our understanding of computation out of its “one countable infinity” frame. And not in the continuum infinity direction, but downward into finitude.
A system that bubbles around for a little bit and then resolves into just a few simple periodic structures, or straight lines running down the page, we call class 2 and dismiss as generally uninteresting. For short transients below any level of aggregation we can imagine mattering, this quick assessment may be merited. But extended indefinitely it collides with our actual experience – it is another way that one infinity over directs our thinking.
A bubbling computational system wanders around Vienna for a few dozen years and writes a few score symphonies. Then it goes remarkably stable. Ah, just a transient – class 2 behavior – uncomplex and therefore uninteresting, right? OK, how about a transient between a speck and a photon bath of non interacting light streaming about without interacting, eventually, that only took oh I don’t know, 100 trillion years to resolve?
If a transient is at least as long and interesting as you are, its temporal finitude is no reason to dismiss it – and if it is a material universe through all its immensities of space and time, its supposedly being spanned by your one imaginary countable infinity as a reason to dismiss it as uninteresting, is simply laughable.
Long enough and complicated enough transients matter. We can’t dismiss them, and if our notions of computation do not take them seriously, then our notions of computation are flat wrong and need to be revised.
Mathew Szudzik is fond of citing the Kalmar elementary or primitive recursive functions (PRF for short) as families sufficiently involved and powerful to capture practically everything we mean by computation, without crossing the threshold of universality, because they don’t have that one countable infinity. In programming terms, they have “Do” loops but not “While” loops. But how much can that matter, operationally and physically, in a transient actuality?
You have some practical computer and you know its operations speed. You want a “While” loop construct, but can only program with the PRFs. OK, so you do a little math and figure out an upper bound for the heat death of the universe in seconds, divide by your cycle speed, underprofile to pretend you can get off way more steps in your little routine than you ever actually will, and set the top of your “Do” iterator to that integer. Then put a “Throw” command inside the “Do” instead of a condition on the “While” you wanted to write.
It isn’t a While. It will provably halt. It can’t be universal. But then, no actual While running in your hardware in the actual universe will get any farther. So what operational difference can there be between them?