- #1

- 458

- 0

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.