Computer Science 351 — Turing Machines and Their Languages and Functions

A Turing Machine

Turing Machines and Their Languages and Functions

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.

This material will be covered in lectures on October 3–10 and in tutorials on October 9–22.

Supplemental Material

You should not need any reference material, for this, that is not provided on the course web site. However, both of the following books include useful introductions to Turing machines.

Please note that lots of references make small changes to the definition of a “Turing machine” — so that the “Turing machine” that you are reading about, somewhere else, might not be the same as the kind of “Turing machine” described in this course. The description in the lecture material is consistent with the description of a Turing machine in Sipser’s textbook (while, possibly, giving a few more technical details).

Lecture #10: Introduction to Turing Machines (Thursday, October 3)

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. Ideally, by attending and participating in the lecture presentation, you will better understand how the languages of these machines are defined, and how similar machines are used to compute functions (from strings to strings).

“Turing machine design” is not a very significant part of this course — but it will be helpful for you to understand something about this in order to solve problems concerning “computability” after these lectures. A supplemental document for this lecture introduces this topic and explains how one technique — “refinement” — can be used for this.

Preparatory Reading

Lecture Presentation

Finishing Up

Tutorial #9: Introduction to Turing Machines (Wednesday, October 9 and Thursday, October 10)

Lecture #11: Multi-Tape Turing Machines, Nondeterministic Turing Machines, and the Church-Turing Thesis (Tuesday, October 8)

Why This is Included

While the “Turing machines” that were introduced in the previous lecture are quite powerful, they are too limited for it to be easy to design (or even read and understand) these kinds of Turing machines for nontrivial problems.

This lecture introduces 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”, “decidable languages”, and “computable functions” 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”:

In supplemental material, another Turing-machine variant — a nondeterministic Turing machine is introduced. While it does not really make sense to consider the nondeterministic computation of functions (so that “computable functions” cannot be defined using them, at all) a proof is sketched that the sets of Turing-recognizable languages and Turing-decidable languages would be unchanged if they were defined using nondeterministic Turing machines instead of standard (deterministic) Turing machines.

This 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.

As previously noted, Turing machine design is not a major part of this course — but it will be helpful to know a little bit about this later one, when “computability” is considered. The lecture presentation includes a “Turing machine design” exercise that is intended to help students to be prepared for the rest of this course.

Preparatory Reading

Lecture Presentation

Finishing Up

Tutorial #10: More About Turing Machines (Tuesday, October 15 and Wednesday, October 16)

Tutorial #11: Variants of Turing Machines — and Simulations (Monday, October 21 and Tuesday, October 22)

Lecture #12: Universal Turing Machines (Thursday, October 10)

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.

The existence of a “universal Turing machine” can be seen as additional evidence that Turing machines really are as powerful as “real computers.” Furthermore, the fact that Turing machines (and their inputs) can be encoded as strings over a fixed alphabet will be extremely important later on in this course. The languages of valid encodings of Turing machines, and the “acceptance” language (which is the language of the universal Turing machine being introduced) will all be extremely important as the course continues, and “computability” is studied.

Preparatory Reading

Lecture Presentation

Finishing Up


University of Calgary Extension of Logo
Department of Computer Science

cpsc 351 computer science faculty of science u of c

cpsc 351 introduction finite automata and regular languages turing machines computability discrete probability conclusion course outline more about course administration references assignments tests