Lemmata

Shocking fact: computers can’t do everything.

I know, I know, all of those years living in delusion. But get up off the floor, it’s not that bad. You see, what a computer can’t do tells us at least as much about the computer as what it can do. Actually, to be more exact, what a computer can’t do is the exact opposite (the complement) of what a computer can do, so the two things delineate the same boundary. By knowing the limitations on a computer’s power, I feel like I know much more about it than if you gave me a list of 100 things the computer actually can do.

For example, an extremely simple type of computer called a finite state automaton can be devised to do things like recognize all sequences of letters that end with the letter ‘z’, or that have five ‘a’s in a row. But, strangely, a finite state machine (that’s another name for finite state automaton) cannot do something so simple as telling you whether that sequence of letters has the same number of ‘a’s and ‘b’s in it. Weird.

For each more sophisticated type of computer, there is a well-defined limit to its ability to solve problems. Usually this is demonstrated using a fancy proof called a lemma. These lemmata are learned and utilized by computer science students the world over. An interesting question resulting from this observation is whether the human mind has a similar limit. In other words, is there a problem that a human being, using reason alone, could not solve even with unlimited amounts of time and an infinite ability to remember things (and an infinite desire to just sit there crunching numbers)?

I’ve been discussing what’s known as computation theory. A related field, known as computational complexity theory, has similar implications. Rather than focusing on what a computer could theoretically compute with infinite time and memory, complexity theory focuses on how much time it takes to solve different problems. It turns out that many problems fall into a few basic classes, namely Polynomial (P), Non-deterministic Polynomial (NP), and NP Complete (NP-Complete). (For WAY more than you ever wanted to know about this topic, check out Stanford’s Complexity Garden and “Petting Zoo“.)

I wouldn’t be at all surprised if human rationality, as its own special type of computer, runs into similar limits of complexity and computability. In “So Open It’s Closed” we ran into the difficulty of proving that genocide is bad, and yet the vast majority of human beings (myself definitely included) would agree that it is. What would happen if everybody took that lack of proof to heart and just went about rampaging and slaughtering the ethnic group that most recently got on their nerves?

I consider this wall—against which human rationality can pound its head forever but never demonstrate anything—to be good evidence that our rationality is bounded. Not just in the sense of making expedient assumptions about things in order to save time and energy, but rather in the sense of what we can figure out over the long haul if we really put our minds to it. There’s a limit. We can see beyond it to a wider world around us, but we can’t quite escape from our complexity class prison, so most people just make long-term assumptions, assumptions which are vital to the development of both individuals and civilizations.

Revealed religions claim a source of knowledge—a means of proof—other than human rationality. Western philosophy and folk argument frequently make claims that cannot be substantiated rationally, and yet are still believed in. Ultimately, whether people like it or not, beliefs in something nobody can prove keep us from destroying each other!

Belief people “are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness” would have steered humanity around such profound disasters as the Holocaust, Stalin’s Gulag death camps, the Chinese Cultural Revolution, the needless slaughter of European conquest in the Americas, etc. I see this as a support of the validity of those who teach such morals, especially Christ and the prophets, and a support of the necessity of seeking out “[our] Creator” in order to reach beyond the limits of our own rationality.

There’s much to see, and I hope to see it. No finite state machine ever aspired so.