Completeness vs decidability

  • Thread starter EvLer
  • Start date
In summary, completeness refers to the ability to prove or disprove every statement in a system, while decidability refers to the existence of an algorithm that can determine whether a statement is valid or not valid within a finite number of steps. In some cases, a system can be both complete and decidable, but there are also cases where a system can be complete but not decidable. This is because completeness refers to proofs within the system, while decidability refers to an external algorithm that may not be able to access all aspects of the system.
  • #1
EvLer
458
0
I don't have a clear idea of distinction between the two, to me the latter seems to be restatement of the former with added "procedure".

completeness: every statement in the system can be either proved or disproved in the system;

decidability: iff there exists an algorithm such that for every well-formed formula in that system there exists a maximum finite number N of steps such that the algorithm is capable of deciding in less than or equal to N algorithmic steps whether the formula is (semantically) valid or not valid;

So a system can be complete and undecidable, right? If system is incomplete, does that necessarily mean that it is also undecidable?
Could someone explain on a simple example?

Thanks in advance.
 
Physics news on Phys.org
  • #2
Completeness: A set of sentences R is complete if every sentence A or ~A is a consequence of R.

Decidable: A set of sentences R is decidable if the set of sentences of its language that are consequences of R is recursive.

So a system can be complete and undecidable, right?


If T is an axiomatizable theory then no. If T is complete, it must be decidable.
 
  • #3
Your definition of decidability is odd, so I suspect some of your confusion may relate to that. All that stuff about "a maximum finite number N of steps" just means that the algorithm terminates. In other words, it either accepts or rejects every input.


I don't have a clear idea of distinction between the two, to me the latter seems to be restatement of the former with added "procedure".

That's somewhat correct...

Completeness means that either a proof or disproof exists.
Decidability means that there's an algorithm for finding a proof or disproof.


In nice cases, they are equivalent, since in a complete theory, you can just iterate over every possible proof until you find one that either proves or disproves the statement.

I'll pause here. That should give you a hint as to how a complete, but not decidable, theory should look, so I want to give you a chance to find it (or at least the basic idea).
 
  • #4
*frown*

I don't think my definition of "decidable" is equivalent to gravenworld's definition. I'll have to ponder this for a while.
 
  • #5
Hurkyl said:
*frown*

I don't think my definition of "decidable" is equivalent to gravenworld's definition. I'll have to ponder this for a while.


What I wrote means the same thing as what you did. A set of sentences R is decidable if the set of sentences of its language that are consequences of R are proved by R.
 
  • #6
thank you both for the clarification :smile:

gravenewworld said:
So a system can be complete and undecidable, right?
If T is an axiomatizable theory then no. If T is complete, it must be decidable.
the reason I said that is because, first order logic is complete, since there are models in it, but my book says that it is not decidable in a sense that if you run some sentence through a semantic tableax, it may not necessarily reach a closure. Does it mean it is just not axiomatizable then?
 
  • #7
it means you can't tell when the algorithm/execution will terminate
 
  • #8
EvLer said:
thank you both for the clarification :smile:


the reason I said that is because, first order logic is complete, since there are models in it, but my book says that it is not decidable in a sense that if you run some sentence through a semantic tableax, it may not necessarily reach a closure. Does it mean it is just not axiomatizable then?

First order logic is complete, but for a different definition of complete than the one referred to above.

The completeness of first order logic refers to the fact that:
- if I have a set of axioms
- and I have a sentance that is true in every model of those axioms
- then there exists a proof of that sentance from the axioms
so long as the sentances are all expressed using first order logic.
 
  • #9
neurocomp2003 said:
it means you can't tell when the algorithm/execution will terminate
or that it will terminate at all, so there's no way to know whether it is a theorem or not, i.e. it may never terminate with either positive or negative result, in case if that set of sentences is undecidable.

ooops, should have said first order PREDICATE logic... since propositional is both decidable and complete. Semantic tableaux does close for propositional logic.

Thanks for your replies, i think I have a better idea now.
 
  • #10
What I wrote means the same thing as what you did. A set of sentences R is decidable if the set of sentences of its language that are consequences of R are proved by R.

I'd like to believe that! I'm having trouble making myself happy.

If we're dealing with a finite set of axioms, it's clear, since you can just enumerate the proofs.

If we're dealing with an infinite, but turing decidable*, set of axioms, it's still clear, because we can still enumerate the proofs.


But what if my set of axioms is not turing decidable?


