Computer Science 513/601.08 — Models of Computation

Kurt Godel

Models of Computation — and the Church-Turing Thesis

Who is This Guy?

Kurt Friedrich Gödel was a logician, mathematician and philosopher who dealt a serious blow to Hilbert’s program by publishing two incompletness theorems in 1931. The proof of the first of these can be modified to show there is no consistent set of axioms, that can be listed by an effective procedure (that is, “algorithm”) that is capable of proving all truths about the natural numbers — provided that an “effective procedure” can be defined.

Initially, the notion of an “effective procedure” was only understood informally. Gödel realized, and argued, that a formal definition of an “algorithm” was needed if his work was to continue. His investigations, and discussions, helped to motivate much of the work that will be described next.

Overview

There were multiple attempts to formalize the notion of an “algorithm” in the 1930s. The next lectures present some of these — beginning with an attempt that is not, quite, successful (it is too limited) but still useful. Later lectures present other attempts to define an “algorithm” that were more successful. Models that were proposed later on, when computers were somewhat more widely available, are also included.

The lectures also introduce significant results concerning the equivalence of computational models, along with some of the complications arising when these different computational models are to be compared. This will lead to the “Church-Turing Thesis” — a widely accepted belief about computable functions.

Lecture #2: Modelling Computations of Functions I
(Thursday, September 5)

Why This is Included

Attempts for formalize the notion of an “algorithm” (and “computable” objects), beginning in the 1930s, can be grouped into three types:

This lecture begins a study of “modelling computation of functions” by introducing the primitive recursive functions. These had already been described in (or before) 1923 — before the publication of Gödel’s incompleteness theorems. For a time it was widely believed that the only total functions that could be seen to be “computable” were these functions. While this was eventually proved not to be true, quite a few computable total functions are primitive recursive, and we will use these functions at several places in this course.

This first lecture introduces these functions, along with a process, and several closure properties, that can sometimes be used to prove that a function is primitive recursive.

Preparatory Reading

Lecture Presentation

Finishing Up

Lecture #3: Modelling Computations of Functions II
(Tuesday, September 10)

Why This is Included

As suggested above, many of the “computable functions” that arise in mathematics can be shown to be primitive recursive — and it is challenging to show that computable total functions, which are not primitive recursive, even exist. On the other hand, all primitive recursive functions are total functions, so something else is needed if “computable partial functions” are to be considered.

This lecture presents additional techniques that can be used to show that functions are primitive recursive. It then provides another construction — unbounded minimization that can be used to describe “computable” partial functions. Another class of functions that can be recursively defined, namely, the set of μ-recursive functions (also called the general recursive functions), is defined after that.

Yet another kind of functions that can be recursively defined, namely, functions that can be defined using the λ-calculus, are described in supplemental material, as well.

These are being introduced, partly to suggest what attempts to define “effective computability” initially looked like. The constructions, and the sets of “primitive recursive functions” and “μ-recursive functions”, will also be useful later on.

Preparatory Reading

Lecture Presentation

Finishing Up

Lecture #4: Modelling Computations of Functions III
(Thursday, September 12)

Why This is Included

The types of “computable” partial and total functions that have been described, so far, had been identified and were being studied by the 1930’s. Decades later, as computers became available, other definitions of “computable” functions were also proposed. These were based either on the architectures of computers that were now available, or programming languages that were now being developed and used.

This lecture introduces a programming language, “S”, and defines partial and total functions to be “S-computable” if there are S-programs that compute them. The lecture notes and supplemental document include a proof that every μ-computable partial or total function is S-computable as well.

The converse will eventually be proved as well. That is, several lectures later, it will be shown that every S-computable partial function is μ-computable too. This will allow us to use S-programs (and proofs of S-computability) in later proofs — greatly simplifying the task of proving several properties of computable functions that will be introduced.

Preparatory Reading

Lecture Presentation

Finishing Up

Lecture #5: Encodings — Sequences and Strings
(Tuesday, September 17)

Why This is Included

When solving computational problems we frequently use a variety of data types, rather than simply working with natural numbers. If computations with other data types are to be modelled, using the models of computation that have been introduced so far, then it is necessary to describe how other data types can be represented, or encoded, using natural numbers.

This lecture makes a start on this, by providing encoding schemes for finite sequences of natural numbers and for strings of symbols over an alphabet. This makes it easier to describe and use encoding schemes for other data types. It will also help us to relate the models of computation that have been described, so far, to models of computation that will be defined next — which work with strings of symbols over an alphabet as the basic data type, instead of natural numbers.

Preparatory Reading

Lecture Presentattion

Finishing Up

Lecture #6: Computation on Strings: Intermediate Models
(Thursday, September 17)

Why This is Included

Computational models that have been described, so far in this course, are all for the computation of partial and total functions of natural numbers — with “natural number” used as the elementary data type. However, the abstract models of computation that you are most likely to have seen before this are models that work with strings of symbols over alphabets — so that either “string” or even “symbol” should be thought of as the elementary data type being used, instead.

The models of computation presented, in this lecture, are not of much interest by themselves. They are presented and used because they help to bridge from the models (using natural numbers) that have been introduced in the course so far and the string-based models that you have probably seen already, and that will be discussed after this.

Preparatory Reading

Lecture Presentation

Finishing Up

Lecture #7: Modelling Computations by Humans: Turing Machines
(Tuesday, September 24)

Why This is Included

If you have seen an “abstract model of computation” before this, then it is likely to be some version of a Turing machine. A version of this model should therefore be discussed in a course like this one, so that the model that you are (probably) already familiar with can be compared to the other models, being discussed in this course, that are more likely to be new.

As Turing explained, when introducing a version of this model (in 1937), this model was developed by considering how human beings solve problems, using a pencil and paper, and using a simplified version of this to develop a machine model. It was more easily accepted than various abstract models that had been introduced before it, because it was seen to be at least a bit more “natural” (and less “artificial”). Turing machines are also easier to use in computational complexity theory than many of the other models considered in this course, so that they are far more likely to be considered in courses like CPSC 413 and CPSC 511.

Preparatory Reading

Lecture Presentation

Finishing Up

Lecture #8: Modelling Computation of Languages
(Thursday, September 26)

Why This is Included

In order to show the variety of models of computation that were being proposed in the early-to-mid twentieth century, several models that can be used to generate, or accept, the strings in a language are described. At least one of these, phrase-structure grammars, has significant applications in computational linguistics — so that this model will be studied further, later in the course.

Ideally, students in this course have already heard of the Church-Turing thesis — which seems plausible, once all these models (and their “equivalence”, in one sense or another) have been considered. A bit more information about this, which students might not already know, will be supplied.

Preparatory Reading

Lecture Presentation

Finishing Up


University of Calgary Extension of Logo
Department of Computer Science

cpsc 513/601.08 computer science faculty of science u of c

cpsc 513/601.08 intro and math review models of computation first hard problems classifying unsolvable problems post’s problem chomsky hierarchy cpsc 513 course outline cpsc 601.08 course outline more about administration references assignments tests