# Questions tagged [turing-machines]

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

1,993 questions
Filter by
Sorted by
Tagged with
33 views

415 views

148 views

### Is determining if a Turing Machine stops for at least one entry decidable?

I can't find how to prove the decibility with a reduction. EDIT: I've tried the reduction from the halting problem and the aceptance problem. Stopping for at least one entry has infinite inputs (you ...
42 views

### Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
33 views

25 views

### Probabilistic Turing machine - Probability that the head has moved k steps to the right on the work tape

I have a PTM with following transition: $\delta(Z_0, \square , 0) = \delta(Z_0, \square , L, R)$, $\delta(Z_0, \square , 1) = \delta(Z_0, \square , R, R)$ Suppose that this PTM executes n steps. ...
90 views

### What is the semantics of a Turing machine?

Can we formalize the operational/denotational semantics of a Turing Machine? Is there any formalization in literature?
37 views

### Is there a way to hash a turing machine?

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
82 views

### Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^ā\}$?

I'm having a lot of problems trying to make a Turing Machine that accept that language, is it even possible to make it? and if so, how can I proceed to make the Turing Machine?
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that \$\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...