Halting Problem and Computer Simulation of Real World


When I was a kid, I read about a story written by an Italian poet. It was about a kid stepping into a country where everybody has to spoke lies only everyday. While reading this story, I was thinking, “How can I come up with a sentence that is always a lie?” After a few thoughts, I found out that no matter how you respond to the line “What I say is false”, this statement will always be false. If this statement is true, then “I” am indeed saying something wrong; otherwise, this statement is false itself.

After I grew up and took Basic Algorithm course, I realized that this statement is somehow similar to Turing’s Halting Problem. The basic idea of Halting Problem is that no program can be written to predict whether other program will do an infinite loop. A key point of its proof is to provide a counterexample: when a program is written to do an infinite loop if it is predicted to be “halting”, else it stops, such program will always cause the predicting program to output the incorrect answer, no matter what algorithm is used by the predicting program. This is probably one of the most significant achievement I had accomplished in my childhood, and it is really a shame that no one else has witness my “achievement”. Anyway, things are always getting complicated when they bring themselves into the equation.

One thing that computer graphics programmers and artists are constantly trying to challenge is to simulate authentic graphics and effects. From concepts like particle-based modeling and brain in a vat, to movies like Matrix and Ready Player One, people always love to search for the idea that a plausible world can be simulated and people will get lost inside this mixed reality. Like these people, I think about these questions all the time. Can computer simulated particles be small enough in which they can simulate molecules, as computer hardwares evolve with such a high speed? Generally, can a computer simulate everything in a real world?

Sadly, the answer seems to be no. We can just bring the Halting Problem as a counterexample: could a computer simulate itself? To simulate a computer that is simulating itself, we have to simulate the simulation run by the computer that simulates itself, and simulate simulation that simulates the simulation… and, an infinite loop.

It is a discouraging answer, at least for me. As an artist and game developer, it is discouraging to realize that the world I am building is just a baseless dataset that could collapse anytime. Moreover, as someone who wants to do some useful researches to the Computer Graphics field, it is discouraging to find out that most researches done to make graphics more realistic by considering real-world factors are useless: why use an algorithm that takes so much time and resources to simulate and render the real world, while the same effect can be achieved by methods that are way more cheaper to render? Why simulating waves when the water surface pattern can be achieved by adding and multiplying noise function? Why simulating thousands of particles to render a fire when you can simply put pre-rendered textures together?

But this is not a rant from a discouraged person. Computer Graphics is a magic trick performed by programmers. They are never meant to simulate the real world, and we as programmers and researchers are only trying to trick our audiences to believe that they are real. The same thing has been emphasized by Ken when I take his class. This is a harsh truth that everyone who wants to do Computer Graphics has to know, but our job is to make less audiences to realize this harsh truth, and enjoy their time in Virtual Reality without spoiling the trick.

Back to the topic of whether simulation can be made to simulate the real world, I don’t think any computer is capable of doing such simulation; but, I do believe that our mind can do so. It is not that our brain can run the simulation code, but because the world we are perceiving is delivered through our brain using our perception ability, maybe someday we can hack such ability to deliver a simulated world. Then all the rules for Computer Graphics will not work, we will say goodbye to triangles, ray-tracing, PBR, etc.. I’ve always want to create my world using something that is described in movies like Inception and World Builder, but I guess I have to wait another 100 years to find out.

Leave a Comment

Your email address will not be published. Required fields are marked *