search
Log In
0 votes
59 views
CS4820 Spring 2013 Notes on Turing Machines 19/26

(e) ever moves its head more than 481 tape cells away from the left endmarker on input
 ε ?

 

(f) accepts the null string ε ?

(g) accepts any string at all?(h) accepts every string?(i) accepts a finite set?(j) accepts a recursive set?

 

(k) is equivalent to a Turing machine with a shorter description???
in Theory of Computation
edited by
59 views

1 Answer

0 votes
Anyone?

Related questions

0 votes
0 answers
1
194 views
How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?
asked Sep 8, 2018 in Theory of Computation aambazinga 194 views
0 votes
1 answer
2
113 views
Let E={<M>| M is a DFA that accepts some strings with more 1's than 0's} Show that E is decidable. How can E be decidable. How can a DFA compare between number of 1's and 0's. From the question I know that it's not talking about all, but some. The things is even some should not be decidable. isn't it?
asked Sep 8, 2018 in Theory of Computation aambazinga 113 views
1 vote
1 answer
3
216 views
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
asked Aug 10, 2018 in Theory of Computation manisha11 216 views
0 votes
0 answers
4
215 views
Consider <M> be the encoding of a Turing Machine as a string over alphabet Σ = {0, 1}. Consider L = {<M>⏐M is TM that halt on all input and L(M) = L′ for some undecidable language L′}. Then L is .... can anyone explain the sentence in Bold and bold & italics ?? i didnt get L(M).
asked Jul 31, 2018 in Theory of Computation daksirp 215 views
...