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
2
answers
1
Made Easy Test Series : TOC Turing Machine
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ is TM that halt on all ... NonRecursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked
Apr 13
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

299
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 8.2 Question 1 (Page No. 335)
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$ $00$ $000111$ $00111$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 8.1 Question 1 (Page No. 324)
Give reductions from the helloworld problem to each of the problems below. Use the informal style of this section for describing plausible program transformations, and do not worry about the real limits such as maximum file size or ... $?$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

18
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 9.3 Question 1 (Page No. 248)
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 9.2 Question 8,9,10 (Page No. 245)
$\text{Exercise 8}:$ Give an implementation of the macroinstruction $\text{searchright} (a,q_i,q_j),$ ... $a$ by a blank. If the input contains no $a$, replace the rightmost nonblank symbol by a $b.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 9.2 Question 7 (Page No. 245)
Sketch the construction of a Turing machine that can perform the addition and multiplication of positive integers $x$ and $y$ given in the usual decimal notation.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 9.2 Question 6 (Page No. 245)
Suggest a method for representing rational numbers on a Turing machine, then sketch a method for adding and subtracting such numbers.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

21
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 9.2 Question 5(e) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^n : n\text{ is a prime number}\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 9.2 Question 5(d) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}$. For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^nb^m : m = n^2,n\geq1\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 9.2 Question 5(c) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $\text{The complement of the language in }L = \{ww^R\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

27
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 9.2 Question 5(b) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{w_1w_2: w_1 \neq w_2: w_1 = w_2\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 9.2 Question 5(a) (Page No. 244)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{ww^R\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 9.2 Question 4 (Page No. 244)
Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by $f(w_1,w_2,w_3) = i,$ where $i$ is such that $w_i = \text{max}(w_1,w_2,w_3)$ if no two $w’s$ have the same length, and $i=0$ otherwise.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 9.2 Question 3(d) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n!,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

23
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 9.2 Question 3(e) (Page No. 244)
Using adders, subtracters, comparers, copiers or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^{n!},$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 9.2 Question 3(c) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = 2^n,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 9.2 Question 3(b) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^5,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 9.2 Question 3(a) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n(n+1),$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 9.2 Question 2 (Page No. 244)
Establish a convention for representing positive and negative integers in unary notation. With your convention, sketch the construction of a subtracter for computing $xy.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 9.2 Question 1 (Page No. 244)
$\text{Example}:$ Design a Turing machine that multiples two positive integers in unary notation. Write out the complete solution to Example.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 9.1 Question 19 (Page No. 240)
You may have noticed that all the examples in these sections had only one final state. Is it generally true that for any Turing machine, there exists another one with only one final state that accepts the same language$?$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 9.1 Question 18 (Page No. 240)
$\text{Example}:$ Given two positive integers $x$ and $y$, design a Turing machine that computes $x+y$. Sketch how Example could be solved if $x$ and $y$ were represented in decimal.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 9.1 Question 17 (Page No. 239)
$\text{Example}:$ Given two positive integers $x$ and $y,$ design a Turing machine that computes $x+y$. Suppose that in Example we had decided to represent $x$ and $y$ in binary. Write a Turing machine program for doing the indicated computation in this representation
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

14
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 9.1 Question 16 (Page No. 239)
$\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 ... $q_0w(x)0w(y) \vdash^* q_nw(x)0w(y)$ if $x < y$, Complete all the details in Example
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

16
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 9.1 Question 15 (Page No. 239)
$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give convincing arguments that the Turing machine in Example does in fact carry out the indicated computation$.$
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 9.1 Question 14 (Page No. 239
$\text{Example}:$ Design a Turing machine that copies strings of $1's$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give the sequence of instantaneous ... through when presented with the input $111$. What happens when this machine is started with $110$ on its tape$?$
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

10
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 9.1 Question 13 (Page No. 239)
$\text{Example}:$ Design a Turing machine that accepts $L = \{a^nb^nc^n:n\geq 1\}$. Write out a complete solution for Example.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 9.1 Question 12 (Page No. 239)
Design a Turing machine $\Gamma = \{0,1,\square\}$ that, when started on any cell containing a blank or $a\space 1$, will halt if and only if its tape has a $0$ somewhere it.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 9.1 Question 11(f) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = \lfloor{\frac{x}{2}}\rfloor,$ where $\lfloor{\frac{x}{2}}\rfloor,$ denotes the largest integer less than or equal to $\frac{x}{2}.$
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 9.1 Question 11(e) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = x \text { mod } 5. $
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
Page:
« prev
1
2
3
4
5
6
7
8
9
...
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
Even In 2019 my 16 questions goes for negative...
It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
50,647
questions
56,492
answers
195,471
comments
100,771
users