Recent questions tagged turing-machine / GATE Overflow for GATE CSE

0 votes

0 answers

91

Michael Sipser Edition 3 Exercise 3 Question 2 (Page No. 187)
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string. $11$ $1\#1$ $1\#\#1$ $10\#11$ $10\#10$

This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ ...

admin

179 views

admin asked Oct 12, 2019

0 votes

0 answers

92

Michael Sipser Edition 3 Exercise 3 Question 1 (Page No. 187)
This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string. $0$ $00$ $000$ $000000$

This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ e...

admin

432 views

admin asked Oct 12, 2019

0 votes

0 answers

93

Ullman (TOC) Edition 3 Exercise 9.4 Question 4 (Page No. 412)
A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\Sigma$, we say that $wy\vdash yx$. That is ... . If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.

A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\S...

admin

324 views

admin asked Jul 21, 2019

0 votes

0 answers

94

Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM's$ that halt on no input. The set of ... halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.

Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.The set of all $TM$ codes for $TM's$ that halt on every input.The set of all $TM$ codes ...

admin

235 views

admin asked Jul 21, 2019

0 votes

0 answers

95

Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400 - 401)
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ ... $TM's$.

Show that the following problems are not recursively enumerable:The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.The set of pairs $(M_{1...

admin

254 views

admin asked Jul 21, 2019

0 votes

0 answers

96

Ullman (TOC) Edition 3 Exercise 9.3 Question 6 (Page No. 400)
Show that the following questions are decidable: The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its tape. Hint: If $M$ has $m$ states, consider the first $m$ ... $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.

Show that the following questions are decidable:The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its t...

admin

173 views

admin asked Jul 21, 2019

0 votes

0 answers

97

Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.

Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $...

admin

179 views

admin asked Jul 21, 2019

0 votes

0 answers

98

Ullman (TOC) Edition 3 Exercise 9.3 Question 3 (Page No. 400)
Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.

Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.

admin

198 views

admin asked Jul 21, 2019

0 votes

0 answers

99

Ullman (TOC) Edition 3 Exercise 9.3 Question 2 (Page No. 400)
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary ... that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.

The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bel...

admin

242 views

admin asked Jul 21, 2019

0 votes

0 answers

100

Ullman (TOC) Edition 3 Exercise 9.3 Question 1 (Page No. 400)
Show that the set of Turing-machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.

Show that the set of Turing-machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.

admin

313 views

admin asked Jul 21, 2019

0 votes

1 answer

101

Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.

Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10...

admin

609 views

admin asked Jul 21, 2019

0 votes

0 answers

102

Ullman (TOC) Edition 3 Exercise 9.2 Question 2 (Page No. 390 - 391)
In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore ... : Evaluate $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.

In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what ca...

admin

298 views

admin asked Jul 21, 2019

0 votes

0 answers

103

Ullman (TOC) Edition 3 Exercise 9.1 Question 4 (Page No. 383)
We have considered only Turing machines that have input alphabet $\left\{0,1\right\}$. Suppose that we wanted to assign an integer to all Turing machines, regardless of their input alphabet. That is not quite possible because ... could assign an integer to all $TM's$ that had a finite subset of these symbols as its input alphabet.

We have considered only Turing machines that have input alphabet $\left\{0,1\right\}$. Suppose that we wanted to assign an integer to all Turing machines, regardless of ...

admin

213 views

admin asked Jul 21, 2019

0 votes

0 answers

104

Ullman (TOC) Edition 3 Exercise 9.1 Question 3 (Page No. 382)
Here are two definitions of languages that are similar to the definition of $L_{d}$, yet different from that language. For each, show that the language is not accepted by a Turing machine, using a diagonalization-type argument. Note that you cannot develop ... $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.

Here are two definitions of languages that are similar to the definition of $L_{d}$, yet different from that language. For each, show that the language is not accepted by...

admin

547 views

admin asked Jul 21, 2019

0 votes

0 answers

105

Ullman (TOC) Edition 3 Exercise 9.1 Question 2 (Page No. 382)
Write one of the possible codes for the Turing machine of Fig.$8.9.$

Write one of the possible codes for the Turing machine of Fig.$8.9.$

admin

404 views

admin asked Jul 21, 2019

0 votes

0 answers

106

Ullman (TOC) Edition 3 Exercise 8.5 Question 2 (Page No. 362)
The purpose of this exercise is to show that a one-stack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$ is the concatenation of language $L$ with the language containing only the one string $\$ ... $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.

The purpose of this exercise is to show that a one-stack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$$ is the concatenation o...

admin

194 views

admin asked Jul 21, 2019

0 votes

0 answers

107

Ullman (TOC) Edition 3 Exercise 8.5 Question 1 (Page No. 361)
Informally but clearly describe counter machines that accept the following languages. In each case, use as few counters as possible,but not more than two counters. $\left\{0^{n}1^{m} \mid n\geq m\geq 1\right\}.$ ... $\left\{a^{i}b^{j}c^{k} \mid i=j \ \text{or} \ i=k \ \text{or}\ j=k\right\}.$

Informally but clearly describe counter machines that accept the following languages. In each case, use as few counters as possible,but not more than two counters.$\left\...

admin

220 views

admin asked Jul 21, 2019

0 votes

0 answers

108

Ullman (TOC) Edition 3 Exercise 8.4 Question 10 (Page No. 352)
A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at ... Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary $TM's$.

A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed o...

admin

480 views

admin asked Jul 21, 2019

0 votes

0 answers

109

Ullman (TOC) Edition 3 Exercise 8.4 Question 9 (Page No. 352)
A $k$-head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one move, the $TM$ can change state, write a new symbol on ... there. Prove that the languages accepted by $k$-head Turing machines are the same as those accepted by ordinary $TM's$.

A $k$-head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one move, the $TM$ ...

admin

183 views

admin asked Jul 21, 2019

0 votes

0 answers

110

Ullman (TOC) Edition 3 Exercise 8.4 Question 8 (Page No. 351 - 352)
In Fig. $8.17$ we saw an example of the general simulation of a $k$-tape $TM$ by a one-tape $TM.$ Suppose this technique is used to simulate a $5$-tape $TM$ that had a tape alphabet of seven symbols. ... reduce the number of tape symbols of the one-tape $TM$? Does it have any drawbacks compared with the other methods discussed?

In Fig. $8.17$ we saw an example of the general simulation of a $k$-tape $TM$ by a one-tape $TM.$Suppose this technique is used to simulate a $5$-tape $TM$ that had a ta...

admin

213 views

admin asked Jul 21, 2019

0 votes

0 answers

111

Ullman (TOC) Edition 3 Exercise 8.4 Question 7 (Page No. 351)
In this exercise, we shall implement a stack using a special $3$-tape $TM$. The first tape will be used only to hold and read the input. The input alphabet consists of the symbol $\uparrow$ , which we shall interpret as ... transition function of the $TM$ informally but clearly. Also, give a summary of the purpose of each state you use.

In this exercise, we shall implement a stack using a special $3$-tape $TM$.The first tape will be used only to hold and read the input. The input alphabet consists of the...

admin

211 views

admin asked Jul 21, 2019

0 votes

0 answers

112

Ullman (TOC) Edition 3 Exercise 8.4 Question 6 (Page No. 351)
Design the following $2-$tape $TM$ to accept the language of all strings of $0's$ and $1's$ with an equal number of each. The first tape contains the input, and is scanned from left to right. The second ... versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state.

Design the following $2-$tape $TM$ to accept the language of all strings of $0's$ and $1's$ with an equal number of each. The first tape contains the input, and is scann...

admin

271 views

admin asked Jul 20, 2019

0 votes

0 answers

113

Ullman (TOC) Edition 3 Exercise 8.4 Question 5 (Page No. 350)
Consider a nondeterministic $TM$ whose tape is infinite in both directions. At some time, the tape is completely blank, except for one cell, which holds the symbol $\$ ... Suppose the $TM$ were deterministic instead. How would you enable it to find the $\$ and enter state $p?$

Consider a nondeterministic $TM$ whose tape is infinite in both directions. At some time, the tape is completely blank, except for one cell, which holds the symbol $\$$. ...

admin

351 views

admin asked Jul 20, 2019

0 votes

0 answers

114

Ullman (TOC) Edition 3 Exercise 8.4 Question 4 (Page No. 350)
Consider the nondeterministic Turing machine $M=\left(\left\{q_{0},q_{1},q_{2},q_{f}\right\},\left\{0,1 \right\},\left\{0,1,B \right\} ,\delta,q_{0},B,q_{f}\right)$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the ...

Consider the nondeterministic Turing machine $M=\left(\left\{q_{0},q_{1},q_{2},q_{f}\right\},\left\{0,1 \right\},\left\{0,1,B \right\} ,\delta,q_{0},B,q_{f}\right)$Inform...

admin

221 views

admin asked Jul 20, 2019

0 votes

0 answers

115

Ullman (TOC) Edition 3 Exercise 8.4 Question 3 (Page No. 350)
Informally but clearly describe nondeterministic Turing machines $-$ multitape if you like $-$ that accept the following languages. Try to take advantage of nondeterminism to avoid iteration and save time in the non - deterministic sense. That is, prefer to ... but for at least two values of $j$, we have $w_{j}$ equal to $j$ in binary.

Informally but clearly describe nondeterministic Turing machines $-$ multitape if you like $-$ that accept the following languages. Try to take advantage of nondeterminis...

admin

285 views

admin asked Jul 20, 2019

0 votes

0 answers

116

Ullman (TOC) Edition 3 Exercise 8.4 Question 2 (Page No. 350)
Here is the transition function of a nondeterministic $TM \ \ M = \left(\left\{ q_{0},q_{1},q_{2}\right\},\left\{0,1\right\},\left\{0,1,B\right\},\delta,q_{0},B,\left\{q_{2}\right\} \right):$ Show the $ID's$ reachable from the initial $ID$ if the input is: $01$ $011$

Here is the transition function of a nondeterministic $TM \ \ M = \left(\left\{ q_{0},q_{1},q_{2}\right\},\left\{0,1\right\},\left\{0,1,B\right\},\delta,q_{0},B,\left\{q...

admin

269 views

admin asked Jul 20, 2019

0 votes

1 answer

117

Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$

$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...

ajaysoni1924

853 views

ajaysoni1924 asked Jul 15, 2019

4 votes

1 answer

118

UGC NET CSE | June 2019 | Part 2 | Question: 79
Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$? $G$ is a CFG with $L(G)=\phi$ There exist two TMs $M_1$ and $M_2$ such that $L(M) \subseteq \{L(M_1) \cup L(M_2)\} = $ language of ... $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape i and ii only i only i, ii and iii iii only

Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$?$G$ is a CFG with $L(G)=\phi$There exist two TMs $M_1$ and $M_2...

Arjun

2.7k views

Arjun asked Jul 2, 2019

1 votes

1 answer

119

UGC NET CSE | June 2019 | Part 2 | Question: 80
For a statement A language $L \subseteq \Sigma^*$ is recursive if there exists some turing machine $M$. Which of the following conditions is satisfied for any string $\omega$? If $\omega \in L$, then $M$ accepts $\omega$ ... $M$ halts without reaching to acceptable state If $\omega \in L$, then $M$ halts without reaching to an acceptable state

For a statementA language $L \subseteq \Sigma^*$ is recursive if there exists some turing machine $M$. Which of the following conditions is satisfied for any string $\ome...

Arjun

2.1k views

Arjun asked Jul 2, 2019

0 votes

0 answers

120

How do a^n! and a^n^2 come under machine Linear Bound Automata?I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs...

Akash Kumar Roy

621 views

Akash Kumar Roy asked Jun 12, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true