# Tagged Questions

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

26 views

### A question on the graph induced by the transition function of a deterministic Turing machine

Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$. Let $Q$ denote the statespace of $M$'s finite control. Let $G_M$ be the ...
18 views

### Timely lower bounded Turing machines

Let M be a deterministic Turing machine wich has the properties: 1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$ 2) $\forall a \in \Sigma: t_M(a) \ge 1$ (Also 2) should be obvious for ...
77 views

### Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
33 views

### Is this language semi-decidable?

Let $M_w$ be the DTM encoded by the binary string $w$ and let $$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$ I've already proved that this language is undecidable (the ...
44 views

### Is unrestricted grammar equivalent to deterministic Turing machine?

Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second ...
25 views

61 views

### TM that accepts all strings is recognizable or not?

Lets say we have the following language $L = \{\text{$M$is a TM such that$M$accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct ...
14 views

### Uses of unary or sparse languages in other models

In the turing model we have the statements that if there is an unary or sparse language that is NP complete then P=NP and if there is a Turing reduction from an NP complete problem to an unary or ...
60 views

### How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}. How can I prove that this is undecidable? I have considered trying to build the ATM ...
34 views

### Example of a simple recognizable language, whose complement is not recognizable

Can any one provide me with a simple language that is recognizable, but that it's complement is not? I have read that recognizable languages may have this property but I am yet to find an example to ...
108 views

### Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?

Consider a chatbot that runs on a turing machine. It has some restrictions: It must talk to itself 1 sentence at a time. It is forced to use English words to reply. (so only around say 80 k ...
40 views

### If I prove that a language is not a CFL, can I assume it is Turing-Decidable?

Lets say I have just used the pumping lemma to prove a certain L language is not CFL. If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to ...
27 views

### Can you do operations on the halt state of a turing machine?

As the title says, can operations be performed by a turing machine after it has transitioned to the halt state like shown in the following image.
53 views

### Turing Completeness of System Which Randomly Fails to Complete Calculations

If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python ...
25 views

142 views