edited by
553 views
0 votes
0 votes
$\text{Example}:$ Let $x$ and $y$ be two positive integers represented in unary notation. Construct a Turing machine that will halt in a final state $q_y$ if $x\geq y,$ and that will halt in a nonfinal state $q_n$ if $x < y.$ More specifically, the machine is to perform the computation

                                                $q_0w(x)0w(y) \vdash^* q_yw(x)0w(y)$      if $x\geq y$,

                                                $q_0w(x)0w(y) \vdash^* q_nw(x)0w(y)$      if $x < y$,

Complete all the details in Example
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
4