# Questions tagged [turing-machines]

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

1,894 questions
Filter by
Sorted by
Tagged with
7 views

### Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages? I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and ...
19 views

### Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes. In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
37 views

### Universal Turing Machine algorithm

First, I learned this based on these facts: Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$. Any computation rules that can use to simulate any possible ...
53 views

### Prove that a language is decidable

I need some help to prove that the language is decidable. $K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}. It tried to make an algorithm ...
108 views

### Turing Machine - Analyze brackets

For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets. The only tape symbols ...
27 views

### Incomputable sets of low degree vs Rices theorem?

I have heard that there are sets that are not computable, but are lower in degree than the halting problem. How does this not contradict Rice's theorem? Are there any concrete examples of such sets?
19 views

### How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?

Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs? By a Halt1 oracle I mean that we have the ability to decide if Turing ...
51 views

### Halting problem for turing machines with one input

My question is: Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs. ...
57 views

51 views

### Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
81 views

### How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $M = (Q,Σ,Γ,δ,q_0,q_a,q_r)$ and $M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$. We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more ...
Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...