# Questions tagged [turing-machines]

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

1,943 questions
Filter by
Sorted by
Tagged with
42 views

### Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
40 views

### Give a formal description for a deterministic TM that accepts the language:. L = {#w#w^ R#w# | w ∈ {a, b} ∗}

I feel the following approach is suitable for the question but I dont know how to give a formal proof using the Turing machine 7-tuple, where : Q is a finite set of states X is the tape alphabet ∑ ...
140 views

### closure property on Recursively enumerable language

How to prove that recursive and recursively enumerable language is closed under reversal? Why recursively enumerable language is not closed under set difference? [But intersection of recursive and ...
125 views

### Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$L = \{ \langle M,w \rangle \mid \text{M on input w tries to move its head past the left end of the tape}\}.$$ Prove whether L is decidable or not. I tried to prove ...
75 views

### Turing machines moving left at least once

Is the following language decidable? $$L = \{ \langle M,w \rangle \mid \text{M moves its head left at least once when run on w}\}.$$ I feel like this is a decidable language. But I don't know ...
264 views

### Turing machine with “move to origin” instead of “move left”

You have a Turing machine which has its memory tape unbounded on the right side which means that there is a left most cell and the head cannot move left beyond it since the tape is finished. ...
47 views

### How can we know if a Turing machine halts, given that it writes to finite memory?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine 𝑀 writes to an arbitrary amount of memory, and false if it ...
23 views

### Show that the language L = {< M1 > | M1 is a Turing machine that accepts 0} is Turing recognizable

Show that the language L = {< M1 > | M1 is a Turing machine that accepts 0} is Turing recognizable. I was told by my professor to go about this proof by giving an informal description of a Turing ...
40 views

### What strings does this language accept/reject?

F = {ww | w ∈ {0,1}^*} Which strings are accepted and why? 0011 1010 1111
58 views

### Turing machines: can a machine write to a finite number of memory cells, but not halt?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
21 views

### Encoding huge number of tape-symbols of a turing machine in the simulation of the turing-machine using real computer

I was going through the classic text "Introduction to Automata Theory, Languages and Computation" by Hopcroft,Ullman,Motwani where I came across the simulation of a turing machine using a real ...
144 views

### Queries regarding simulation of multi-tape turing machine using single tape turing machine

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Jeffrey Ullman,John Hopcroft and Rajeev Motwani, where I came across the simulation of MULTI-TAPE ...
129 views

### Can a Turing Machine simulate every possible Turing Machine?

Related to my answer on this question, I'm not sure of a detail. Assume you have a Turing Machine which simulates all possible Turing Machines all at once (meaning it does not "page" its data, i.e. ...
54 views

### Prove that a language is decidable

I need some help to prove that the language is decidable. $K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}. It tried to make an algorithm ...
178 views

### Turing Machine - Analyze brackets

For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets. The only tape symbols ...
35 views

### Help in understanding 'reasonable' encoding of inputs

I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are ...
90 views

### Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ ...
19 views

### Is it semidecidable to test whether a Turing decidable language is empty?

I'm not sure how to go about solving this. I tried this: Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U ...
60 views

### Is it decidable for a NPDA to halt?

I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string. But are there ...
33 views

### Is it decidable to know the number of positions used by a Turing machine for a fixed input?

I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the ...
33 views

### Non Deterministic Turing Machine

Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?
322 views

### Trading States for Symbols with a Turing Machine

Show that for each string $w ∈ \{0, 1\}^∗$ there exists a stay-put Turing machine $$M_w = (Q, \{0, 1\}, \Gamma, \delta, s, q_{\mathit{accept}}, q_{\mathit{reject}})$$ with $|Q| ≤ 5$ states that ...
64 views

### How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...
7 views

### When Turing Machine looped? [duplicate]

Turing Machine stay at first cell and dont move to the left/right. Its condition!!!(Machine can only rewrite content of cell or dont do anything) Turing Machine looped when two iterations in which ...
97 views

### Prove a TM problem is NP-complete

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of \leq c steps}\}$$ This question looks weird to me ...
40 views

39 views

### Is there an abstract architecture equivalent to Von Neumann's for Lambda expressions?

In other words, was a physical implementation modelling lambda calculus (so not built on top of a Von Neumann machine) ever devised? Even if just on paper? If there was, what was it? Did we make use ...
85 views

### Time complexities of state-of-the-art SAT solvers with respect to length of the formula

I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables. If I am not mistaken, one of the reasons why most believe P does not ...
60 views

### Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$

Imagine you are designing a TM where $x$ and $y$ are binary representation( $x \ge y$). the TM should accept $1101\#1001$ and reject strings such as $110\#10001$, as well as it could reject if you ...
42 views

### Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable

I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable. I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ ...
41 views

### EVEN-CFL Decidable / Undecidable - Rice-Theorem

Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$ Question : Is EVEN-CFL ...
51 views

### Help with finding a flaw in argument simulating large Turing machines with smaller ones

I have an argument which, if it goes through, just about proves that either: Programming languages are more powerful than Turing machines The busy beaver function ($BB()$) on Turing machines is ...
111 views

### Computational complexity of counting symbols

Consider the counting function $\{x\}^* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$. I am confused about the (asymptotic) complexity of computing this function, ...
459 views

### To what extent is an x86 machine equivalent to a Turing Machine?

To what extent is the abstract model of computation specified by the x86 language Turing complete? The above question is related to this question: Is C actually Turing-complete? In theoretical ...
21 views

### Turing machine state with 2 “values”?

$Q=\left\{q_{0}, q_{1}\right\} \times\{0,1, \cup\} \times\{0,1, \cup\}$ What does this mean ? Is it just for saving values in a state?
72 views

277 views

### Does Turing machine have no shift?

In a Turing machine I read that it can go only right or to left. But in my book [elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis ] it says that Turing machine ...
32 views

### Do closure properties for languages go the other way?

For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?
10k views

### why don't we use machines with random access memory as our basic model of computation?

Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is ...
I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't ...
$A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$. Is $A$ semi-decidable? Is a ...