Computer Science 351 — Turing Machines and Computability

A Turing Machine

Turing Machines and Computability

Overview

The next set of lectures introduces another, more powerful, way to represent languages — namely by giving Turing machines that “recognize” or “decide” these languages. We will see that these are — in a significant sense — at least as powerful as any “real” computer.

Various concepts, including design, verification, simulations, and proofs of equivalence of computational models have already been introduced. These concepts will now be used, in somewhat more sophisticated and challenging ways, to establish results about the power of Turing machines which will be helpful when the next topic is considered.

These lectures also concern the question of whether there are problems that provably cannot be solved by computers, and how to identify these.

Two techniques for showing that languages are undecidable, or unrecognizable — which make use of closure properties for the sets of decidable languages and of recognizable languages — will be introduced.

This material will be covered in lectures on May 21–June 2 and in tutorials on May 25 – June 4.

Supplemental Material

You should not need any reference material, for this, that is not provided on the course web site. However, the following book provides a readable introduction to computability theory, including the use of many-one reductions to prove undecidability:

Lecture #6: Introduction to Turing Machines (Thursday, May 21)

Why This is Included

Once again, “you have to start somewhere”. In this lecture, the kind of abstract machine that will be considered for much of the rest of the course will be introduced. Lecture activities are intended to help you understand notation used to describe these machines and to help you to understand how strings are processed when these machines are used — in order to recognize languages, and also to compute functions.

When solving problems later on, it will sometimes necessary to show that partial or total functions from strings (over one alphabet) to strings (over a possibly different alphabet) are “computable” — so a variant of a Turing machine that computes a function is now being introduced.

While “Turing machine design” is not a major part of this course, it will still be necessary to present Turing machines for various computations when solving other (more interesting) problems. This can be challenging, because Turing machines are more complicated than finite automata and the process can be overwhelming if it is not carried out carefully. A recommended design process, that can make it easier to do this when needed, is also introduced.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #6: Introduction to Turing Machines (Tuesday, May 26 and Wednesday, May 27)

This exercise concerns material from Lecture #6. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.

Lecture #7: Simulations and Turing Machine Variants (Tuesday, May 26)

Why This is Included

At this point, one might wonder how “recognizable languages” and “decidable languages” are related to “regular languages”, and how a relationship can be proved.

Students seeking other sources of information about this will, very likely, encounter slightly different versions of “Turing machines” which might — or might not — be used to define “recognizable language” and “decidable languages”. After all, if you change the way that something is defined, how can you be sure that you are still defining the same thing?

This lecture reviews, and expands on, the previous discussion of simulations — which were used to consider alternative ways to define “regular languages”. These are now being applied to prove a relationship between the set of “regular languages” and the set of “decidable languages”, and to consider alternative ways to define “recognizable languages” and “decidable languages”.

This lecture introduces more complicated variants, called multi-tape Turing machines, that make problem solving somewhat easier. Lecture material introduces this new kind of a machine, and sketches a simulation that can be used to show that the sets of “recognizable languages” and “decidable languages” are not changed, if these are defined using multi-tape Turing machines instead of the simpler Turing machines that have already been introduced.

In a way, this will allow us to have “the best of both worlds”:

This also provides evidence to support a widely-held belief, the Church-Turing thesis, which (effectively) asserts that Turing machines, and the sets of languages and functions defined using them, really do model “computability”. This justifies their study. Additional information about the Church-Turing thesis is also provided in supplemental material.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #7: Simulations and Turing Machine Variants (Monday, June 1 and Tuesday, June 2)

This exercise concerns material fromn Lecture #7. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.

Lecture #8: Proving Undecidability — Part One (Thursday, May 28)

Why This is Included

A “Python emulator” is a program that receives a Python script and input for that script, and executes the script on the input. This can be written as a Python script, itself.

Similarly, a “Java compiler” is a program that receives a Java program as input and converts it into lower-level machine code that can be processed, directly, by a computer. This can be written as a Java program, itself.

This lecture introduce a universal Turing machine — which is, essentially, a “Turing machine interpreter” which is, itself, a Turing machine.

Once one knows about universal Turing machines, one can define an “acceptance language”, ATM, and prove that it is recognizable. A simple proof by contradiction establishes something extremely important, namely, that this language is undecidable. The complement of this language is provably unrecognizable — and proofs of both of these results are also sketched.

Thus, this lecture plays a role that is similar to the lecture about regular languages that introduced the Pumping Lemma for Regular Languages, as part of the discussion of regular languages: It introduces the first provably undecidable and unrecognizable languages, that are needed in order to use techniques, introduced after this, to prove that other languages ore undecidable or, sometimes, unrecognizable, as well.

“Establishing an oracle reduction” is the first technique to prove undecidability, that is based on a closure property, which will be introduced in this course. This is often the first such technique introduced, in introductions to computability, because it can be easier to discover and present oracle reductions than the other kind of “reduction” that will be introduced after this. As this lecture explains, oracle reductions can be used to prove that various languages are undecidable if you know of at least one undecidable language already.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Lecture #9: Proving Undecidability — Part Two (Tuesday, June 2)

Why This is Included

While oracle reductions can be used to prove undecidability, because the set of decidable languages is closed under these reductions, the set of recognizable languages is not closed under these reductions, so they cannot be used, in the same way, to prove unrecognizability. Many-one reductions between languages can be trickier to find and describe — but the set of recognizable languages is closed under these reductions, so that many-one reductions can be used to prove unrecognizability and to prove undecidability.

The lecture also introduces decision problems — which we are frequently interested in, instead of languages, describes what it means to “prove that a decision problem is undecidable”, and outlines a process to do this too.

Students can find the problem of proving undecidability of decision problems to be overwhelming — there can be too much to keep track of. However, this information can all be managed, if you start at the high level and solve the problem from the top down.

This lecture provides another example of a proof of undecidability — which resembles the kind of problem that students might be asked to solve on an assignment for this course — so that students can be more familiar with the process that you are being asked to follow.

Preparatory Viewing and Reading

Lecture Presentation

Tutorial #8: Proving Undecidability (Wednesday, June 3 and Thursday, June 4)


University of Calgary Extension of Logo
Department of Computer Science

cpsc 351 computer science faculty of science u of c

cpsc 351 course outline intro and review finite automata and regular languages turing machines and computability discrete probability for computer science course admin assignments tests