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 7–14 and in tutorials on October 8–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.
- M. Sipser, Introduction to the Theory of Computation
Third Edition, CENGAGE Learning, 2013
- J. E. Hopcroft, R. Motwani, and J. D. Ullman,
Introduction to Automata Theory, Languages, and Computation
Third Edition, Pearson/Addison-Wesley, 2007
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 (Tuesday, October 7)
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.
Preparatory Reading and Viewing
- Introduction to Turing Machines [ Video: 34:09 ]
- Introduction to Turing Machines: Supplement for Preparatory Viewing [ PDF: 3.pp ]
Lecture #11: Simulations and Simple Turing Machine Variants (Thursday, October 9)
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 “decidaable languages”.
Preparatory Reading and Viewing
Lecture #12: Multi-Tape Turing Machines, Nondeterministic Turing Machines, and the Church-Turing Thesis (Tuesday, October 14)
Why This is Included
While the “Turing machines” that were introduced in Lecture #10 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” 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”:
- When we want to argue that a problem can be solved using a Turing machine, we can make task this simpler by presenting a multi-tape Turing machine that solves this problem.
- When we want to prove a property of the set of recognable languages or decidable languages (or computable functions), we can work with “standard” Turing machines. The simplicity of the machine model will often help to make the proof simpler than it would be if an argument was being given about a multi-tape Turing machine, instead.
Another Turing-machine variant — a nondeterministic Turing machine is briefly introduced. In supplemental material, 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. Depending on how material is introduced, this may be useful in a later course that introduces computational complexity theory.
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 Reading and Viewong
- Multi-Tape Turing Machines, Nondeterministic Turing Machines, and the Church-Turing Thesis [ Video: 30:39 ]
- Multi-Tape Turing Machines, Nondeterministic Turing Machines, and the Church-Turing Thesis: Supplement for Preparatory Viewing [ PDF: 2pp. ]
