Edmund Harriss describes an interesting pattern he sees in mathematics and constructivist art in his interview on Strongly Connected Components. For most of history, mathematics and art have been fairly direct abstractions of physical reality. Then in the 20th century both became more and more abstract. But then a sort of reversal took place. After reaching heights of abstraction—Harriss cites Gödel and Picasso as examples—both mathematics and art began to apply abstractions back to the physical world.
… starting from clearly abstract structures and building something real from the abstract rather than abstracting something from the real. … You have models that you can then apply to the world rather than models you took from the world.
Stephen Wolfram has an analogous idea about computer programs. Until now we have written programs to solve specific problems. Wolfram suggests we reverse this and explore the space of all possible computer programs. As he demonstrates in his magnum opus, simple programs can have surprisingly complex behavior. We may be able to find some relatively small but useful programs that way.
As Edmund Harriss alludes, people have successfully applied very abstract mathematics, mathematics developed with no physical application in mind, to physical problems. I’m more skeptical of Stephen Wolfram’s proposal.
Suppose you find a program that appears to solve some problem, such as optimally controlling a nuclear reactor. How do you really know what it does? You didn’t write it; you found it. It wasn’t designed to solve the problem; you discovered that it (apparently) solves the problem. Wolfram is optimistic that we could discover programs that we might never be able to write. But a program that powerful would likely also be impossible to thoroughly understand.When Wolfram says “Look what interesting behavior tiny programs can have!” I think “Look how hard it can be to understand arbitrary programs even when they’re small!”
Computer science might not be that helpful in determining what a found program does. It is theoretically impossible to write a program that can always determine whether another program stops. We would have to study the program empirically. This process would be more like squeezing an extract from some plant root and testing its medicinal properties than designing drugs.
Related post: What does this code do?
Whoa! Slow down there. I suggest you look at modern research on type systems, especially dependent typing. Type systems sound mundane but they are evolving into extremely powerful tools for making static guarantees about arbitrary constraints in your program. Sure you can’t solve the halting problem but that doesn’t mean you can’t make other complex guarantees about your program. Can we develop a type theory for cellular automata? That’s an interesting research question, but I’d hardly say the state of affairs is as grim as you make it sound.
Shrutarshi: I look forward to seeing what progress can be made along the lines you discuss. In the mean time, here’s a three-line program that no one understands well.