more from this thinker     |     more from this text

Single Idea 10080

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

Full Idea

An 'effectively decidable' (or 'computable') algorithm will be step-by-small-step, with no need for intuition, or for independent sources, with no random methods, possible for a dumb computer, and terminates in finite steps.

Gist of Idea

'Effective' means simple, unintuitive, independent, controlled, dumb, and terminating

Source

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

Book Ref

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

A Reaction

[a compressed paragraph]

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]