We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [turing-machines]

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

1,631 questions
Filter by
Sorted by
Tagged with
22 views

### Is the language of turing machines, which return epsilon on its own encoding, decidable?

Is the language $\{ \langle M\rangle | f(\langle M\rangle)=\epsilon\}$ decidable? $f()$ means, that the turing machine returns $\epsilon$ on its own encoding and $\langle M\rangle$ stands for the ...
32 views

### Can current quantum computers decide languages that Turing Machines cannot?

I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
15 views

### Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
32 views

### Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
40 views

### Maximum number of configurations of Turing machine after $n$ moves

I came across following question: What are maximum number of configuration of Turing Machine after $n$ moves? The answer given was: $k^n$, where $k$ is a branching factor. And that "branching ...
15 views

### Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...
22 views

### Semidecidable Turing Machine for L={a,b}*

I have a language L={a,b}* over the alphabet {a,b}. How do I build a Turing Machine that semidecides but does not decide this language? Me and my classmates tried using the macro language to solve ...
30 views

### Solution to prove that every recursively enumerable language is accepted by a Turing machine with a single accepting state

In order to prove that every "recursively enumerable language" is accepted by a Turing machine with a single accepting state, my idea is using the following theorem. Theorem: Every nondeterministic ...
30 views

### Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
16 views

41 views

### Is language {M | M halts and print “Hello World”} recursively enumerable?

Is language {M | M halts and print "Hello World"} recursively enumerable? I'm not sure my proof is correct. Let universal Turing machine U start another Turing machine M2 that reads result of work of ...
127 views

### What can't you do without Turing-completeness?

I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose. ...
16 views

1k views

### How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
67 views

### Why is it not possible to prove that two Turing Machines calculate the same function?

I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
49 views

### Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
### How can $A \cup B$ be decidable if $B$ is undecidable?
My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...