Register

Recent questions tagged turing-machine

0 0 votes
0 0 answers
791
791 views
Conversion of multitape TM to single tape TM
User Avatar
0 0 votes
0 0 answers
681
681 views
decidablilty
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be cor...
User Avatar
0 0 votes
0 0 answers
1.7k
1.7k views
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation?MEMBERSHIP PROBLEMEMPTINESS PROBLEMCOMPLETENESS ...
User Avatar
0 0 votes
0 0 answers
622
622 views
Zeal Test Series 2019: Theory of Computation - Turing Machine
I think c is not true please correct me if i am wrong
User Avatar
0 0 votes
0 0 answers
889
889 views
Self doubt
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every...
User Avatar
1 1 vote
1 1 answer
1.2k
1.2k views
Zeal Theory of Computation module.
Does the statement given below is true?If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
User Avatar
0 0 votes
1 1 answer
586
586 views
self doubt - Turing Machines
I have doubt in the following question:Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language...
User Avatar
1 1 vote
1 1 answer
694
694 views
Turing Machine lecture content stan..
A = { <M,w | M is a TM that accepts W}what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/cla...
User Avatar
2 2 votes
2 2 answers
2.8k
2.8k views
Turing Machine-Techtud
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language$B)$ CFL$C)$ CSL$D)$ NoneAns given CSL b...
User Avatar
3 3 votes
3 3 answers
8.2k
8.2k views
MadeEasy Subject Test 2019: Theory Of Computation - Decidability
Consider <M be the encoding of Turing Machine as string over alphabet $\Sigma$ = {0,1}.Consider L= { <M>| M is TM that halt on all input and L(M) = L for some undecidab...
User Avatar
1 1 vote
3 answers 3 answers
2.7k
2.7k views
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
User Avatar
0 0 votes
0 0 answers
542
542 views
NIELIT Qtn
Consider the following possible outcomes of executing a Turing machine over a given input. Which of the following outcome is NOT possible?A)TM halts and accepts the input...
User Avatar
3 3 votes
3 answers 3 answers
2.0k
2.0k views
Zeal Test Series 2019: Theory of Computation - Turing Machine
i marked the a) answer is D)please explain it
User Avatar
0 0 votes
0 0 answers
695
695 views
Decidability Doubt
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$$L_2 = \{ \text{<M>} | \ \text{M is a TM,...
User Avatar
0 0 votes
0 0 answers
1.0k
1.0k views
Gateforum Test Series: Theory of Computation - Turing Machine
anyone please explain this in detail
User Avatar
0 0 votes
0 0 answers
600
600 views
Gateforum Test Series: Theory of Computation - Turing Machine
Im not getting the intution behind this can any one explain
User Avatar
0 0 votes
1 1 answer
510
510 views
Turing machine
is multi dimension Tm contain multiple tape or just a single tape, arrange differently?
User Avatar
0 0 votes
0 0 answers
670
670 views
Theory of Computation : Turing Machine
Correct ans is Type - 0. My doubt is LBA is also TM and LBA belongs to type - 1 then why ans is not type - 1
User Avatar
0 0 votes
1 1 answer
850
850 views
Decidability
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category...
User Avatar
1 1 vote
2 answers 2 answers
1.0k
1.0k views
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps.Please elaborate.
User Avatar
0 0 votes
0 0 answers
510
510 views
Recursive language
https://gateoverflow.in/86546/theory-of-computation-22Total recursive functions are similar to a) Recursive Languages b) Recursive Enumerable languages c) can not re...
User Avatar
0 0 votes
1 1 answer
450
450 views
Turing machine
What is the meaning of non trivial property related to a language. Please explain with an example.
User Avatar
0 0 votes
0 0 answers
804
804 views
Undecidability
L1:{<M | there exist a Turing machine M' such that <M>$\neq$<M' and L(M) = L(M')}How this problem becomes trivial? and if it non-trivial then please explain why is that s...
User Avatar
0 0 votes
0 0 answers
544
544 views
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
User Avatar
0 0 votes
0 0 answers
1.3k
1.3k views
Ace Book
User Avatar
0 0 votes
1 answers 1 answer
592
592 views
TANCET 2011 TURING MACHINES
Time taken by one tape TM to simulate n moves of k-tape TM is1) O(n)2) O(n^k)3) O(n^2)4) None of the above
User Avatar
0 0 votes
0 0 answers
334
334 views
Turing Machine
A turing machine $\left \langle M,w,i \right \rangle$ where $M$ is TM , $w$ is string and $i$ is bit.Is the bit $i$ is encoding at last of the string $w$ or at first?
User Avatar
0 0 votes
0 0 answers
644
644 views
undecidability
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape.how the above problem is solvable?somewhere...
User Avatar
0 0 votes
0 0 answers
389
389 views
Peter Linz Edition 4 Exercise 12.1 Question 14 (Page No. 306)
Consider the set of all n-state Turing machines with tape alphabet Γ = {0,1, B}. Give an expression for m(n), the number of distinct Turing machines with this Γ.
User Avatar
Page: