The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
0
answers
1
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$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
2
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 an ... following: Evaluate $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
ackermannsfunction
descriptive
0
votes
0
answers
3
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 while ... could assign an integer to all $TM's$ that had a finite subset of these symbols as its input alphabet.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
4
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 diagonalizationtype argument. Note that you cannot develop ... $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
ullman
theoryofcomputation
turingmachine
diagonalization
descriptive
0
votes
0
answers
5
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.$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

2
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 8.5 Question 2 (Page No. 362)
The purpose of this exercise is to show that a onestack 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.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
dpda
descriptive
0
votes
0
answers
7
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\}.$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 8.4 Question 10 (Page No. 352)
A twodimensional Turing machine has the usual finitestate control but a tape that is a twodimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the ... Prove that the languages accepted by twodimensional Turing machines are the same as those accepted by ordinary $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

7
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
9
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$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
10
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 onetape $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 onetape $TM$? Does it have any drawbacks compared with the other methods discussed?
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

5
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
11
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.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
12
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 tape is ...  versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state.
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

8
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
13
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?$
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

6
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
14
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 ...
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
15
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.
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

8
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
16
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$
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

9
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
1
answer
17
Self Doubt: Decidability
$L=\left \{< M_{1},M_{2}> \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 )$
asked
Jul 15
in
Theory of Computation
by
ajaysoni1924
Boss
(
10.6k
points)

149
views
theoryofcomputation
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
18
UGCNETJune2019II79
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 all TMs. $M$ is a TM that accepts $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape a and b only a only a, b and c c only
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
425k
points)

155
views
ugcnetjune2019ii
decidability
turingmachine
+1
vote
1
answer
19
UGCNETJune2019II80
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$ and $M$ will not halt ... $M$ halts without reaching to acceptable state If $\omega \in L$, then $M$ halts without reaching to an acceptable state
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
425k
points)

246
views
ugcnetjune2019ii
turingmachine
0
votes
0
answers
20
Question related to Linear bound automata
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(for also input of infinite length) But can anyone help me by designing a ... stack which may help for comparing any two of them only i.e, either for a & b or b&c or a&c).
asked
Jun 12
in
Theory of Computation
by
Akash Kumar Roy
Junior
(
559
points)

31
views
theoryofcomputation
linearboundautomata
turingmachine
0
votes
1
answer
21
ace academy test series toc turing machine
asked
May 28
in
Theory of Computation
by
hitesh159
(
161
points)

135
views
theoryofcomputation
turingmachine
acetestseries
+1
vote
1
answer
22
Made Easy Test Series:TOCTuring Machine
$P_{1}:$ {$<M>M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked
Apr 30
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

146
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
23
Self doubt Turing machine
$1)L=M$ is a turing machine $M$ accepts two strings of different length $2)L=M$ is a turing machine $M$ accepts atleast two strings of different length Which one RE? Which one REC? How to compute the different length string?
asked
Apr 13
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

35
views
turingmachine
theoryofcomputation
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 8.3 Question 3 (Page No. 343)
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not hold $0,$ then the TM should halt. You may assume that there are no tape ... a TM that accepts all strings of $0's$ and $1's$ that do not have two $1's$ in a row$.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

34
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 8.3 Question 2 (Page No. 343)
A common operation in Turingmachine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit ... perform this operation. Hint $:$ Leave a special symbol to mark the position to which the head must return.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

26
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 8.3 Question 1 (Page No. 343)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$ Redesign your Turing machines from Exercise $8.2$ to take advantage of the programming techniques.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 8.2 Question 5 (Page No. 337)
Consider the Turing machine $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules$:$ ...
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

27
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 8.2 Question 4 (Page No. 336)
In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem ... $?$ If not, explain how you could modify the construction to make it work.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

35
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 8.2 Question 3 (Page No. 336)
Design a Turing machine that takes as input a number $N$ and adds $1$ to it in binary. To be precise, the tape initially contains a $ \$ $ followed by $N$ in binary. The tape head is initially scanning the $ \$ $ in state ... $ of your TM when given input $\$111.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

33
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 8.2 Question 2 (Page No. 335  336)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)

20
views
ullman
theoryofcomputation
turingmachine
Page:
« prev
1
2
3
4
5
6
7
8
...
16
next »
Quick search syntax
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
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Lakshman Patel RJIT Do you have such notes...
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
50,645
questions
56,556
answers
195,715
comments
101,580
users