Computability Theory

Contents

Foreword ix

Preface xi

1 The Computability Concept 1

1.1 The Informal Concept 1

1.1.1 Decidable Sets 1

1.1.2 Calculable Functions 3

1.1.3 Church’s Thesis 10

Exercises 11

1.2 Formalizations – An Overview 12

1.2.1 Turing Machines 13

1.2.2 Primitive Recursiveness and Search 18

1.2.3 Loop and While Programs 20

1.2.4 Register Machines 22

1.2.5 Definability in Formal Languages 24

1.2.6 Church’s Thesis Revisited 26

Exercises 27

2 General Recursive Functions 29

2.1 Primitive Recursive Functions 29

2.1.1 Bounded Search 40

2.2 Search Operation 47

Exercises 49

3 Programs and Machines 53

3.1 Register Machines 53

3.2 A Universal Program 60

Exercises 71

3.3 Register Machines Over Words 72

Exercises 76

3.4 Binary Arithmetic 76

4 Recursive Enumerability 79

4.1 Recursively Enumerable ...