Cheap and Secure Web Hosting Provider : See Now

[Solved]: First-order logic arity defines decidability?

, , No Comments
Problem Detail: 

I've read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that's propositional logic, correct me if I am wrong)

The question is why arity leads to undecidable problems?

I would like to see some reference material, or at least some simple example of it, as a way to think in this passage from unary to n-ary and why it leads to undecidable problems.

Asked By : Hernan_eche

Answered By : Andrej Bauer

Logic with unary predicates (not operators), is called monadic. The thing that is called propositional logic only has nullary predicates, i.e., constants true and false, and no quantifiers.

The undecidability of predicate logic follows because predicate logic (with at least one binary predicate) is powerful enough to describe how a Turing machine works, and so we can express in the logic sufficiently complicated statements about Turing machines to get undecidability. In contrast, in monadic logic, where we only have unary predicates, we cannot describe the working of a Turing machine. I am being deliberately vague here to give an idea without getting bogged down in technicalities.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6488

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback