mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-08-30, 22:31   #1
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default 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?
Orgasmic Troll is offline   Reply With Quote
Old 2005-08-31, 19:26   #2
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

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.
Orgasmic Troll is offline   Reply With Quote
Old 2005-09-01, 00:35   #3
ColdFury
 
ColdFury's Avatar
 
Aug 2002

1010000002 Posts
Default

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
ColdFury is offline   Reply With Quote
Old 2005-09-01, 04:42   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
question: decidability for quadratic residues modulo a composite 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.