more from this thinker     |     more from this text

Single Idea 10087

[filed under theme 5. Theory of Logic / K. Features of Logics / 7. Decidability ]

Full Idea

A theory is 'decidable' iff there is a mechanical procedure for determining whether any sentence of its language can be proved.

Gist of Idea

A theory is 'decidable' if all of its sentences could be mechanically proved

Source

Peter Smith (Intro to Gödel's Theorems [2007], 03.4)

Book Ref

Smith,Peter: 'An Introduction to Gödel's Theorems' [CUP 2007], p.24

A Reaction

Note that it doesn't actually have to be proved. The theorems of the theory are all effectively decidable.

The 7 ideas with the same theme [are positive or negative answers always possible?]:

18758 Validity is provable, but invalidity isn't, because the model is infinite [Church, by McGee]
9996 Expressions are 'decidable' if inclusion in them (or not) can be proved [Enderton]
10080 'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating [Smith,P]
10087 A theory is 'decidable' if all of its sentences could be mechanically proved [Smith,P]
10088 Any consistent, axiomatized, negation-complete formal theory is decidable [Smith,P]
10156 'Recursion theory' concerns what can be solved by computing machines [Feferman/Feferman]
10155 Both Principia Mathematica and Peano Arithmetic are undecidable [Feferman/Feferman]