One does not simply study Computational Complexity

Last night, I ran into an interesting question on Complexity while surfing the Internet. Here it is:

Let A be the language containing only the single string w where: w = 0 if God does exist and w = 1 otherwise. Is A decidable? Why or why not? (Note: the answer does not depend on your religious convictions.)

So what’s the proof. I come up with my proof that A is undecidable.

Consider a Turing Machine M used to decide A. If A is decidable, the Turing Machine M will stop and output God, the supreme being, in the output tape.

Forget about religious viewpoint, from logical point of view, let’s assume that God is the supreme being, who holds the most super power and can create anything. So, where does God come from? There must be another supreme being, who created God. The Turing Machine M, therefore continues working to output The One, who created God. But then, who created The One? Turing Machine M definitely enters infinite loop seeking for the original supreme being. Thus, A is undecidable.

Hey, does the proof sound familiar? Of course,  it’s an analogue version of Turtles all the way down. In case you’ve never heard of this philosophical story, here is one of those version, found in the first page of my book Plato and a Platypus Walk into a Bar, Philogagging chapter.

Dimitri: If Atlas holds up the world, what holds up Atlas?
Tasso: Atlas stands on the back of a turtle.
Dimitri: But what does the turtle stand on?
Tasso: Another turtle.
Dimitri: And what does that turtle stand one?
Tasso: My dear Dimitri, it’s turtles all the way down!

Advertisements

One thought on “One does not simply study Computational Complexity

  1. Hey! I am complete noob so please bear with me. I live with the belief that we need to step out of the universe to understand this idea of turtles all the way down. What I mean is that you cannot identify the color of a house unless you are outside it right? (or if you can prove that the windows offer a complete view of the house :) This belief is similar to Godel’s incompleteness theorems and I think your language A is but an expression of this. What do you think? Am I echoing an established idea? (I am complete noob with respect to complexity theory and hence will be starting grad school this fall :) Nice post!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s