Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
35 views

Is there a mapping reduction of E(tm) to OVERLAP(tm)?

$E_{TM}=$ { < $M$> $|$ $M$ is a TM; $L(M)$=$\varnothing$} Where $L(M)$ is the language accepted(recognized) by $M$. $OVERLAP_{TM}=$ {< $M_{1}$,$M_{2}$> $|$ $M_{1}$,$M_{2}$ are TMs; $L(M_{1})\...
3
votes
2answers
251 views

Proof that Turing machines and computers have same power

How do we prove that any logical circuit can be simulated by a Turing machine? For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, ...
1
vote
1answer
39 views

M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time

$M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape. let $c_{1}, c_{2}$ be two configurations of $M$. A configuration is defined like this: $uqv$ where $(q\in Q; u,v\...
0
votes
1answer
62 views

QTM & Halting problem [duplicate]

"Can QTM (Quantum Turing machine) solve halting problem" Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the ...
4
votes
0answers
85 views

Is every von neumann machine turing complete? [duplicate]

I understand that TM is a 'Model of Computation' which tells us about the computational power of a machine while Von Neumann Architecture is a 'System Architecture' that tells us about how the machine ...
0
votes
1answer
44 views

Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$ [on hold]

my solution is that $L\in co-RE$ by showing that $\overline{L}\in RE$ TM $M$ on input:$\langle M_1,M_2,w\rangle$ Build TM $M_1,M_2$ Simulate $M_1$ on $x\in\Sigma^*$, before that check if $x\neq w$ ...
-1
votes
1answer
87 views

Prove {0^n OR 1^2n OR 2^3n | n >= 0} is not context free

How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n >= 0} is not context free This isnt the same language as {0^n1^2n2^3n | n >= 0} as this language the numbers need to be in order.
2
votes
1answer
140 views

SAT Solving + Turing Machines

I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques: Randomness Heuristics Backtracking SAT is just one example ...
2
votes
1answer
44 views

If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?

I tried to solve it as the following: $$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$ I'll show that $\overline{L}\not\in RE$ by ...
-1
votes
1answer
1k views

Turing machine that accepts L = {a^nb^2n : n ≥ 0}

write a Turing machine that accepts L = {a^nb^2n:n ≥ 0} where there are double the amount of b's in comparisons to the amount of a's. So aabbbb would be accepted but aabbaabb would not. I am unsure of ...
1
vote
1answer
38 views

How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

I'm asking this, because in every exercise I check if I can relate it to one of the things I know, like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{...
0
votes
2answers
202 views

Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
1
vote
1answer
60 views

Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

I thought about these languages: $$L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$$ $$L_{2} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid ...
6
votes
0answers
67 views

Can all computational complexity results be expressed in terms of programming languages?

Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems. However, on a more formal ...
3
votes
1answer
51 views

Definition of a TM accepting a word

The following is a quote from Sipser's "Introduction to the theory of computation" A Turing machine $M$ accepts input $w$ if a sequence of configurations $C_{1}, C_{1}, \ldots , C_{k}$ exists, ...
0
votes
1answer
55 views

Turing machines and their computational power

Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the ...
1
vote
2answers
527 views

A Turing Machine that Doesn't Move to the left [duplicate]

My question is if the following statement is true or false: Does every turing-recognized $B$ language has a turing machine $M$ that recognizes $B$ and fullfiles the following statement: For ...
0
votes
0answers
30 views

Acceptable language in computational complexity

What are acceptable languages in computational complexity? Is it Turing recognizable? I was searching online and found this description. Does anyone beg to differ?
0
votes
0answers
67 views

Is a Turing Machine able to reduce a grammar by chomsky hierarchy? [duplicate]

If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3? ...
0
votes
0answers
40 views

Reduction of HP to L3

I want to make the following reduction: HP is the Halting Problem: HP = {w#x | w, x ∈ {0,1}* , Mw halts on input x} w is the binary coded turing machine Mw. L3 is the problem which asks, if M ...
1
vote
1answer
91 views

Recognize end of Input in a Turing Machine

If I have a turing machime TM, can I recognize end of input on the tape? I know that the "end of input" in a turing machine is signaled with a special character, $\sqcup$. Can I do this - Let $...
2
votes
0answers
30 views

Reference request: Algorithms on Turing Machines

Is there a good survey or some papers with algorithms in the Turing machine model? I know the paper STRING-MATCHING AND OTHER PRODUCTS contains Turing Machine version of KMP. Are there any other such ...
1
vote
1answer
31 views

Obtain all possible Turing Machines from a Universal Turing Machine

Knowing how a Universal Turing Machines works and its capabilities, is it possible to obtain the collection M = {M0 , M1 , M2 , M3, … } of all possible Turing Machines? If so, can we prove that a ...
1
vote
1answer
44 views

Turing machine Representation for string of 3 letters

Can someone explain to me what this statement implies? I am assuming that it means that a string consisting of three characters repeated. What I don't understand is if the repeated string is all 0s or ...
2
votes
1answer
237 views

Verifier - Complexity Theory

A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\...
0
votes
1answer
66 views

Obtaining a computational history of a Turing Machine

I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In ...
1
vote
1answer
74 views

Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

For example: This looks like a context free grammar: 𝑆 → 𝑄𝑅𝑇 𝑄 → 𝑎𝑄 | 𝑎 𝑅 → 𝑏𝑅 | 𝑏 𝑇 → 𝑐𝑇 | c but it can be reduced to this regular language: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
0
votes
2answers
179 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 ...
7
votes
3answers
1k views

Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?

I have seen the following statement, and I don't quite understand the reasoning behind it: If a Turing machine repeats the same configuration twice, it must be in an infinite loop. I thought that ...
0
votes
2answers
78 views

Turing Machine DTime(log(n))

An Exercise from a Textbook: L3 := {ε,01,0011} is L3 ∈ DTime(log(n)) The answer says yes it is, it is even in DTime(1). How is this possible? I would say it takes at least n steps to check ...
1
vote
1answer
74 views

Turing decider Halting Problem

Wiki and my classes Textbook defines a decider as: In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing ...
2
votes
1answer
173 views

Rice's theorem application on a language that resembles ETM

I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages. The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(...
0
votes
0answers
84 views

Non deterministic turing machine vs Turing machine with stay option

According to book by Peter Linz, the transition function for non deterministic Turing machine is: $Q\times \Gamma\rightarrow 2^{Q\times \Gamma\times \{L,R\}}$ where, $Q$ is a set of ...
2
votes
1answer
39 views

Potential General Model of Computation with Physics?

I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input ...
1
vote
2answers
51 views

Does the undecidability of the halting problem require Turing Machines to be enumerable?

I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
1
vote
1answer
27 views

Given a Turing machine M, is there a TM that computes the number of states M has?

I've seen it used but I can't think of a way to construct such TM. Would appreciate any help!
1
vote
2answers
164 views

functional vs state-based

As mentioned in Lambda Calculus - Computerphile, Alonzo Church's method is functional where a function as a blackbox, takes an input, processes, and produces an output, and Turing machines ...
1
vote
0answers
101 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
2
votes
1answer
151 views

P, NP Problem and Turing Machines

My first question here, I think this will be an easy one. As for definition: NP: NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. (...
1
vote
1answer
120 views

Turing machine that does not halt on any input

I'm struggling to find a way to show that $$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$ is undecidable. Should I use reduction? If so, reduce this to what &ndashp ...
2
votes
2answers
48 views

Is every reduction function $f \in O(n)$?

I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions. We defined reduction as following (If I translate a term false please correct me.): $ ...
3
votes
1answer
456 views

Can a weaker version of the Halting Problem be solved?

I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this: Assume that some machine $...
0
votes
0answers
53 views

Decidability of language that contains all TM encodings that accept at least one word

I have a language that contains all encodings of the Turing machines that accept at least one word. Is this language recursive, recursively enumerable, or neither?
1
vote
2answers
134 views

Why does the Turing Machine allow for multiple final states?

Why does the Turing Machine allow for multiple final states when it would be simpler yet equivalent to work with just one? Why allow additional unnecessary states? Is there some historical reason for ...
0
votes
1answer
39 views

Why we write “Ignore the input ” when describing an Enumerator?(Sipser Chapter 3)

The Theorem and its proof is given below: But I am wondering why we write "Ignore the input " when describing an Enumerator? could anyone explain this for me please?
-1
votes
1answer
36 views

mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$

If $$ A_n = \{ x | n \in W_x\} \ where \ W_x \ is \ domain \ of \ M_x $$ how can I show that $$ \forall i,j \ \ \ A_i \le_M A_j $$
0
votes
1answer
355 views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
2
votes
1answer
128 views

Determining whether the language of a DFA is closed under reversal

The question and its answer is given below: Let $S = \{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\}$. Show that $S$ is decidable. ...
2
votes
1answer
100 views

Prove that the TM which would go over the leftmost position is not decidable

Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the ...
2
votes
0answers
167 views

Simulating a turing machine with DPDA with two stacks

In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...