# Questions tagged [turing-machines]

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

1,590 questions
Filter by
Sorted by
Tagged with
29 views

### Language which is recursively enumerable but not recursive [duplicate]

Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable ...
24 views

### Turing Machine equivalence in MinTM proof

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows: $C=$ "On ...
42 views

### L(M)=L where M is a TM that can move right or stay, so L is decidable

Suppose that L(M)=L where M is a one tape TM that can move right or stay. I need to Show that L is decidable. I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
27 views

### Böhm-Jacopini theorem

I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never ...
23 views

### What is the intuition behind the relationship between space and time for an algorithm? [duplicate]

I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?
33 views

### What is a trivial language?

I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?
54 views

### Turing Machines proof notations

In context of "Computability", I have went over some proofs for Recursion Theorem using Turing Machine description. A TM $M$ stands for a single tape Turing machine and $\langle M \rangle$ is the ...
69 views

### Prove completeness of a language with Turing Machine

I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling ...
123 views

### What does it mean for a TM to solve a problem?

When we say a TM solves a problem, what does this mean?
17 views

### What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements? I.e. What is the link between the language and the algorithm
13 views

### Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?

A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A. A language L2 is defined as the set of all inputs to which a TM halts and accepts. What is the link ...
20 views

### Can a Turing Machine be defined over many languages?

What does it mean, if possible, for a Turing machine to be defined over many languages?
2k views

### Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct? As I have also seen places where we mention a Turing machine "...
42 views

### D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

Given that a language D has a polynomial verifier, and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space. How can I prove that $D\in P$ ? My idea was to ...
43 views

42 views

### Uncomputably coded model of computation

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
33 views

### Superset of another language and recognizability of turing machines

$L_1$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\}$ $L_2$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\}$ a) Is $L_2$ a ...
45 views

### Is $L = \{ a^n\ |\ a^n \not\in L_n \}$ Turing recognizable (recursively enumerable)?

Say $\Sigma = \{a\}$, $M_1, M_2, ...$ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ...$ are respectively the languages that are recognized by those TMs. We ...
69 views

### Are all compilers Turing Machines?

So the definition of a compiler I got is that: A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No". So does that mean all compilers ...
15 views

### How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
28 views

### One-taped RAM vs Multi-taped RAM

In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently. (Well, actually I'm not ...
259 views

### How does a Turing machine with one tape read its input?

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
35 views

### Turing machine loop and reject example

I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on. My textbook has one example on a reject state and no physical one for loop: Assume that no ...
23 views

### Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register. Suppose the time complexity of M is T(n): ...
32 views

### Complexity of a Turing Machine when changing its alphabet to binary

I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof: For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f ...
30 views

### Recognizably turing machine question (reject / loop)

The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way? Give a deterministic TM D that recognizes L such that ...
54 views

### Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?
29 views

### Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows: "On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to ...
49 views

### Advantages of Lambda calculus over Turing machine and vice versa [closed]

What kind of advantages does Lambda calculus have over Turing machine, and vice versa?
17 views

### What's the difference between Acfg and ALLcfg

In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
85 views

### Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^*$ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
$L = \{M | \text { M is a TM and there exist some string w that contains five 1's such that M halts}\}$ Where $\Sigma =\{0,1\}$ let $w_1, w_2, \cdots, \in \Sigma^*$ be an effective enumeration. We ...