This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
Questions tagged [turing-machines]
954 questions
0
votes
1 answer
$ E_{\text{TM}} = \{ \langle M \rangle \mid L(M) = \varnothing \} $ is undecidable.
In this proof, we need to convert the input from $ \langle M,w \rangle $ to $ M_{1} $ as $ E_{\text{TM}} $’s input is only a Turing Machine. However, I couldn’t understand the construction of $ M_{1} $, mainly I couldn't understand what “On input $…
mahmudul hasan
- 101
0
votes
1 answer
How to prove that One Way infinite tape Turing Machine is Turing Complete?
I have always worked in 2 way infinite tape and most probably I think that was the first represented as Turing Machine. How can I emulate One-way Turing Machine to Two way Turing Machine.
-1
votes
1 answer
Why does a Turing machine take $n^k$ steps for computing an input?
I was reading about Cook's Theorem for Turing machine. In its proof, it is said that the Turing machine would take at most $n^k$ steps (where $k$ is an integer and $k > 0$) to compute an input of length $n$.
This is probably assuming that the Turing…
-1
votes
1 answer
Draw a Turing machine that recognizes $\{w \in\{0,1\}^*\,|\,w\text{ contains even number of 1's}\}$
Draw a Turing machine that recognizes the language $\{w \in \{0,1\}^*|w \text{ contains even number of 1's}\}$
This is where I am at:
Brice Petty
- 11
-1
votes
1 answer
How to design a turing machine that recognizes any language?
here I have a problem.
Design a turing machine that recognizes the language of all strings of even length over alphabet
{a, b}.
soln:
Let turing machine is
$Tm =(Q, \Sigma, \Gamma, \delta, q_0 , h)$
$\Sigma=\{a, b \}$
$\Gamma=\{ a, b ,\# \}$
$Q…
Bishwas
- 3