in

Mathematical Logic

Volume II

Computability and Incompleteness

Stefan Bilaniuk

Author address:

Department of Mathematics

Trent University

Peterborough, Ontario

Canada K9J 7B8

E-mail address: sbilaniuk@trentu.ca

1991 Mathematics Subject Classi¬cation. 03.

A Problem Course in Mathematical Logic

Volume II: Computability and Incompleteness

Version 1.3

Copyright c 1994-1997 by Stefan Bilaniuk.

Abstract. This is the Volume II of a text for a problem-oriented

undergraduate course in mathematical logic. It covers the basics

of computability, using Turing machines and recursive functions,

and G¨del™s Incompleteness Theorem, and could be used for a one-

o

semester course on these topics. Volume I, Propositional and First-

Order Logic, covers the basics of these topics through the Sound-

ness, Completeness, and Compactness Theorems.

Information on availability and the conditions under which this

book may be used and reproduced are given in the preface.

This book was typeset using L TEX, using the AMS-L TEX and

A A

AMSFonts packages of the American Mathematical Society.

Contents

Preface v

Introduction 1

Computability 5

Chapter 10. Turing Machines 7

Chapter 11. Variations and Simulations 13

Chapter 12. Universal Turing Machines and the Halting Problem 17

Chapter 13. Computable and Non-Computable Functions 25

Chapter 14. Primitive Recursive Functions 29

Chapter 15. Recursive Functions 35

Incompleteness 41

Chapter 16. Preliminaries 43

Chapter 17. Coding First-Order Logic 45

Chapter 18. De¬ning Recursive Functions In Arithmetic 49

Chapter 19. The Incompleteness Theorem 53

Hints 57

Chapter 10. Hints 59

Chapter 11. Hints 61

Chapter 12. Hints 63

Chapter 13. Hints 65

Chapter 14. Hints 67

Chapter 15. Hints 69

iii

iv CONTENTS

Chapter 16. Hints 71

Chapter 17. Hints 73

Chapter 18. Hints 75

Chapter 19. Hints 77

Bibliography 79

Index 81

Preface

This book is intended to be the basis for a problem-oriented full-year

course in mathematical logic for students with a modicum of mathe-

matical sophistication. Volume II covers the basics of computability,

using Turing machines and recursive functions, and incompleteness.

It could be used for a one-semester course on these topics. Volume

I covers the basics of propositional and ¬rst-order logic through the

Soundness, Completeness, and Compactness Theorems, plus some ma-

terial on applications of the Compactness Theorem; it could also be

used as for a one-semester course on these topics. However, part of

Volume II, particularly the chapters on incompleteness, assume some

familiarity with the basics of ¬rst-order logic.

In keeping with the modi¬ed Moore-method, this book supplies

de¬nitions, problems, and statements of results, along with some ex-

planations, examples, and hints. The intent is for the students, indi-

vidually or in groups, to learn the material by solving the problems

and proving the results for themselves. Besides constructive criticism,

it will probably be necessary for the instructor to supply further hints

or direct the students to other sources from time to time. Just how

this text is used will, of course, depend on the instructor and students

in question. However, it is probably not appropriate for a conventional

lecture-based course nor for a really large class.

The material presented here is somewhat stripped-down. Various

concepts and topics that are often covered in introductory courses on

computability are given very short shrift or omitted entirely, among

them models of computation other than Turing machines and recursive

functions, formal languages, and computational complexity.1 Instruc-

tors might consider having students do projects on additional material

if they wish to cover it. It might also be expedient, in view of the

somewhat repetitive nature of devising Turing machines and recursive

functions for various purposes, to be selective about the problems the

students are required to do or to divide them up among the students.

1

Future versions of both volumes may include more “ or less! “ material. Feel

free to send suggestions, corrections, criticisms, and the like ” I™ll feel free to ignore

them or use them.

v

vi PREFACE

Acknowledgements. Various people and institutions deserve the

credit for this text: All the people who developed the subject. My

teachers and colleagues, especially Gregory H. Moore, whose math-

ematical logic course convinced me that I wanted to do the stu¬.

The students at Trent University who su¬ered, su¬er, and will suf-

fer through assorted versions of this text. Trent University and the

taxpayers of Ontario, who paid my salary. Ohio University, where I

spent my sabbatical in 1995“96. All the people and organizations who

developed the software and hardware with which this book was pre-

pared. Anyone else I™ve missed.

Any blame properly accrues to the author.

Conditions. This book may be freely transmitted, stored, copied,

and used until 31 December, 1998, subject to the following restrictions:2

1. It may not be modi¬ed in any way without the express written

permission of the author.

2. It may not be sold at a pro¬t, but only to recover the cost of

reproduction.

3. After 31 December, 1998, it may no longer be reproduced, stored,

or transmitted in any form without the express written permis-

sion of the author, except that printed copies existing as of 31

December, 1998, may be retained and used after this date.

The reason for the time-limit is that I hope to improve this book

and make a new version available.3

Availability. The URL of the home page for A Problem Course

In Mathematical Logic, with links to L TEX and PostScript source ¬les

A

of the latest release of both volumes, is:

• http://www.trentu.ca/academic/math/sb/misc/pcml.html

A text-only information ¬le and LTEX and PostScript source ¬les of

A

the latest release of both volumes can be accessed by anonymous ftp

at:

