CSC 456/656 Assignment 5
Due date: Tuesday, November 18, 2004, 4:00 PM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
We will define the configuration of a Turing Machine (TM)
as it is defined at the top of page 129 in the textbook.
For purposes of this class, we will modify the definition of TM in the
middle of page 128. The modification is in part 4: we will permit
S (stay) in addition to L (left) and R (right) as movement commands.
This simplifies many of the exercises.
A word of caution: many textbooks do not have a "reject" state as
given in part 7: they have only one halt state, which is the "accept"
state.
The definition "Turing decidable" given on page 130 of your textbook
is equivalent to "Recursive" given in other books, and is also
equivalent to "Decidable."
The definition "Turing recognizable" given on page 130 of your textbook
is equivalent to "Recursively enumerable" given in other books.
Do not be confused by the meaning of "enumerable." If you have taken
advanced mathematics classes, in particular, you have learned that
all subsets of the integers are enumerable. Thus,
it is easy to prove that every language is enumerable.
But not every language is recursively enumerable:
in fact, most are not. It was not until the twentieth century that
this distinction was generally acknowledged: in fact, in my own mathematics
education it was ignored, despite its overwhelming importance.
-
Work Exercise 3.8(a) on page 148 of your textbook.
-
Work Exercise 3.13 on page 149 of your textbook.
-
Work Problem 4.11 on page 169 of your textbook. (You will have to refer
back to earlier chapters.) If x is a regular expression, L(x) refers to
the language described by that regular expression.
Back to
Course Page