You can't just use the proof that the turing machine decides the theory, becuase:
(1) The proof might require methods that simply don't exist in the theory
(2) There might not be a proof! Whether the turing machine decides the theory could be independent of ZFC. (or whatever formal world in which you're living)


It's not obvious to me that this can be patched up... and I don't recall any fancy results that could be used to do it, since I don't know what does and does not apply to theories with infinitely many axioms.


*: means the same as "recursive", but I'm much more comfortable with this language
 
  • #11
Hmmm I'm not sure how to respond to your point. I never studied turing machines. But Church thesis states that a function is effectively computable iff it is recursive. A set of sentences is effectively decidable iff its characteristic function is effectively computable. I think my professor mentioned to me that if a set is effectively decidable it can be computed by a TM. Thus if TM can compute a characteristic function for a set, the characteristic function is recursive, i.e. the set of sentences is recursive and decidable. If a TM can't compute a set of sentences, then the set of sentences isn't recursive. (I may be wrong about what I vaguely recall about TMs though.)
 
  • #12
how did you manage to study church thesis before turing machines? I thought any algorithm can be put on a turing machine...whether it be single tape or multitape.
isn't that why its related(can't remember if its called it) to the "universal machine"(been awhile...forgot that name too).
 
  • #13
I did an independent study on Mathematical logic. I never studied logic before, but I definitely wanted to learn enough machinery so I could go through and understand the proofs to Godel's incompleteness theorems. There simply wasn't enough time to learn about TMs an other topics in logic. Needless to say, after a lot of blood, sweat, and tears I got through Godel's theorems.
 
  • #14
My text says "Turing decidable" is synonymous with "Recursive", and "Turing recognizable" is synonymous with "Recursively enumerable", if that helps.
 
  • #15
Ummm... :redface:
I have a follow-up question.

According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent. So then, if it(system_1) can proved to be consistent from within another system (system_2), does that system (system_2) have to be consistent?

I am not exactly sure how this works, I just read an article that talked about proving consistency of one system using another system. If you have a simple example to demonstrate this, it would be great.

Thanks again!
 
  • #16
According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent.

Not quite: if a system satisfying his conditions is consistent, it cannot prove itself consistent.


As an example of relative consistency, you can use algebra to prove geometry consistent: you can define the words "point", "line", "incident", "between", and "congruent" algebraically, and then prove that these terms satisfy the axioms of Euclidean geometry.
 
  • #17
EvLer said:
Ummm... :redface:
I have a follow-up question.

According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent. So then, if it(system_1) can proved to be consistent from within another system (system_2), does that system (system_2) have to be consistent?
No. An inconsistent system can prove any statement. If (system_2) is inconsistent it can prove (system_1) is consistent. For what it's worth, if (system_2) is inconsistent, it can also prove (system_1) is inconsistent.
 

1. What is completeness in terms of decidability?

Completeness in terms of decidability refers to the concept that a formal system or logical theory is able to prove or disprove all true statements within that system. This means that every valid statement within the system can be proven or disproven using the rules and axioms of the system.

2. How does completeness differ from decidability?

Completeness and decidability are two related but distinct concepts. While completeness refers to the ability of a formal system to prove or disprove all true statements within that system, decidability refers to the ability to determine whether a given statement is true or false within the system. In other words, completeness is about the power of the system, while decidability is about the limitations of the system.

3. Can a system be complete but not decidable?

Yes, a system can be complete but not decidable. This means that the system is able to prove or disprove all true statements within it, but there may be statements that are undecidable, meaning that it is impossible to determine their truth or falsity within the system.

4. What are some examples of complete and decidable systems?

One example of a complete and decidable system is first-order logic. This logical system is able to prove or disprove all true statements within it, and it is also decidable, meaning that there is an algorithm that can determine the truth or falsity of any statement within the system. Another example is the propositional calculus, which is both complete and decidable.

5. Why is completeness vs decidability an important concept in computer science?

Completeness vs decidability is an important concept in computer science because it helps us understand the limitations and capabilities of different logical systems and programming languages. It also has implications for the design and analysis of algorithms, as some problems may be undecidable, meaning that there is no algorithm that can solve them. Understanding completeness and decidability can also aid in the development of more efficient and powerful computer systems.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Programming and Computer Science
Replies
29
Views
2K
  • Quantum Interpretations and Foundations
3
Replies
84
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
916
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
33
Views
19K
  • Quantum Physics
Replies
2
Views
920
Replies
93
Views
4K
Back
Top