 mersenneforum.org > Math a question on decidability
 Register FAQ Search Today's Posts Mark Forums Read 2005-08-30, 22:31 #1 Orgasmic Troll Cranksta Rap Ayatollah   Jul 2003 641 Posts a question on decidability Alice is working on the Frickenhaard Conjecture and mentions it to Bob. Bob wonders if the Frickenhaard Conjecture is even decidable and starts working to determine if it is or not. Charlie hears what Bob is working on and starts working to see if Bob's problem is decidable. After several pots of coffee, Charlies proves that Bob's problem is undecidable. First off, can you prove that determining the decidability of a problem is undecidable? If so, in the above situation, should Alice continue her work on the Frickenhaard Conjecture?   2005-08-31, 19:26 #2 Orgasmic Troll Cranksta Rap Ayatollah   Jul 2003 641 Posts Could someone give me a general method of attack for proving a problem decidable or not (or a resource that would have such a write-up)? Right now, I'm operating on the "..and then a miracle happens" level of understanding.   2005-09-01, 00:35   #3
ColdFury

Aug 2002

1010000002 Posts Quote:
 Originally Posted by TravisT Could someone give me a general method of attack for proving a problem decidable or not (or a resource that would have such a write-up)? Right now, I'm operating on the "..and then a miracle happens" level of understanding.
Assume that you have an algorithm to solve the problem and then show that using that algorithm you can solve the halting problem*. Since the halting problem is known to be undecidable, no such algorithm to solve your problem can therefore exist.

(* Can actually be any known undecidable problem)

Last fiddled with by ColdFury on 2005-09-01 at 00:36   2005-09-01, 04:42 #4 Zeta-Flux   May 2003 7·13·17 Posts TravisT, To answer your first question: I *think* the answer is yes, BUT only in inconsistent systems. To show undecidability, Charlie has to have *proven* that EVERY algorithm Bob could try to answer his question will ultimately fail. But what that means is, in fact, all the algorithms Alice might try will also ultimately fail (because they will also be algorithms that would answer Bob's question). So Charlie has had to show that in fact Alice's question is undecidable, and hence Bob's question is decidable, contradicting Charlie's answer! Let me put that a different way. If Charlie's answer is correct, then he has proven that every algorithm to answer Bob's question will fail to answer Bob's question. Suppose that there exists an algorithm A that answers Alice's question. Then, A is an algorithm that will also answer Bob's question (since A shows that Alice's question is provably solvable, and hence is decidable). Charlie's proof implies that such an A cannot exist. And therefore Charlie's proof actually shows that there is no algorithm to answer Alice's question. But that means the answer to Bob's question IS decidable (by Charlie's proof) contradicting Charlie's answer that Bob's question was undecidable. So, Alice should double check Charlie's work. If it is correct, she is working in an inconsistent area of mathematics. So, one might say, "While it is true that there are statements which one cannot decide whether they are decidable or not, one cannot *prove* that any given statement is such a statement because such a proof, of necessity, would tell us the statement is undecidable." (For those logicians out there, please feel free to correct me if my logic is off!) ========================== On your second post, ColdFury gave a good idea. One can also show undecidability by showing something slightly stronger, namely *independence*. This involves model theory. Basically, you construct a model where the statement is true, but at the same time INSIDE your model is another model where the statement is false! For a basic introduction, you might see the proof that the parallel postulate is independent of the other geometrical axioms in Euclid's theory. Best, Pace  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Math 18 2017-09-16 14:47

All times are UTC. The time now is 07:25.

Wed May 12 07:25:06 UTC 2021 up 34 days, 2:05, 0 users, load averages: 1.62, 2.00, 1.90