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
0
votes
1answer
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}$. ...
0
votes
0answers
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 βˆ‘ ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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. ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
1answer
40 views

What strings does this language accept/reject?

F = {ww | w ∈ {0,1}^*} Which strings are accepted and why? 0011 1010 1111
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
2answers
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. ...
-1
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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}$ ...
1
vote
0answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
40 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
65 views

Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input. My related question would be the following: is it true that for every fixed $M_0$ ...
0
votes
0answers
19 views

enumerator and turning machine mapping reduction?

Let, E = enumerator M = Turing machine the language SAMEe,tm = {⟨E,M⟩ | E is an enumerator, M is a TM, and L(E) ∩ L(M) != βˆ…}. Can someone give me a hint on how to prove the complement of SAMEe,tm is ...
2
votes
1answer
198 views

Halting problem for fixed Turing machine and fixed input

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. What if we fixed both the machine and the input? I.e., is it decidable for every ...
1
vote
1answer
53 views

Proving undecidability of HALT_tm by reduction

Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
2
votes
1answer
41 views

Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use. If a language L is ...
0
votes
1answer
56 views

Are there more languages than functions?

My gut says "no", but I don't know why. For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$ ...
0
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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, ...
2
votes
4answers
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 ...
0
votes
0answers
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?
0
votes
1answer
72 views

show that this decidable set $C$ exists

I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $...
3
votes
2answers
273 views

show that in every infinite computably enumerable set, there exists an infinite decidable set

I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set. As an attempt to solve the problem, I could only think of a proof by ...
1
vote
1answer
48 views

Is $L \subset 1NL$ when $L \neq NL$? [closed]

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
0
votes
1answer
30 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
2
votes
1answer
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 ...
1
vote
1answer
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?
30
votes
8answers
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 ...
2
votes
2answers
368 views

Why doesn't the recursion theorem prove there is an undecidable finite set?

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 ...
1
vote
2answers
46 views

Is this set semi-decidable? A set of all <M> that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M

$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 ...

1
…
3 4
5
6 7
…
39