Register

Recent questions tagged turing-machine

1 votes
1 answer
276
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.
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
1 votes
1 answer
278
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/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf
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/c...
User Avatar
0 votes
0 answers
282
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 B)TM halts and rejects the input C)TM hangs and accepts the input D)TM never halts.
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
0 votes
1 answer
287
Turing machine
is multi dimension Tm contain multiple tape or just a single tape, arrange differently?
is multi dimension Tm contain multiple tape or just a single tape, arrange differently?
User Avatar
0 votes
0 answers
288
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
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 votes
1 answer
290
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 it falls?
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 votes
2 answers
291
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
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 votes
1 answer
293
Turing machine
What is the meaning of non trivial property related to a language. Please explain with an example.
What is the meaning of non trivial property related to a language. Please explain with an example.
User Avatar
0 votes
0 answers
295
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
User Avatar
0 votes
0 answers
297
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?
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 votes
0 answers
299
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 Γ.
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
1 votes
1 answer
300
TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$What is complement of D and is it Decidable, Turing recognizable or not Turing recogni...
User Avatar
Page: