# Questions tagged [turing-machines]

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

1,999 questions
Filter by
Sorted by
Tagged with
6 views

### EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
103 views

### is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in ...
20 views

### 1-Tape Non-deterministic Turing machine and non-palindromes

I have to design a Non-deterministic 1-Tape Turing machine that accepts only non-palindromes in O (n log n). But my best shot was only in O(n^2). How can I use the properties of NTM on a single tape ...
30 views

205 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 ...
145 views

### Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
69 views

### How this language belong to R?

Consider the following language $$L= \{ \langle M\rangle | \text{ M is a TM, and L(M)\in coRE} \}$$ I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
36 views

### surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
176 views

### Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
78 views

### Why do we create universal turing machines?

Why do we create Universal Turing Machine explicilty to simulate the run of a word (say, $w$) on a Turing Machine $M$, given the description on it? Can't we just run $w$ on $M$ itself? I don't see the ...
32 views

### If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$

I found the following question with an answer here, but I can't understand the steps of the solution. Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive. Solution....
7k views

### Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1,L_2 \in RE - R$ , I want to prove or disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$ What I did: I think any ...
63 views

### Decidability of Turing machines and misconceptions on the halting problem

In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability ...
31 views

### Halting (on empty input tape) for an infinite subset of all Turing machines

As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem. But what if, instead ...
30 views

### De morgan's law in formal language

I found in some exercise in computation the following step: I can't understand why is it equal terms, based of what I know about De morgan's law: OR should be replaced by AND where $w=\varepsilon$ ...
39 views

### Show that if $SAT \in P/klog(n)$ then $SAT \in P$

Show that if $SAT \in P/klog(n)$ then $SAT \in P$ Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$. Since $SAT \in P/klog(n)$, ...
55 views

### What is the actual scope of the Halting Problem impossibility result?

Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function ...
24 views

### Showing semidecidability without using diagonalization

All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down ...
52 views

### What is the contradiction in the proof of the halting theorem?

In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string ...
335 views

### Prove that PRE-WORK-POST is Turing Complete

This is a homework question and I am trying to fully understand what I have to do and how to go about it. Therefore, I don't want full answers to the question. The programming language PRE-WORK-POST ...
34 views

### Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions. My ...
168 views

### How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
I found the following answer: $L_{17} = \{ \langle M \rangle \mid \text{$M$is a TM, and$M$is the only TM that accepts$L(M)$} \}$. R. This is the empty set, since every language has an infinite ...
The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...