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
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$ ...
user avatar
  • 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 ...
user avatar
-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.
user avatar
-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
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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} [...
user avatar
  • 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). ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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?
user avatar
  • 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.
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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/...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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)$. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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
user avatar
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 ...
user avatar
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'...
user avatar
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 ...
user avatar
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{ ...
user avatar
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&...
user avatar
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 $...
user avatar
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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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^...
user avatar
  • 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\...
user avatar

1
2 3 4 5
47