Timeline for Completeness of a set of propositional formulas
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2015 at 14:48 | vote | accept | M a m a D | ||
| Feb 28, 2015 at 14:18 | comment | added | M a m a D | Yes, sounds I need a trick more than an algorithm! The examples I mentioned in the question was the problem of the last year. | |
| Feb 28, 2015 at 14:15 | comment | added | Joel David Hamkins | I see, you just have to solve one instance! So you don't need a general algorithm. The true meaning of the undecidability result is that one must be creative to decide any given instance---there is no general rote algorithm. | |
| Feb 28, 2015 at 14:13 | comment | added | M a m a D | I'll have PhD entrance exam in the next week and they ask the completeness of a set of formulas problem every year. sounds I should give it up! | |
| Feb 28, 2015 at 14:08 | comment | added | Joel David Hamkins | Inconsistency is semi-decidable, since we can find it by checking a finite part of the truth table and a finite part of the theory. Incompleteness looks to have complexity $\Sigma^0_2$, since a theory is incomplete if there is some $p$ such that the theory is satisfiable with $p$ and also with $\neg p$, and satisfiability is $\Pi^0_1$. I expect these bounds are sharp, and in this case, neither completeness nor incompleteness would be semi-decidable. | |
| Feb 28, 2015 at 13:59 | comment | added | M a m a D | You mentioned the Rice theorem. it says any non-trivial attribute of algorithms is undecidable. Undecidable means both semi-decidable which equals to recursively enumerable sets and non recursively enumerable sets. Semi decidable problems have an algorithm. I would like to know if this problem is semi-decidable is there any partial algorithm (partial function) to solve the problem? | |
| Feb 28, 2015 at 13:35 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |