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.
Lecture #9: Introduction to Turing Machines
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
Lecture #10: Multi-Tape Turing Machines
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”:
- 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, 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.
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
- Multi-Tape Turing Machines: [ PDF ] [ Video ]
- Supplement: Multi-Tape Turing Machines That Compute Functions [ PDF ]
- Supplement: Encodings [ PDF ]
Lecture Presentation
Finishing Up
Lecture #11: Nondeterministic Turing Machines
Why This is Included
Nondeterministic Turing machines are abstract machines that differ from “deterministic Turing machines” in one significant way: You may be allowed to go from a given non-halting state to zero, one, or even many states when a given symbol is visible on the tape. Thus, like computations with “nondeterministic finite automata”, computations with these machines seem to involve guessing. Once again, a (complicated) simulation will be used to argue that this does not change the computational power of machines in a significant way: Both the set of “decidable languages” and the set of “recognizable languages” would be unchanged if these were defined using “nondeterministic Turing machines” instead of “deterministic Turing machines.”.
While “nondetrministic Turing machines” will not be used after this in this course, they introduce a challenging question about the efficiency of computation that will be considered in CPSC 413.
The lecture presentation is intended to help you to better understand “nondeterministic Turing machines”. It will also continue the study of “Turing machine design” by exploring the use of multi-tape Turing machines to solve more challenging problems than the ones we have considered before this.
Preparatory Reading
Lecture Presentation
Finishing Up
Tutorial #10: More about Turing Machines
Tutorial #11: Variants of Turing Machines — and Simulations
Lecture #12: Universal Turing Machines
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 “encodings” of Turing machines (and their inputs) as strings over a fixed alphabet, 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.
The lecture presentation is intended to help you to better understand “universal Turing machines”. If there is time then it will also include the discussion of the use of simulations to show that the computational power of Turing machines is not changed when the “Turing machine” model is changed in various ways.
Preparatory Reading
Lecture Presentation
- What Will Happen During the Lecture Presentation
- Notes For You To Complete
- Supplement: Church-Turing Thesis [ PDF ]
