Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Turing Machine Notes
Recent questions tagged turing-machine
0
votes
0
answers
301
Peter Linz Edition 4 Theorem 12.1 (Page No. 301)
How $H'$ ending with initial state $q_{0}$? Plz explain with the figure given
How $H'$ ending with initial state $q_{0}$? Plz explain with the figure given
srestha
187
views
srestha
asked
Sep 13, 2018
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
turing-machine
self-doubt
+
–
0
votes
0
answers
302
Peter Linz Edition 4 Theorem 12.1 (Page No. 300)
Need some explanation on these two states. How from first state we can go to the last state as shown the symbol?
Need some explanation on these two states. How from first state we can go to the last state as shown the symbol?
srestha
242
views
srestha
asked
Sep 13, 2018
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
turing-machine
self-doubt
+
–
0
votes
1
answer
303
Doubt in Turing Machines
Consider the following T.M. {Note Σ ={a,b} ⌈ = {*,a,b} Δ = empty cells of Tape. Which of the following string does not accepted by T.M. ? (i) aabbaa (ii) ε (iii) aabb
Consider the following T.M.{Note Σ ={a,b}⌈ = {*,a,b}Δ = empty cells of Tape.Which of the following string does not accepted by T.M. ?(i) aabbaa(ii) ε(iii) aabb
goluabhinan
841
views
goluabhinan
asked
Sep 11, 2018
Theory of Computation
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
304
Turing machine
Consider <M> be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M> | M is a TM that halts on all the input and L(M) = L' for some Undecidable language L' } then L is ? A. Decidable and Recursive B. Decidable and Non recursive C. Undecidable and RE D. Undecidable and Non RE
Consider <M be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M | M is a TM that halts on all the input and L(M) = L' for some Undecidable langu...
Na462
249
views
Na462
asked
Sep 9, 2018
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
decidability
+
–
0
votes
0
answers
305
TOC- Undecidability
sidlewis
413
views
sidlewis
asked
Sep 8, 2018
Theory of Computation
theory-of-computation
decidability
rice-theorem
context-free-language
turing-machine
+
–
0
votes
1
answer
306
Difference between computability and decidability
Hi, Could someone please tell the difference between computability and decidability? Thanks
Hi,Could someone please tell the difference between computability and decidability?Thanks
surbhijain93
2.6k
views
surbhijain93
asked
Sep 7, 2018
Theory of Computation
decidability
turing-machine
+
–
0
votes
0
answers
307
Gate-overflow questions
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of them have different answers and I am not able to decide which one is correct. https://gateoverflow.in/82703/toc-turing-machine https://gateoverflow.in/98850/turing-machine
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of the...
Swapnil Naik
282
views
Swapnil Naik
asked
Sep 2, 2018
Theory of Computation
turing-machine
decidability
+
–
1
votes
0
answers
308
Decidability
Ans. D
Ans. D
Na462
207
views
Na462
asked
Sep 2, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
+
–
2
votes
1
answer
309
Turing Decidable
Na462
788
views
Na462
asked
Sep 2, 2018
Theory of Computation
theory-of-computation
turing-machine
decidability
+
–
0
votes
1
answer
310
Language Represented by TM
Ans. C
Ans. C
Na462
473
views
Na462
asked
Aug 30, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
2
votes
0
answers
311
Doubt TOC
which of the following is/are decidable? 1)for some input if an arbitrary TM makes 5 moves. 2) whether an arbitary TM halts within 5 steps 3) whether an arbitary TM prints some non blank character 4)the set of codes for TM that never make a left move. 5)an arbitrary TM halts after 100 steps 6)a TM prints a specific letter 7) a turing machine computes the product of two numbers.
which of the following is/are decidable?1)for some input if an arbitrary TM makes 5 moves.2) whether an arbitary TM halts within 5 steps3) whether an arbitary TM prints s...
Sumit Singh Chauhan
867
views
Sumit Singh Chauhan
asked
Aug 24, 2018
Theory of Computation
theory-of-computation
decidability
turing-machine
+
–
0
votes
0
answers
312
TOC, REL
Set of all languages that are not Recursively Enumerable is uncountable. This is true. WHY?
Set of all languages that are not Recursively Enumerable is uncountable.This is true. WHY?
manisha11
383
views
manisha11
asked
Aug 16, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
2
votes
2
answers
313
TOC decidability
Let <M> be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M> | M is TM on input w will visit some state P}. The language L is (a) Decidable (b) Undecidable but partially decidable (c) Undecidable and not even partially decidable (d) Not a decision problem
Let <M be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M | M is TM on input w will visit some state P}.The language L is(a) Decidable(b) Undecid...
manisha11
748
views
manisha11
asked
Aug 10, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
0
votes
0
answers
314
Theory Of Computation , Decidability
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True? (a) If L ≤ pL’ and L’ is semidecidable then L is semidecidable. (b) If L ≤ pL’ and L is RE then L’ is RE. (c) If L ≤ pL’ and L is decidable then L’ decidable. (d) If L ≤ pL’ and L is recursive. Solution: Option (a) PLEASE Explain
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True?(a) If L ≤ pL’ and L’ is ...
manisha11
277
views
manisha11
asked
Aug 10, 2018
Theory of Computation
theory-of-computation
decidability
turing-machine
+
–
0
votes
1
answer
315
Gate overflow old question
Referring to the question https://gateoverflow.in/227957/self-doubt If the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular language?
Referring to the question https://gateoverflow.in/227957/self-doubtIf the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular langu...
Vikas Verma
390
views
Vikas Verma
asked
Jul 31, 2018
Theory of Computation
theory-of-computation
turing-machine
finite-automata
+
–
2
votes
1
answer
316
self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
Vegeta
612
views
Vegeta
asked
Jul 24, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
+
–
0
votes
3
answers
317
UGC NET CSE | July 2018 | Part 2 | Question: 40
Consider the following statements( ): $S_1$: There exist no algorithm for deciding if any two Turing machine $M_1$ and $M_2$ accept the same language $S_2$: The problem of determining whether a Turing machine halts on any input is undecidable Which ... $S_2$ are correct Both $S_1$ and $S_2$ are not correct Only $S_1$ is correct Only $S_2$ is correct
Consider the following statements( ):$S_1$: There exist no algorithm for deciding if any two Turing machine $M_1$ and $M_2$ accept the same language$S_2$: The problem of ...
Pooja Khatri
1.2k
views
Pooja Khatri
asked
Jul 13, 2018
Theory of Computation
ugcnetcse-july2018-paper2
theory-of-computation
turing-machine
+
–
9
votes
0
answers
318
Decidability Vs Semi-Decidability Vs Undecidability Self Doubt
Please tell whether the following is Decidable, Semi-decidable or Undecidable A turing machine halts after running for exactly k steps A turing machine halts after running for atmost k steps A turing machine halts after running ... ;x" A turing machine visits a particular state "q" atleast k times on input "x"
Please tell whether the following is Decidable, Semi-decidable or UndecidableA turing machine halts after running for exactly k stepsA turing machine halts after running ...
Balaji Jegan
2.4k
views
Balaji Jegan
asked
Jul 12, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
+
–
2
votes
3
answers
319
Decidable
1)Let G be CFG. Whether L(G) is CFL. Q)Is it decidable or not? 2)Let G be CFG and unambiguous. Whether L(G) is CFL. Q)Is it decidable or not?
1)Let G be CFG. Whether L(G) is CFL.Q)Is it decidable or not?2)Let G be CFG and unambiguous. Whether L(G) is CFL.Q)Is it decidable or not?
srestha
2.0k
views
srestha
asked
Jun 1, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
+
–
1
votes
0
answers
320
Introduction to Computer Theory
Construct a Turing Machine to compute the following function: $f(x,y) = 1 \text{ if length(x) > length(y)} \\ =0 \text{ otherwise}{}$ where $x$ and $y$ are strings over the alphabet set $\{a b\}$. The output should be written on the tape after a \$. For example, if input is $\$abaab\$aaba$, then output should be $\$abaab\$aaba\$1$
Construct a Turing Machine to compute the following function:$$f(x,y) = 1 \text{ if length(x) length(y)} \\ =0 \text{ otherwise}{}$$where $x$ and $y$ are strings ove...
The Capricorn
219
views
The Capricorn
asked
May 30, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
0
votes
0
answers
321
Introduction to Computer Theory
Construct a Turing Machine that computes length of a given input string. For Example, if the input is $abbaab$, the output should be $abbaab00110$.
Construct a Turing Machine that computes length of a given input string. For Example, if the input is $abbaab$, the output should be $abbaab00110$.
The Capricorn
196
views
The Capricorn
asked
May 28, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
0
votes
0
answers
322
Turing Machine
Design a TM that accepts strings over the alphabet{a,b} i)Of even length ii)containing the substring "abababa" iii)not containing two consecutive zeros
Design a TM that accepts strings over the alphabet{a,b}i)Of even lengthii)containing the substring "abababa"iii)not containing two consecutive zeros
Sourav_35
267
views
Sourav_35
asked
Apr 28, 2018
Theory of Computation
turing-machine
+
–
1
votes
1
answer
323
TOC Decidability Theory
Which of the following problems is solvable? a) Writing a universal Turing machine b) Determining if an arbitrary Turing machine is a Universal Turing Machine c) Determining if a universal Turing Machine can be written in fewer than k instructions for some k d) Determining if a universal Turing Machine and some input will halt
Which of the following problems is solvable?a) Writing a universal Turing machineb) Determining if an arbitrary Turing machine is a Universal Turing Machinec) Determining...
gauravkc
5.9k
views
gauravkc
asked
Apr 25, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
+
–
0
votes
0
answers
324
Codes of Turing Machine
As codes of turing machines are unique for a given turing machine,Say no i have two turing machines ,one for even a's and other for odd a's over the input a,b. Now both these machines will have same transition function but ... and codes of turing machine is the representation of transition function,so how do these two turing machines will have different codes?
As codes of turing machines are unique for a given turing machine,Say no i have two turing machines ,one for even a's and other for odd a's over the input a,b. Now both t...
rahul sharma 5
1.9k
views
rahul sharma 5
asked
Apr 11, 2018
Theory of Computation
turing-machine
theory-of-computation
self-doubt
+
–
1
votes
0
answers
325
Introduction to Computer Theory
Construct a Turing Machine for the language of all strings of this form $L= \{(a^m)(b^n) \mid {\text{n is a multiple of m, and m belongs to N}\}}$
Construct a Turing Machine for the language of all strings of this form$L= \{(a^m)(b^n) \mid {\text{n is a multiple of m, and m belongs to N}\}}$
The Capricorn
217
views
The Capricorn
asked
Apr 5, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
1
votes
0
answers
326
Turing Machine
$L(M)$ = Contains atmost $10$ Strings ? Is it Recursively enumerable ? According to me its Not. Because according to Rices theorem there exist a non monotonic property which makes it Non recognizable. because $T_{yes}$ = $\phi$(i.e. NULL) and $T_{no} = (a+b)^* $ say $\Sigma = \{a,b\} $ and $T_{yes}$ is proper subset of $T_{no}$ Hence its not Recursively enumerable right?
$L(M)$ = Contains atmost $10$ Strings ? Is it Recursively enumerable ?According to me its Not. Because according to Rices theorem there exist a non monotoni...
Na462
335
views
Na462
asked
Apr 4, 2018
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
327
Decidability
A turing machine $M$ halts if started with a blank tape. This is undecidable . Can somebody explain this in easiest way possible.
A turing machine $M$ halts if started with a blank tape. This is undecidable . Can somebody explain this in easiest way possible.
Saurav
516
views
Saurav
asked
Mar 19, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
0
votes
1
answer
328
Decidability
Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$. Can somebody explain the solution.
Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$.Can somebody explain the solution.
Saurav
307
views
Saurav
asked
Mar 19, 2018
Theory of Computation
theory-of-computation
turing-machine
+
–
3
votes
2
answers
329
what type of language
{$<M>\mid M$ is a $TM$ that doesn't accept any even number} what type of language is it? Recursively enumerable Recursive Not recursively enumerable none of the above
{$<M>\mid M$ is a $TM$ that doesn't accept any even number}what type of language is it?Recursively enumerableRecursiveNot recursively enumerablenone of the above
Sambit Kumar
725
views
Sambit Kumar
asked
Mar 15, 2018
Theory of Computation
decidability
turing-machine
theory-of-computation
+
–
0
votes
1
answer
330
Self Doubt on Decidability
Here in this video https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87 professor is explaining that Turing Machine that accept something is recursively enumerable. We would run multiple inputs on turning machine in parallel using ... there are even two strings that are being accepted won't we get to know using the same method ?
Here in this video https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87 professor is explaining that Turing Machine that accept something is recu...
Jeevesh
410
views
Jeevesh
asked
Mar 4, 2018
Theory of Computation
theory-of-computation
turing-machine
decidability
shai-simonson
+
–
Page:
« prev
1
...
6
7
8
9
10
11
12
13
14
15
16
17
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register