\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parindent0pt

\begin{document}

\tutorial{tutorial5}{Problems for Tutorial 5}{March 10, 1997}

\begin{problems}

\problem
Let $R$ be a relation on a possibly infinite set $A$.  
Recall that the powers of a relation are
recursively defined by

$$
R^1 := R
$$

$$
R^{n+1} := R^{n} \circ R.
$$


We define the {\em Transitive Closure} of $R$ to be the relation given by
$\bar{R} = \bigcup_{i=1}^{\infty}{R^n}$

Prove that $\bar{R}$ is transitive.

\problem  The Dining Philosophers
There are 4 philosophers who sit down to eat dinner at a round table.  
In front of each of them
is a plate of spaghetti and to the right of each of them is a fork.  In order
to eat, each philosopher must do the following:
\begin{enumerate}
\item pick up the fork directly to his left
\item pick up the fork directly to his right
\item eat
\item put down the fork directly to his left
\item pick down the fork directly to his right
\end{enumerate}

\begin{problemparts}

\problempart
Show the state machine for this scenario.  Show that it is possible for 
a series of state transitions to occur such that
no philosopher can eat (this is called deadlock).

\problempart
Detecting a problem in their eating strategy, the philosophers start over.
Each philosopher is assigned a unique number 1 through 4.  A fork must be
used by philosophers in numerical order.  For example, if a fork is sitting
between philosophers 2 and 4, 4 must wait until 2 has picked up the fork, eaten,
and put it down before 4 can use the fork.
The philosophers may be seated in any order.

Show the state machine for this scenario.
Prove that with any seating arrangement and any order of philosophers, all
philosophers will get to finish their dinner.

\end{problemparts}


\end{problems}

\end{document}

