Problems 002
Thanks to Prof. Burton Dreben (Math 281, 1961):
Is there a {computer, computer program, algorithm, etc.} which solves the following problems, i.e., are these problems decidable in the metamathematical sense?
a) Are there 777 consecutive 7's in the decimal expansion of pi?
b) Is there exactly one God?
Or are one or both of these questions perhaps unsolvable?
Is there a {computer, computer program, algorithm, etc.} which solves the following problems, i.e., are these problems decidable in the metamathematical sense?
a) Are there 777 consecutive 7's in the decimal expansion of pi?
b) Is there exactly one God?
Or are one or both of these questions perhaps unsolvable?
First, an old fable, then the answer.
ReplyDeleteOne day, a man and a woman were riding in a hot-air balloon, and unfortunately they had completely lost their bearings in the wilderness. Fortunately, they spotted a man strolling through a field. They called out, "Where are we?" The man didn't answer immediately, but just before they disappeared over the trees, he shouted back, "You're in a basket hanging from a balloon!" Frowning, the woman sighed, "Just our luck, to have run into a mathematician." Her companion asked how she knew the man's profession. "Simple," she replied, "he thought carefully before answering, his answer was absolutely correct, and it was totally useless."
Without further ado, this very post will include a Python function that solves both these problems, with just one proviso.
q1="Are there 777 consecutive 7's in the decimal expansion of pi?"
q2="Is there exactly one God?"
def solve1(s):
if q1 == s:
return "no"
if q2 == s:
return "no"
def solve2(s):
if q1 == s:
return "yes"
if q2 == s:
return "no"
def solve3(s):
if q1 == s:
return "no"
if q2 == s:
return "yes"
def solve4(s):
if q1 == s:
return "yes"
if q2 == s:
return "yes"
By the law of the excluded middle (the applicability of said law to both problems being the proviso I mentioned), either solve1, solve2, solve3, or solve4 decides both of these problems correctly. Thus, an algorithm exists that decides these problems; then, by definition, they are decidable.
In general, all finite sets are decidable, all functions over a finite domain are computable, etc.
Also, I can right now give an explicit algorithm, not merely a trivial existence proof, such that, if P=NP, the algorithm decides a specific NP-complete problem in polynomial time. Does anyone else know this one?
Your answer is the one Dreben gave. You could see that he didn't think much of the student who asked. D., however, apparently being of a more economical turn of mind, made do with two functions, either of which he was prepared to use twice.
ReplyDelete"P=NP"? Don't know that one.