# Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

230 questions
Filter by
Sorted by
Tagged with
197 views

### Reducing recursive languages

I need a clarification related to the following situation. Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are ...
299 views

184 views

### If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?

Assuming that f(n) >= n. If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, ...
348 views

### Variant of Turing machine

How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
98 views

### Determining if a TM decidable or not, with limited information

Were being asked to determine the whether this Turing Machine is decidable or not "Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine ...
303 views

### What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
37 views

397 views

### Prove that this language is decidable or undecidable

Is the following language decidable? L = {(M) : M performs at least 100 steps on every accepted input.} I tried to use reduction from the halting problem, but still no dice.
110 views

### Where does the need for conditionals (if, switch, jump tables, etc…) truly arise? [duplicate]

I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind. When we ...