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
1
vote
1answer
137 views

Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ ...
1
vote
2answers
145 views

Can I program a universal Turing machine to accept arbitrary input encodings?

I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find ...
0
votes
1answer
105 views

Proving a set is semi-decidable

Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q. To prove that $S$ is semi-decidable, I've tried to use the equivalence: ...
3
votes
2answers
153 views

Does Halts reduce to all other undecidable languages?

In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
0
votes
1answer
51 views

Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
1
vote
1answer
119 views

Circuits vs Turing Machines in the “nonuniform model of computation”

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...
1
vote
1answer
75 views

Proof for Turing Machines being able to simulate any algorithm in the same time complexity

I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the ...
2
votes
1answer
120 views

What is the algorithm for a decider to get the language accepted by a DFA?

I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be ...
1
vote
1answer
175 views

Proof that the Blank Tape Halting Problem is undecideable [duplicate]

I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not) Proof: Suppose that the Blank Tape ...
1
vote
2answers
77 views

What is the type signature of a Turing Machine?

Maybe my question is a bad question, but if it is, I want to know eactly how it is a bad question. Suppose we have some Turing machien $M$ that takes as input a natural number $n$ in the form of a ...
1
vote
2answers
478 views

What is the “description” of a Turing machine?

I am currently reading about the Halting Problem in my course on the theory of computation and the following was given in my lecture slides Now my question is that if $d$ is the description of a ...
1
vote
1answer
18 views

Complexity of not P or EXPTIME

Question 1: Is it possible to create an algorithm for deterministic Turing machine that will run not in P neither EXPTIME? Question 2: For me it seems that the answer for my question is ...
1
vote
2answers
41 views

Is every language over any alphabets is accepted by automata?

The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general ...
2
votes
2answers
315 views

Prove: Every decidable set is Turing reducible to the empty set

Question- Prove: Every decidable set is Turing reducible to the empty set. Can anyone help me with this please? All reductions tutorials I've seen use practical examples of reduction such as sipser'...
1
vote
1answer
226 views

How to prove the following: Every set is Turing reducible to itself

Question: Prove the following: Every set is Turing reducible to itself. If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as ...
0
votes
1answer
174 views

Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language?

Is the complement of every semi-decidable language a semi-decidable language?
1
vote
1answer
100 views

Decidability of $E_{TM}$ and $A_{TM}$ for “erasing” Turing machines

Why is the $A_{ETM}$ for a variant of a Turing machine (an erasing Turing machine), where changing a tape symbol to a nonblank symbol is prohibited, decidable? Why does the following diagonalization ...
0
votes
1answer
49 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 ...
-1
votes
1answer
50 views

Alan Turing Halting Problem with C code which check how TM works

If we want to write to write a C code, to check if halting problem halts on a given input, how it will be ? I tried this code as shown below but stuck int main(int argc, char * argv[]) { <...
1
vote
1answer
188 views

Prove if a property of a Turing Machine is decidable or not, how can I do it?

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not. For example, if a have this: (1.1) "M always halts within 100 steps" or this (1.2) "M recognizes ...
0
votes
1answer
51 views

How can I check if $n >m$ in $a^n b a^m$?

How can I design a Turing machine that takes string $a^n b a^m$ and check if $n>m$ then convert the string to $a^{n-m}$, otherwise reject it?
1
vote
1answer
837 views

Turing machine that converts decimal to binary [closed]

I'm a beginner in Turing machine computation and want to design two TMs; one that converts decimal number to binary, and other one that converts binary to decimal. Could anyone help me design these ...
1
vote
1answer
34 views

If a language is contained in other langauge, is it of the same complexity?

If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P? Thanks :)
1
vote
2answers
63 views

How to define (logically) the complement language?

I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language: $$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{...
0
votes
2answers
47 views

How many bits representation of data on tape of Turing machine consumes

I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory. For signed number it is obvious: encode sign as a ...
3
votes
1answer
108 views

Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?

Let $$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$ Is $L_{300}$ decidable? My intuition is it is decidable because given $M$ and $w$, we need ...
0
votes
1answer
70 views

Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?

Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?
-1
votes
1answer
56 views

Class of given language

The language given is: $$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$ I have to find the class to which this language belongs. Now according to my intuition, ...
2
votes
2answers
74 views

Requirements for a TM to halt

I'm just beginning self-studying a course on computability and automata; my textbook, describing a generic Turing Machine, lists two following halt conditions: A TM halts, if for a particular state $...
1
vote
1answer
191 views

Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
-1
votes
1answer
150 views

How to convert a CFL to a deterministic PDA?

I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA. I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
4
votes
3answers
280 views

Oracle machine solving halting problem for other oracle machines

Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle ...
3
votes
1answer
103 views

$TSAT$ is $NP$-complete

In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete: $\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ ...
1
vote
1answer
77 views

Does Multitape reduction to a one tape machine preserve space complexity?

Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input. Is there some constant ...
15
votes
8answers
2k views

Cardinality of the set of algorithms

Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms ...
0
votes
0answers
33 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
241 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
38 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
60 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
36 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\}$

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
86 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
132 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
0answers
34 views

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption that $NP=CO-NP$? [duplicate]

Is it true that $NP^{NP}=NP$, or it is true just if there is an assumption like $NP=CO-NP$? I was proving that $NP^{NP}=NP$ by using the assumption that $NP=CO-NP$ but it seems that it might by ...
0
votes
2answers
200 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 ...