Computability

Computability

1. A computability problem is computable if it can be solved by some algorithm; a problem that is noncomputable cannot be solved by any algorithm

2. Mechanizing Reasoning

   • Aristotle’s Organon developed rules of inference known as syllogisms to codify syllogisms logical deductions in approximately 350 BC.
     • Euclid went beyond Aristotle by developing a formal axiomatic system. An axiomatic system is a formal system consisting of a set of axioms and a set of in- axiomatic system ference rules.
       • The goal of an axiomatic system is to codify knowledge in some domain.
   • Russell's Paradox
     • Russell’s paradox is a problem where we suppose R is defined as the set containing all sets that do not contain themselves as members.
   • Gödel’s Incompleteness Theorem
     • Gödel proved that the axiomatic system in Principia Mathematica could not be complete and consistent.
     • Gödel’s proof used construction: to prove that ¨ Principia Mathematica contains statements which cannot be proven either true or false
       • The statement that Gödel found:
         • GPM: Statement GPM does not have any proof in the system of Principia Mathematica
           • But this statement of GPM is provable in the system but, at the same time, is not provable in the system

3. The Halting Problem

   • Are there problems for which no algorithm exists?
     • Alan Turing proved that noncomputable problems exist. The way to show that uncomputable problems exist is to find one
       • Proving Noncomputability
         • Proving non-existence is requires more than just showing a hard problem could be solved if something exists
         • One way to prove non-existence of an X, is to show that if an X exists it leads to a contradiction.