Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
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
srestha
asked
in
Theory of Computation
Sep 13, 2018
by
srestha
187
views
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?
srestha
asked
in
Theory of Computation
Sep 13, 2018
by
srestha
254
views
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
goluabhinan
asked
in
Theory of Computation
Sep 11, 2018
by
goluabhinan
875
views
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
Na462
asked
in
Theory of Computation
Sep 9, 2018
by
Na462
255
views
turing-machine
recursive-and-recursively-enumerable-languages
decidability
0
votes
0
answers
305
TOC- Undecidability
sidlewis
asked
in
Theory of Computation
Sep 8, 2018
by
sidlewis
423
views
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
surbhijain93
asked
in
Theory of Computation
Sep 7, 2018
by
surbhijain93
2.6k
views
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
Swapnil Naik
asked
in
Theory of Computation
Sep 2, 2018
by
Swapnil Naik
287
views
turing-machine
decidability
1
vote
0
answers
308
Decidability
Ans. D
Na462
asked
in
Theory of Computation
Sep 2, 2018
by
Na462
215
views
decidability
theory-of-computation
turing-machine
2
votes
1
answer
309
Turing Decidable
Na462
asked
in
Theory of Computation
Sep 2, 2018
by
Na462
842
views
theory-of-computation
turing-machine
decidability
0
votes
1
answer
310
Language Represented by TM
Ans. C
Na462
asked
in
Theory of Computation
Aug 30, 2018
by
Na462
501
views
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.
Sumit Singh Chauhan
asked
in
Theory of Computation
Aug 24, 2018
by
Sumit Singh Chauhan
878
views
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?
manisha11
asked
in
Theory of Computation
Aug 16, 2018
by
manisha11
391
views
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
manisha11
asked
in
Theory of Computation
Aug 10, 2018
by
manisha11
761
views
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
manisha11
asked
in
Theory of Computation
Aug 10, 2018
by
manisha11
284
views
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?
Vikas Verma
asked
in
Theory of Computation
Jul 31, 2018
by
Vikas Verma
412
views
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??
Vegeta
asked
in
Theory of Computation
Jul 24, 2018
by
Vegeta
638
views
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
Pooja Khatri
asked
in
Theory of Computation
Jul 13, 2018
by
Pooja Khatri
1.3k
views
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"
Balaji Jegan
asked
in
Theory of Computation
Jul 12, 2018
by
Balaji Jegan
2.4k
views
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?
srestha
asked
in
Theory of Computation
Jun 1, 2018
by
srestha
2.1k
views
decidability
theory-of-computation
turing-machine
1
vote
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$
The Capricorn
asked
in
Theory of Computation
May 30, 2018
by
The Capricorn
226
views
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$.
The Capricorn
asked
in
Theory of Computation
May 28, 2018
by
The Capricorn
202
views
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
Sourav_35
asked
in
Theory of Computation
Apr 28, 2018
by
Sourav_35
277
views
turing-machine
1
vote
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
gauravkc
asked
in
Theory of Computation
Apr 25, 2018
by
gauravkc
5.9k
views
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?
rahul sharma 5
asked
in
Theory of Computation
Apr 11, 2018
by
rahul sharma 5
1.9k
views
turing-machine
theory-of-computation
self-doubt
1
vote
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}\}}$
The Capricorn
asked
in
Theory of Computation
Apr 5, 2018
by
The Capricorn
222
views
theory-of-computation
turing-machine
1
vote
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?
Na462
asked
in
Theory of Computation
Apr 4, 2018
by
Na462
347
views
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.
Saurav
asked
in
Theory of Computation
Mar 19, 2018
by
Saurav
522
views
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.
Saurav
asked
in
Theory of Computation
Mar 19, 2018
by
Saurav
318
views
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
Sambit Kumar
asked
in
Theory of Computation
Mar 15, 2018
by
Sambit Kumar
735
views
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 ?
Jeevesh
asked
in
Theory of Computation
Mar 4, 2018
by
Jeevesh
421
views
theory-of-computation
turing-machine
decidability
shai-simonson
Page:
« prev
1
...
6
7
8
9
10
11
12
13
14
15
16
17
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged turing-machine
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...