Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,311
questions
2
votes
1
answer
53
views
Showing that a property is semantic - Rice's theorem
I want to show that the language
$$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\
\text{if M halts on input $w$, $M'$ halts on $w$ ...
- 161
-4
votes
0
answers
18
views
Conducting a Turing machine
I'm having trouble conducting a Turing machine for the language L = {a^m-1 b^n c^m+n| m,n∈N, m>= 1}
Can anyone help me with this question? I've conducted some TMs but they still work even if I ...
- 1
-2
votes
0
answers
23
views
How to use Pumping Lemma $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$?
I'm trying to use the Pumping Lemma to prove that $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$ is not a CFL.
-2
votes
0
answers
25
views
How to use Pumping Lemma for L={www|w∈{0,1}* and w starts with 0}?
I know my question might be a bit similar to How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$
However, I feel that it is different enough due to the extra requirement of starting with 0
1
vote
1
answer
66
views
Is there a Turing machine that packs a machine and its input into a single machine?
Let $U$ be the universal Turing machine. Is there a Turing machine $T$ taking two inputs such that $\forall m \forall n \exists q \; T(m; n) = q \land U(q;0)=U(m;n)$?
It seems "obvious" that ...
- 111
1
vote
1
answer
37
views
Are deterministic Turing machines as powerful as probabilistic Turing machines?
I am wondering if it is known whether probabilistic Turing machines are more powerful than deterministic ones, in the sense that they can solve problems faster on average, or can solve problems that ...
- 119
-1
votes
0
answers
28
views
Is there a non-deterministic polynomial time TM such that $L(M)\in NPC$ and $L(\bar M) \in NPC$?
When $\bar M$ is a non-deterministic polynomial time TM with final states switched: accept to reject and vice versa.
- 1
1
vote
1
answer
55
views
Turing Machines time complexity with regard to the NP and P problem
I'm studying Turing machines and I came across the following definitions:
NP is the set of problems that can be solved in polynomial time by a non-deterministic Turing machine.
and
Let t(n) be a ...
- 41
0
votes
0
answers
31
views
DJNZ command in Universal Register Machine
How do I represent DJNZ command of counting machine via commands of Universal Register Machine, those commands are CLR JNE INC and TR, via this commands i have to represent DJNZ command, any help ...
- 1
0
votes
0
answers
18
views
Is it a well-posed question to decide whether a process is deterministic, given that the machine is equipped with a TRNG?
Consider a machine equipped with two input devices: A true random number generator for a fair coin toss, and stdin. I wondered whether it's possible to decide that ...
- 221
1
vote
1
answer
47
views
What would be an easy approach for this Turing machine description?
I am tasked to design a turing machine which calculates the function:
$f(n) = 2n \iff 0 \le n \le 2$, or $4n+2 \iff n>2$
Where "n" is given in binary.
Now, I'm not in the slightest way ...
- 155
0
votes
1
answer
57
views
Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed
I came here to ask for help with a two-tape Turing machine for the following language.
$L = \{ a^{n^2} | n \ge 0 \}$
I tried following the advice on this site: Turing machine that accepts L={an2|n≥1}
[...
- 155
0
votes
0
answers
21
views
Final state to halting turing machine conversion
So i have this turing machine that accepts the lenguage $L=(a+b)^*aa(a+b)^*$. Where $*$ is the empty cell, and the string is located at the right of the initial empty cell (where the head is placed).
...
- 11
0
votes
0
answers
41
views
Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]
Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically:
P - finding all subwords from a giving word and looking if there is a connection ...
- 1
1
vote
0
answers
17
views
Solomonoff induction generates sequences of unbounded Kolmogorov complexity?
I was reading this paper, and the author (in private correspondence, though I'm sure it's also in the paper) explains that a bit string generated through Solomonoff induction will have growing (and ...
- 111
2
votes
1
answer
36
views
Turing Machine writes "a" for every input w is undecidable
I have a doubt on my solution of the following:
Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all ...
- 121
-1
votes
0
answers
23
views
I need help with constructing one tape Turing machine for certain language
I have been trying to construct a one tape Turing machine for language 𝐿={𝑎^𝑛^2|𝑛≥1} but without any success. Any advice?
0
votes
1
answer
59
views
Can a Turing machine quickly move to any position of a large string?
Note this question was originally asked on Theoretical CS Stack Exchange, but it is not a research level question so it is being closed, and I am asking here instead.
Suppose we simulated a Turing ...
- 119
0
votes
1
answer
32
views
Determining whether the problem of given a turing machine figuring out whether the language it accepts is the set of prime length inputs is R.E
I'm trying to figure out whether the following problem is R.E.?
Given a turing machine $M$ with alphabet $\Sigma$ is it the case that:
$L(M) = \{w \in \Sigma^* | |w| \space is \space prime\}$
I think ...
- 369
-1
votes
1
answer
25
views
If A is Turing-reducible to B and B is Turing recognizable then A is Turing recognizable
I believe this is true and I have given a simple proof of this:
If A is Turing-reducible to B then there exists a Turing machine with oracle for B that decides A, because B is Turing-recognizable then ...
- 121
-1
votes
1
answer
80
views
Decidability of intersection of regular and decidable languages
I'm wondering if a language (A) is a decidable language and language (B) is a regular language, is the intersection between A and B regular?
- 1
-2
votes
0
answers
37
views
Build a Turing machine that accepts $ L=\{1^{n^m}\#1^n\#1^m| n,m > 1\} $
I need to construct a Turing machine that accepts the following language:
$$L=\{1^{n^m}\#1^n\#1^m| n,m > 1\}$$
I'm having trouble with how to construct the machine.
0
votes
0
answers
100
views
Prove that neither given language nor its complement is recursively enumerable
Let $L = \{\langle M, n\rangle \mid\,\, n \geq 5000$ and $M$ is Turing machine that halts for every input and leaves at least $n$ non-blank symbols on the tape when stopping $\}$.
I believe neither ...
1
vote
1
answer
51
views
Prove the equivalence of the modified Turing Machines and the standard Turing Machines
We have a Turing Machine that cannot write the same symbol it has read in a transition, meaning it should always alter the symbol when passing it. How can we prove that such machines have equal ...
0
votes
0
answers
26
views
Prove that a Turing machine that looks to adjacent cells on left and right of a cell for decision is not weaker than normal Turing machine
We consider a Turing Machine that for a transition to apply, looks not only to the cell the head is currently on, but to its adjacent cells as well.
Basically it will need to read a string of 3 ...
1
vote
2
answers
67
views
How could Penrose's universal Turing machine with a binary alphabet work?
In his book The Emperor's New Mind, Roger Penrose gives an overview of Turing machines in Chapter 2. In his definition of what a Turing machine is he is very minimalist. There is a single linear tape ...
- 111
1
vote
1
answer
48
views
Worrying about details: high-level arguments about polynomial-time computability
I am learning complexity theory with a background in mathematics, and I want to better understand why certain reductions are polynomial-time computable.
Let me give two examples of my worries.
Example ...
- 143
1
vote
1
answer
178
views
Limited tapes-version TM for pair sum
In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/...
- 133
1
vote
1
answer
58
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 133
1
vote
1
answer
54
views
Enumerating through Turing Machines That Solve Same Problem
Is it possible to enumerate through all the Turing Machines that solve the same given problem? For example, we know that there exists a Turing Machine that finds a satisfying assignment given a 3SAT ...
- 11
0
votes
1
answer
281
views
Sets of problems in different models of computation and cardinality
In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg
Essentially, Pushdown Automata (PDA) can solve ...
- 11
1
vote
1
answer
143
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
- 133
1
vote
2
answers
57
views
Why is $A_{TM}$ not mapping reducible to $E_{TM}$?
$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$
$E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$
The standard proof for the undecidability of $E_{TM}$ is given in this ...
- 267
2
votes
1
answer
162
views
Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
- 456
1
vote
2
answers
53
views
Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?
If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata?
Bonus question: Can ...
- 11
1
vote
0
answers
27
views
Showing that $ASPACE(f (n)) = DTIME(2^{O(f (n))})$
My lecture notes for complexity says that $\mathsf{ASPACE}(f (n)) = \mathsf{DTIME}(2^{O(f (n))})$
I can prove the forward direction ($\mathsf{ASPACE}(f (n)) \subseteq \mathsf{DTIME}(2^{O(f (n))})$) by ...
- 369
0
votes
0
answers
31
views
Translate det. Turingmachine into formula
in the cook-levin theorem a nondet. Turingmachine is translated into a formula of the form:
$\phi$ = $\phi$$_{1}$ $\land$ $\phi$$_{2}$ $\land$ $\phi$$_{3}$ $\land$ $\phi$$_{4}$. I want to know what ...
- 11
0
votes
0
answers
13
views
Left and right derivation of Turing Machine
How can the result of the execution of $ \rightarrow RL$ differ from that of $\rightarrow LR$? In turing machines
2
votes
2
answers
61
views
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
Consider the following problem:
Input: A Turing Machine M and a DFA D.
Question: Is $L(D) \subseteq L(M)$?
Of course, this problem is not decidable. Because it is known that judging whether a word ...
- 23
0
votes
1
answer
20
views
Construction of a Turing Machine that accepts the language of (a^nb^nc^md^m for) m,n >= 1
i recently have been practicing constructing Turing Machines for languages. But i can't seem to figure this one out. I've seen a few videos on constructing 3 equal length strings (a^nb^nc^n) But i can'...
0
votes
0
answers
12
views
A finite language of chains is TM decidable? [duplicate]
In class we were talking about the decidability and acceptability of languages by Turing Machines but a doubt arose in my mind, "is any language containing a finite number of strings decidable by ...
1
vote
1
answer
92
views
Language of Turing machines that go through some configuration infinitely many times on empty input
I've been going through some questions on old homework. Here was a question that confused me somehow.
Question: Given a language $$L=\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ ...
- 456
0
votes
0
answers
37
views
How does a Turing machine work when the current head location is at the right end of its configuration?
Let's say we have a Turing Machine M1 and we have following two cases:
(1) Left end of tape
a,b,c are part of "tape alphabet" and u,v are some string constructed from "tape alphabet&...
0
votes
0
answers
12
views
A simple clarification on polynomiality of sequential construction of Turing Machines through plus construction
Suppose our original $NDTM$ $M_0$ has $N<2^t$ number of acceptance paths. We construct $r$ different $NDTM$s $M_1,\dots,M_r$ with each with $m_1,m_2,\dots,m_r$ acceptance paths respectively where $...
- 17
0
votes
1
answer
37
views
Build a 2-PDA for language accepted by Turing Machine
I saw this question on the internet and found many solutions actually but none of them really persuade me that much.
Question: Given language $L$ which is accepted by a Turing machine $M$, provide a 2-...
- 456
1
vote
1
answer
51
views
What are some examples of non-enumerable languages whose complement isn't either?
What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.
Update: Found ...
- 161
1
vote
1
answer
178
views
Undecidability in optimal data compression
There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course:
I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
- 143
-1
votes
2
answers
54
views
How to show that language is Turing-recognizable and Turing-decidable?
How do I being to show that if $L_{1}$ is Turing-recognizable language over $\Sigma=\{0,1\}$, then $L_{2} = \{ww^R | w ∈ L_{1} \}$ is a Turing recognizable language too.
There is another similar ...
- 1
0
votes
0
answers
21
views
Proof of a language being in the polynomial hierarchy and also proof, it is not in a certain subset
Given any $\theta^P_2$-hard problem P $\in$ $\theta^P_2$. I have to show this problem is $\Sigma^P_2$-complete, but I can not find the right idea behind the proof. My idea would be to reduce $\Sigma^...
- 11
1
vote
1
answer
50
views
Prove $REJECT\leq_mACCEPT$ and vice versa
a friend of mine sent me a question which he can't solve and I didn't succeed to solve it as well.
Question: We define two languages:
$$ACCEPT=\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\...
- 456