Problem Set 6—Turing Machines and Algorithms

Purpose

This problem set reinforces your understanding of Turing machines and their relation to general algorithms. In particular, by the time you finish this problem set you should be able to (1) reason about computations by standard Turing machines, (2) reason about equivalences between Turing machines or their variations and other models, and (3) use the Church-Turing Thesis to translate results about Turing machines to other notions of algorithm and vice versa.

Background

This problem set is based on material in chapter 3 of our textbook. We discussed this material in lectures on March 7, March 9, and March 11.

Activity

Solve each of the following problems.

Problem 1

Exercise 3.8b in our textbook (give an implementation-level description of a Turing machine that recognizes the language over {0,1} in which every member has twice as many 0s as 1s).

Problem 2

Exercise 3.2 in our textbook (give the configurations that the Turing machine that accepts strings of the form w#w in Example 3.9 goes through when given input 1#1).

Problem 3

A variation on problem 3.9 in our textbook: show that 2-PDAs as defined in the book are equivalent in computational power to Turing machines.

Problem 4

On reading our book’s description of multitape Turing machines, it struck me that one could just as well have Turing machines with multiple finite-state controllers. I envision such a multicontroller Turing machine being formally defined by a tuple of the form

⟨ Q₁, Q₂,…Q_n, Σ, Γ, δ, q₀₁, q₀₂…q_0n, q_accept, q_reject ⟩

Each Q_i is a finite set of states; q_accept and q_reject are members of all of these sets, but beyond that there are no restrictions on whether the sets have members in common or even have the same number of members. Each q_0i is a member of Q_i, and is the initial state for the i^th controller. The transition function, δ, maps Q₁×Q₂×…×Q_n×Γ to Q₁×Q₂×…×Q_n×Γ×{L,R} and indicates, for any combination of states the controllers may be in and tape symbol, what states the controllers enter, what symbol is written to the tape, and how the tape head moves. The other elements of the tuple are as in a standard Turing machine. A multicontroller Turing machine halts and accepts if on some transition all controllers enter q_accept; the machine halts and rejects if on some transition all controllers enter q_reject.

Show that multicontroller Turing machines are equivalent to standard ones.

Problem 5

There is a style of programming called “logic programming” in which “programs” are logical expressions describing relationships between variables, and “running” a program amounts to finding values for the variables that satisfy the relationships. Check it out online if you are interested; you will probably find lots of examples of logic programs written in a language called Prolog. An extension of logic programming, known as “constraint logic programming” or just “constraint programming” supplements (or replaces) the logical expressions with more powerful mathematical expressions, e.g., equations. In the extreme, it is possible for constraint programs to express problems that are known not to be solvable by Turing machines (for example Hilbert’s tenth problem, finding integer roots of multivariable polynomials, as described in our text). Do you think it will ever be possible to completely execute such constraint programs on computers? Why or why not?

Problem 6

The Alpha Go program has gotten a lot of attention lately for being the first artificial intelligence program to consistently defeat a human champion at the game of Go. Can Turing machines (with suitable input and output devices) also outplay human Go champions?

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.