# Questions tagged [turing-machines]

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

2,198 questions
Filter by
Sorted by
Tagged with
12 views

31 views

### Showing Turing machines are more computationally powerful than Finite State Machines

I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to ...
20 views

### Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}

I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
15 views

### Proving set of register machines that halt before k steps for some input is non-recursive

Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as:  f(n) = \begin{cases} 1 & \exists m \text{ such ...
202 views

### How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
19 views

### Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
22 views

### Turing machine accepting square

I'm trying to figure out following assignment and I could use your help, because I'm stuck. Task: Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. ...
43 views

38 views

### What is wrong with this "proof" of $coNP = NP$? [duplicate]

I am wondering why the following "proof" of $coNP = NP$ does not work: $\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides ...
### Is it true that $P = coNP$?
I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an ...