{"id":3723,"date":"2010-01-13T14:29:54","date_gmt":"2010-01-13T21:29:54","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=3723"},"modified":"2010-01-13T14:29:54","modified_gmt":"2010-01-13T21:29:54","slug":"on-the-turing-away","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2010\/01\/13\/on-the-turing-away\/","title":{"rendered":"On the Turing Away"},"content":{"rendered":"

“The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.”
– E. P. Wigner<\/em><\/p><\/blockquote>\n

Our universe, or at least our understanding of the universe, appears to allow us to see its naked underbelly only through the use of mathematical reasoning. As Wigner says about this state of affairs, we neither understand nor deserve this. On the other hand, I’ve come to believe, this observation can also be a huge aid in describing the world of theoretical computer science. There is no doubt in most people’s opinion that theoretical computer science is mathematics of a highly sophisticated nature (or, well, sophisticated to this lowly physicist.) But theoretical computer science, unlike pure mathematics unfettered in its abstract glory, at its core must be concerned with the practical applicability of its reasoning. Here by practical I do not mean contributing to the better good of software development (though this may be important for the well being, read salary, of the practioners) but that at its core theoretical computer science must be about computers that exist in the real world. On the one hand, this observation leads direction to quantum computing. To paraphrase Feynman: the universe is quantum, damnit, so we better make our models of computing quantum. But it also should influence even our most basic classical computational models. In this vein, then, I would like to attack one of the most sacred holy cows of computer science, the holy mother cow of them all, the Turing machine.
\n
\nThe formalized description of the Turing machine is, no doubt, a major tool in codifying a language for the world of computer science. Recall that a Turing machine, in its most basic form, consists of a machine of finite memory with an ability to read and write symbols on an infinitely long tape made up of memory locations as well as the ability to move up or down these locations. The basic operating step for a Turing machine consists of examining the symbol currently under its read\/write head, examining it’s internal state (of which there are only a finite number), and conditional on these two values, writing a new symbol on the current location and moving one direction on the tape. Such is the most basic model of a Turing machine. And there are many variations which are all “equivalent” to this model: Turing machines with multiple tapes, etc (wikipedia has a long list<\/a>.)
\nOkay, so what’s my beef with the Turing Machine? Well by now many of you might think I’m going to harp on the infinite tape. But no, not really, as long as the tape is always “extendable” this seems like a physically fine model (though don’t try to keep everything in one place or your machine might collapse to a black hole.) What really bothers me about this model is that it is not, or at least I don’t think it is, fault-tolerant. That is, if we consider a world in which errors occur: errors by the machine, errors on the data sitting on the tape, errors in moving, etc, then the Turing machine is most explicitly not fault-tolerant. This is really, in a sense, an old observation: in order to make a computation tolerant to errors one needs parallelism.
\nConsider, for example, a very long computation, the Turing machine starts, say, on one end of the input and starts hacking away. But the data stored on the tape in a galaxy far far away, is just sitting there, and subject to the ever present whims of the decay of data. Noise rates for digital information are low, but they are not, and for physical reason probably can never be, zero. Thus if you are looking at a very large computation (and after all, theoretical computer science is all about asymptotic limits), then by the time the Turing machine needs to get out to the galaxy and process the information, the information out there will have been randomized and thus the computation will go bad. In order to make a truly fault-tolerant version of computing, it is necessary to have parallel computational power.
\nBut wait, aren’t parallel Turing machines equivalent in power to Turing machines (for example, see here<\/a>)? The so-called parallel computation thesis<\/a> states that “Time on any ‘reasonable’ model of parallel computation is polynomially equivalent to sequential space.” But what is missed in such constructions is that while one can construct a sequential Turing machine simulation of a parallel machine, if the later is tolerant to errors, the former need not be. That is errors on the parallel machine, in simulation, appear as errors on the sequential machine which are not physical. The physical errors on the sequential machine will destroy the computation. Well at least that’s what I think is true, but IANACS (despite being in a computer science and engineering department), so does anyone have more insights into this? I’d love to be told this line of reasoning is wrong and all is well for traditionalan Turing machines.
\nWell okay, so because nature doesn’t seem to allow noise free computation, we shouldn’t consider the model of a sequential Turing machine as the basis of our theory of computer science. The model is, physically, an unattainable model. Instead what is needed is a model which allows for noisy computation and a high degree of parallelism. My claim is that this model can do things that a the traditional Turing machine with noise cannot do.
\nOkay, so well, perhaps you find this objection silly. “I’m a theoretical computer scientist, I can study whatever damn model I want.” True, true. I think that’s the first amendment of the computer science constitution. But then what you’re doing is mathematics, and not science: you’ve lost the connection to the real world. In the real world, Turing machines crap out, as far as I can tell, albeit at scales probably large enough to not have to worry about the Turing machine doing a good job capturing modern classical computing machines.
\nBut even more importantly, consider this. Perhaps one of the reason why it is so difficult to prove major separations in computational complexity theory (think P versus NP) is that theory has strayed too far from how the real world operates. I call this the physicist ego principle: mathematics chugs and churns at its best when it is related to the physics of how the universe operates. A case in point would perhaps be Ed Witten’s work on understanding the Jones polynomial of knot theory in terms of the topological quantum field theory. This is, indeed, a kind of inverse claim to the quote by Wigner at the top of this post:<\/p>\n

The miracle of the appropriateness of the language of physics for the formulation of the laws of theoretical computer science is a wonderful gift which we neither deserve nor understand (nor currently have a lot of evidence in favor of it, but lets just speculate.)
– the Quantum Pontiff<\/em><\/p><\/blockquote>\n

Okay, yeah, I’m off on the deep end here. But isn’t it kind of a beautiful dream?<\/p>\n","protected":false},"excerpt":{"rendered":"

“The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.” – E. P. Wigner Our universe, or at least our understanding of the universe, appears to allow us to see its naked underbelly only through the use … <\/p>\n

Continue reading “On the Turing Away”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[20,53,65],"tags":[],"class_list":["post-3723","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-physics","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/3723","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=3723"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/3723\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=3723"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=3723"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=3723"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}