20050830, 22:31  #1 
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? 
20050831, 19:26  #2 
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 writeup)? Right now, I'm operating on the "..and then a miracle happens" level of understanding.

20050901, 00:35  #3  
Aug 2002
101000000_{2} Posts 
Quote:
(* Can actually be any known undecidable problem) Last fiddled with by ColdFury on 20050901 at 00:36 

20050901, 04:42  #4 
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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 