Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [turing-machines]

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

0
votes
0answers
12 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 ...
1
vote
1answer
50 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 ...
1
vote
0answers
14 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 ...
1
vote
0answers
53 views

How does a Turing machine with one tape read it's 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 ...
2
votes
1answer
26 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 ...
1
vote
1answer
29 views

How is this language not co-recognizable?

$L = \{ \langle M \rangle \mid M$ is a Turing machine and $M$ halts on all strings that starts with 11} L is not recognizable and not co-recognizable. I get why it is not recognizable easily by ...
0
votes
1answer
23 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 ...
2
votes
1answer
23 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 ...
0
votes
0answers
20 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): ...
1
vote
1answer
26 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 ...
2
votes
1answer
28 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 ?
0
votes
0answers
24 views

How to recognize the Turing machines that accepts 111? [on hold]

L: $\{\langle M \rangle \mid M$ is a TM and $\{111\} \subseteq L(M)\}$. Basically 111 can get accepted by $M$. Proof that this is recognizable: Here is a recognizer $M1$ for L: ...
3
votes
1answer
25 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 ...
2
votes
1answer
75 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 ...
0
votes
1answer
42 views
1
vote
0answers
15 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 ...
1
vote
1answer
19 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

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^*$ ...
2
votes
2answers
59 views

Is finding a single digit of a computation is as hard as finding the computation?

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages: $$\begin{align*} L_1 &...
1
vote
1answer
32 views

Dove tailing questions about accepting language

$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 ...
2
votes
2answers
83 views

Changing a complete undecidable turing machine language

$L = \{\langle M\rangle\mid \text{M is a TM and }L(M) = \{101\}\}$ meaning M accepts only the string $101$. Which is neither co-recognizable / recognizable. Can be proven easily by $HALT \leq_m L (\...
0
votes
2answers
42 views

Are Context Sensitive Languages Turing Complete?

Related questions: Can regular languages be Turing complete? Why are Linearly Bounded Turing Machines more powerful than Finite State Automata? https://stackoverflow.com/questions/14589346/is-c-...
0
votes
1answer
74 views

What's the purpose of the non-deterministic Turing machine?

(*) Acronyms NTDM := non-deterministic Turing machine. TM := deterministic Turing machine. (*) Consider the following idea The NTDM is able to follow, in parallel, all paths of the tree of the ...
2
votes
1answer
78 views

How to come up with a language that is recognizable but not co-recognizable?

Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^*$ iff $A ...
2
votes
1answer
41 views

How to reduce EQU to UNI?

Let $$\texttt{EQU}=\{u\#v \mid T(M_u)=T(M_v)\} \\ \texttt{UNI}=\{w \mid T(M_w)= \Sigma^*\}$$ How can you prove $\texttt{EQU} \leq \texttt{UNI}$? The idea I have so far is, to simulate the TM that ...
3
votes
1answer
43 views

How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$. I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
3
votes
1answer
39 views

Pebble game lower bound?

This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433. Why is it not considered proof of constructive example for a function in ...
2
votes
2answers
48 views

Turing machine reduction task

I am having trouble solving the following task: Given is the language $$D=\{ \langle M, w \rangle \mid \text{$M$ is a Turing machine and $M$ enters all states on input $w$}\}$$ Prove that $D$ ...
3
votes
1answer
72 views

How does Rogozhin's (2, 18) universal turing machine work?

I am trying to understand Rogozhin's (2, 18) universal turing machine by stepping through a simple 2-tag encoding that I believe should loop forever: a -> aa ...
2
votes
1answer
27 views

Turing machine diagram for twice number of 0 than 1 [closed]

Can anyone help me with a Turing machine diagram for twice number of 0 than 1
3
votes
1answer
53 views

Is the language of all TMs *not* accepting a given string, Enumerable?

Is the following language in RE? $$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$ I could use Rice's Theorem with the property $P = \{L : 010\text{ is not in }L\}$ to show ...
1
vote
1answer
21 views

Universal Turing machine and virtualization technology

I was wondering if virtualization technologies (VmWare, virtual box) are possible thanks to the theoretical existence, translated into practice, of the concept of universal turing machine or if the ...
0
votes
0answers
12 views

building turing machine for busy beaverproblem

I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
3
votes
1answer
51 views

Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length

Prove that the language $$ L=\{\langle M \rangle \mid \exists M_1, M_2 : L(M_1)=L(M_2)=L(M) \text{ and } |\langle M_1 \rangle| < |\langle M \rangle| < |\langle M_2\rangle| \}$$ is not ...
2
votes
1answer
53 views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
0
votes
0answers
191 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let $$L_1 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and doesn't accept $\varepsilon$}\}$$ where TM is ...
1
vote
1answer
32 views

Efficiently deciding whether TM accepts all inputs in at most $k$ steps

I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are ...
1
vote
1answer
19 views

Turing recognizable language between languages that aren't recognizable?

Let $L_{1},L_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L_{1} \subseteq L \subseteq L_{2}$. Is $L$ also not Turing recognizable? I am inclined to ...
1
vote
1answer
50 views

Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?

I'm working on the following problem: Is the following language Turing recognizable (recursively enumerable) ? $$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not > ...
2
votes
1answer
29 views

How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
1
vote
1answer
69 views

I have trouble translating Turing machine language, can you help me break down language notation to English?

My problem is I don't have many issues with creating a Turing machine state table when given a string such as 01101, my issue arises when I am presented with a problem which requires the Turing ...
2
votes
2answers
56 views

How is diagonalization a valid argument for the undecidability of the halting problem?

All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference. ...
1
vote
1answer
67 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
0
votes
2answers
392 views

turing machine for the language L ={w#w' where w<w'}

I'm blocked with a question for a long time. L ={X=w#w' where w < w' and w,w' in {0,1}* } So i'm trying to find : 1-a deterministric turing maching for the language L. 2-a non deterministic for ...
2
votes
1answer
1k views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
0
votes
1answer
48 views

Turing machine - Transition between two states by more than one condition allowed?

Is it allowed to transit between two states $q$, $q'$ by more than one condition? Thank you in advance. e.g. coming from state $q$, the conditions $(0,0,L)$ and $(1,0,L)$ would lead to the same state ...
0
votes
2answers
175 views

Turing machine different accepting states

I want to design a Turing machine that accepts at most 3 0s. Now, I have designed one, which goes to accept state overtime it sees 1, 2 and 3 0s and rejects any further 0s. I wanted to know if it is ...
1
vote
1answer
56 views

how can this function be computed in polynomial time in regards to its input?

i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length) defining a function from assignments ...
2
votes
1answer
147 views

Turing machine with semi infinite tape - Prove by construction

I'm studying constrained Turing Machines. There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
12
votes
3answers
3k views

Why is the blank symbol not considered part of the input alphabet of a Turing machine?

Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet. I wonder what goes wrong when you would make it part of the input alphabet, because ...
4
votes
1answer
62 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...