• edited by
18,980 views
60 60 votes

A single tape Turing Machine $M$ has two states $q0$ and $q1$, of which $q0$ is the starting state. The tape alphabet of $M$ is $\{0, 1, B\}$ and its input alphabet is $\{0, 1\}$. The symbol $B$ is the blank symbol used to indicate end of an input string. The transition function of $M$ is described in the following table.

$$\begin{array}{|l|l|l|l|}\hline \text{}  &  \text{$0$} & \text{$1$} & \text{$B$} \\\hline \text{$q0$}  &  \text{$q1, 1, R$} & \text{$q1, 1, R$} & \text{$Halt$} \\\hline \text{$q1$}  &  \text{$q1, 1, R$} & \text{$q0, 1, L$} & \text{$q0, B, L$} \\\hline  \end{array}$$

The table is interpreted as illustrated below.

The entry $(q1, 1, R)$ in row $q0$ and column $1$ signifies that if $M$ is in state $q0$ and reads $1$ on the current page square, then it writes $1$ on the same tape square, moves its tape head one position to the right and transitions to state $q1$.

Which of the following statements is true about $M$?

  1. $M$ does not halt on any string in $(0+1)^+$
  2. $M$ does not halt on any string in $(00+1)^*$
  3. $M$ halts on all strings ending in a $0$
  4. $M$ halts on all strings ending in a $1$

7 Answers

0 0 votes

The "trick" to solving this problem quickly without tracing every single step is to find the unique halting condition<!--TgQPHd|||[]--> and determine if it can ever be reached.<!--TgQPHd|||[]-->

AI generated image

 

HOPE EVERYONE UNDERSTAND

ago
Answer:
Position:
Show:

Related questions

61 61 votes
5 answers 5 answers
14.9k
14.9k views
Kathleen asked Sep 17, 2014
14,896 views
A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ respectively denote the probability density functions of time taken to execute the two ...
55 55 votes
6 answers 6 answers
14.3k
14.3k views
Arjun asked Sep 8, 2014
14,293 views
Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x...
100 100 votes
6 answers 6 answers
24.3k
24.3k views
Kathleen asked Sep 16, 2014
24,304 views
Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{G}$, the number of components in the resultant graph must neces...
69 69 votes
9 answers 9 answers
24.4k
24.4k views
Kathleen asked Sep 17, 2014
24,379 views
Consider the NFA $M$ shown below.Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of ...