Questions tagged [turing-machines]

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

1
vote
1answer
94 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
1answer
50 views

Number of divisors of a number - in NP?

I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP. The input (m,n) is in binary. The non-deterministic Turing machine for the language would be: 1) Guess the prime ...
1
vote
0answers
19 views

What is the difference between the input set of a BSS RAM and a language?

I'm currently learning some things about BSS RAMs. For sake of simplicity, please imagine them as a Turing machine over the reals. Now, this machine gets some real numbers as input. The input values ...
2
votes
2answers
46 views

Quotient in LOOP program [closed]

I want to construct a LOOP-computable program for the integer division (quotient): x = a DIV b The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language) I ...
0
votes
2answers
52 views

Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
0
votes
1answer
59 views

Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
0
votes
0answers
42 views

Turing machine, tape without blanks, does it halt or no?

So I'm lost on this one. We're given a turing machine and an initial tape. Tape is infinitely long in both ways, but all the blanks are taken out. The head is the leftmost nonblank. So the question is:...
0
votes
1answer
62 views

What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?

I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
2
votes
1answer
152 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 ...
0
votes
1answer
42 views

Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
0
votes
1answer
55 views

Whether language of all turing machines is decidable or undecidable or semi-decidable?

I recently came across this language: $L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$ It was asked in the question to find out whether language L is decidable or undecidable. ...
0
votes
0answers
33 views

What is the power of a Turing-machine that cannot write?

What is the power of a Turing-machine that cannot write? So it can still read and go back and forth on the tape, but it cannot write. I am wondering what this would be equivalent to in the ...
0
votes
1answer
54 views

Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

I am looking for an unrestricted grammar which generates the following language: $\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$ That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
1
vote
1answer
90 views

Trying to prove semidecidability of an undecidable language

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
1
vote
1answer
78 views

Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...
0
votes
1answer
64 views

Can a Turing Machine tell if an input string is a description of itself?

Can some Turing Machine $M$ with description $\langle M\rangle$, check if an input string $w$ is a description of itself? That is, can $M$ be constructed such that $M$ can tell if $w$ = $\langle M\...
1
vote
0answers
50 views

Power of Turing machines that are not allowed to overwrite the input string [duplicate]

The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start ...
0
votes
3answers
158 views

Is a Turing machine too strong of a model to model physical computation?

I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
1answer
211 views

Regarding time complexity of multi-tape Turing machines

So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM? I just don't know where to get started...
1
vote
1answer
21 views

How to think when devising a TM that decides if a DFA rejects some string?

The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ ...
1
vote
2answers
123 views

Turing machine to output enumeration of a language

I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$. So for example it should output the following to the first tape: ...
2
votes
1answer
67 views

Decidability of Turing Machine accepting exactly 14 words

Would you say that the following problem is undecidable? $$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$ My intuition says that this must be undecidable, and I want to try to reduce ...
0
votes
1answer
264 views

Is the language of all TMs accepting all strings starting with 010 decidable?

I am trying to figure out if this language is decidable: $$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$ My intuition is that it is. Whatever string $w$ starts ...
0
votes
1answer
259 views

A,B decidable: proof that A\B is decidable too

For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too. My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is ...
1
vote
1answer
128 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
139 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
89 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
145 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
109 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
65 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
118 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
166 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
75 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
448 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
311 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
161 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
99 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
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 ...
-1
votes
1answer
48 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
163 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
813 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
61 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
43 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
106 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 ...