Theory of Computation

CONTENTS

Preface

1     Mathematical Foundations

1.1     Sets and Logic; Naïvely

1.1.1     A Detourvia Logic

1.1.2     Sets and their Operations

1.1.3     Alphabets, Strings and Languages

1.2     Relations and Functions

1.3     Big and Small Infinite Sets; Diagonalization

1.4     Induction from a User’s Perspective

1.4.1     Complete, or Course-of-Values, Induction

1.4.2     Simple Induction

1.4.3     The Least Principle

1.4.4     The Equivalence of Induction and the Least Principle

1.5     Why Induction Ticks

1.6     Inductively Defined Sets

1.7     Recursive Definitions of Functions

1.8     Additional Exercises

2     Algorithms, Computable Functions and Computations

2.1     A Theory of Computability

2.1.1     A Programming Framework for Computable Functions

2.1.2     Primitive Recursive Functions

2.1.3     Simultaneous Primitive Recursion

2.1.4     Pairing Functions

2.1.5     Iteration

2.2     A Programming Formalism for the Primitive Recursive Functions

2.2.1      vs.

2.2.2     Incompleteness of

2.3     URM Computations and their Arithmetization

2.4     A Double Recursion that Leads Outside the Primitive Recursive Function Class

2.4.1     The Ackermann Function

2.4.2     Properties ...