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!