Theory of Computation

Notes from the computability theory Goal: Answer What are the fundamental capabilities and limitations of computers? Subject matter: Automata, Computability, Complexity What makes some problems computationally hard and others easy? Decidability vs Tractability

Introduction

• Deductive proofs vs Inductive proofs.
• Contrapositive(logically similar) vs converse(not equivalent).