$******************$Designs only $*************************$

$****$No state designs$****$

The following machines are supposed known and may be used where appropriate:

The copy machine $C$

The shift left machine SL

The shift right machine $S_R$

Design Turing Machine for the following similar to this design $($Not a state design$)$:

Example $4\mathrm{.}1\mathrm{.}8$: The copying machine $C$ performs the following function: If $C$

starts with input $w,$ that is$,$ if string $w,$ containing only nonblank symbols but

possibly empty, is put on an otherwise blank tape with one blank square to its

$190$

Chapter $4$: TURING MACHINES

left, and the head is put on the blank square to the left of $w,$ then the machine

will eventually stop with $ww$ on an otherwise blank tape. We say that $C$

transforms $w_{{?}_{?}}|$ into $ww.$

A diagram for $C$ is given in Figure $4-8.$ diamond

Question $1$:

Let $M_{\text{d}\text{i}\text{f}\text{f}}$ be a Turing machine that computes the following function in the unary

representation:

$f(x,y)=x-y$ with $xy$

That is $M$ transforms:

#x#y# into #x$-$y# with $xy$

where $x$ and $y$ are positive integers in the unary representation. Give Mdiff $($not state design$)$ Question $2$:

Let $M_1$ be a Turing machine that computes the following function in unary representation:

$f(x,y)=(x,y,0)$ if $x=y$ and $(x,y,1)$ if $x>y$

That is $M_1$ that transforms:

#x#y# to #x#y#$0$# if $x=y$ and to #x#y#$1$# if $x>y$

where $x$ and $y$ are positive integers in unary representation. Give $M_1$

Hint: Use machines $C$ and Mdiff

Question $3$:

Let $M_2$ be a Turing machine that computes in unary representation the function $f(x,y,o)=x.$

That is $M_2$ transforms:

#x#y#O# into #x#

where $x$ and $y$ are positive integers in unary representation. Give $M_2$

Question $4$:

Let M$3$ be a Turing machine that computes in unary representation the function $,$

$x-y.$ That is $M_3$ transforms:

#x#y# into #$x$#$y$#$x-y$#

where $x,y$ and $x-y$ are positive integers in unary representation. Give $M_3$

Hint: Use machine Mdiff

Question $5$:

Let $M4$ be a Turing machine that computes in unary representation the function $,$

$y,z,1$ if $zy$ and $(x,y,z,0)$ if $zyx,yz{M}_4{M}_{5}0x,yz{M}_5{M}_{6}1x,yzz$

where $x,y,$ and $z$ are positive integers $in$ unary representation. Give $M_4$

Question $6$:

Let $M_{5}be$ a Turing machine that computes $in$ unary representation the function $f(x,y,z,$

$0)=(y,z).$ That $is$ the machine that transforms:

#$x$#$y$#$z$#$0$# into #$y$#$z$#

where $x,y$ and $z$ are positive integers $in$ unary representation. Give $M_5$

Question $7$:

Let $M_{6}be$ a Turing machine that computes $in$ unary representation the function $f(x,y,z,$

$1)=(z,y).$ That $is$ the machine that transforms:

#$x$#$y$#$z$#$1$# into #$z$#$y$#

where $x,y$ and $z$ are positive integers $in$ unary representation. Give $M6z.$ That $is$ the machine that transforms:

#$x$#$y$#$z$# into #$x$#$y$#$z$#$1$# $ifzy$ and #$x$#$y$#$z$#$0$# $ifz$

where $x,y,$ and $z$ are positive integers $in$ unary representation. Give $M_4$

Question $6$:

Let $M_{5}be$ a Turing machine that computes $in$ unary representation the function $f(x,y,z,$

$0)=(y,z).$ That $is$ the machine that transforms:

#$x$#$y$#$z$#$0$# into #$y$#$z$#

where $x,y$ and $z$ are positive integers $in$ unary representation. Give $M_5$

Question $7$:

Let $M_{6}be$ a Turing machine that computes $in$ unary representation the function $f(x,y,z,$

$1)=(z,y).$ That $is$ the machine that transforms:

#$x$#$y$#$z$#$1$# into #$z$#$y$#

where $x,y$ and $z$ are positive integers $in$ unary representation. Give $M6$