3 ms·
Turing completeness may not be that important in everyday programming, but it's at the heart of CS just like (to pick a lame example) conservation of energy is
by fh 18y ago
Turing completeness may not be that important in everyday programming, but it's at the heart of CS just like (to pick a lame example) conservation of energy is at the heart of physics.
What still baffles me about Turing completeness is how ubiquitous it is. Everything from Conway's Game of Life to C++ template specialization to Ruby is Turing complete. Only the latter has been explicitly designed for general computation; for the others, it just "emerged". It's almost as if Turing completeness is an aspect of nature, and it takes work and artificial restraint to design an interesting, powerful mechanism that is not Turing complete. I find that fascinating.
- xenophanes 18y agoYes. How many systems 'jump' to universality when they start getting powerful is one topic of David Deutsch's upcoming book The Beginning of Infinity. (BTW it happens in other fields too, not just computing.) While waiting for that new book, I recommend reading his previous book The Fabric of Reality.