• ftp://ftp.trentu.ca/pub/sbilaniuk/pcml/

Please note that in addition to LTEX you will need the AMS-L TEX

A A

and AMSFonts packages to typeset and print either volume.

If you have any problems, feel free to contact the author at the

addresses given on the title page, preferably by e-mail, for assistance

or even to ask for a paper copy.

2

If you violate these restrictions, I will be ¬‚attered, but you will still be in the

wrong.

3

Who knows, it might even ¬nd a publisher . . .

PREFACE vii

Author™s Opinion. It™s not great, but the price is right!

viii PREFACE

Introduction

The Entscheidungsproblem. Recall that a logic satis¬es the

Completeness Theorem if, whenever the truth of a set of sentences

Σ implies the truth of a sentence •, there is a deduction of • from

Σ. Propositional and ¬rst-order logics both satisfy the Completeness

Theorem, though second- and higher-order logics do not. In the case

of propositional logic, the Completeness Theorem leads to a rote pro-

cedure for determining whether Σ • or not, so long as Σ is ¬nite:

write out a complete truth table for all of Σ together with • and check

whether every assignment that makes every sentence of Σ true also

makes • true. It is natural to ask whether something of the sort can

be done for ¬rst-order logic. If so, it might be very useful: since most

of mathematics can be formalized in ¬rst-order logic, such a method

would have the obvious use of putting mathematicians out of business

. . . This question is the general Entscheidungsproblem 4 for ¬rst-order

logic:

Entscheidungsproblem. Given a set Σ of formulas of a ¬rst-

order language L and a formula • of L, is there an e¬ective method

for determining whether or not Σ •?

Of course, the statement of the problem begs the question of what

“e¬ective” is supposed to mean here. In this volume we™ll explore

two formalizations of the notion of “e¬ective method”, namely Tur-

ing machines and recursive functions, and then use these to answer

the Entscheidungsproblem for ¬rst-order logic. The answer to the gen-

eral problem is negative, though decision procedures do exist for some

particular ¬rst-order languages and sets Σ.

Historically, the Entscheidungsproblem arose out of David Hilbert™s

scheme to secure the foundations of mathematics by axiomatizing math-

ematics in ¬rst-order logic and showing that the axioms do not give rise

to any contradictions. It did so in two related ways. First, given some

plausible set of axioms, it is necessary to show that they do not lead

to a contradiction, such as ± § (¬±). Second, it is desirable to know

Entscheidungsproblem ≡ decision problem.

4

1

2 INTRODUCTION

whether such a set of axioms is complete; i.e. given any sentence • of

the language, that the axioms either prove or disprove •.

In the course of trying to ¬nd a suitable formalization of the no-

tion of “e¬ective method”, mathematicians developed several di¬erent

abstract models of computation in the 1930™s, including recursive func-

tions, »-calculus, Turing machines, and grammars. Although these

models are very di¬erent from each other in spirit and formal de¬ni-

tion, it turned out that they were all essentially equivalent in what they

could do. This suggested the (empirical!) principle:

Church™s Thesis. A function is e¬ectively computable in princi-

ple in the real world if and only if it is computable by (any) one of the

abstract models mentioned above.

Of course, this is not a mathematical statement . . . We will study

Turing machines and recursive functions, and then use this knowledge

to formulate and answer a more precise version of the general Entschei-

dungsproblem for ¬rst-order logic.

The development of the theory of computation actually began be-

fore the development of electronic digital computers. In fact, the com-

puters and programming languages we use today owe much to the ab-

stract models of computation which preceded them. For two, the stan-

dard von Neumann architecture for digital computers was inspired by

Turing machines and the programming language LISP borrows much

of its structure from »-calculus.

Approach. This book supplies de¬nitions and statements of re-

sults, plus some explanations and a number of problems and examples,

but no proofs of the results. The hope is that you, gentle reader, will

learn the material presented here by solving the problems and proving

the results for yourself. Brief hints are supplied for almost all of the

problems and results, but if these do not su¬ce, you should consult

your peers, your instructor, or other texts.

Prerequisites. In principle, little is needed by way of prior math-

ematical knowledge to de¬ne and prove the basic facts about com-

putability. Some knowledge of the natural numbers and a little set the-

ory su¬ces. The material leading up to the Incompleteness Theorem

” the resolution of the general Entscheidungsproblem for ¬rst-order

logic ” does require grounding in ¬rst-logic, such as that provided in

Volume I, as well as in computability.

What really is needed to get anywhere with all of the material

developed here is competence in handling abstraction and proofs, in-

cluding proofs by induction. The experience provided by a rigorous

INTRODUCTION 3

introductory course in algebra, analysis, or discrete mathematics ought

to be su¬cient. Some problems and examples draw on concepts from

other parts of mathematics; students who are not already familiar with

these should consult texts in the appropriate subjects for the necessary

de¬nitions.

Other Sources and Further Reading. [3], [5], [7], and [8] are

texts which go over at least some of the material, while [1] is a good

if terse reference for more advanced material. Entertaining accounts of

much of the material may be found in [6] and [9]; the latter discusses

the possibility that Church™s Thesis may not be true. Many of the

original sources for the material in this volume can be found in the

anthology [4].

4 INTRODUCTION

Computability

CHAPTER 10

Turing Machines

Of the various ways to formalize the notion an “e¬ective method”,

the most commonly used are the simple abstract computers called Tur-