The Unexplained Intellect: The Importance of Computability
Theoretical Computer Science has a broader import than its name suggests. To appreciate it, remember what Turing proved: that a certain hypothetical machine would be able to compute every recursively definable function in a finite amount of time. If we supplement that theorem with a plausible assumption about physics then …