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
43 views

What is the sequence that is computed by a Turing machine?

so I was wondering how to know the sequence a Turing machine T computes? We are reading The Annotated Turing by Charles Petzold at the moment which includes Turing's original paper "On Computable ...
1
vote
1answer
16 views

One-tape Turing machine for doubling words (strings)

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape ...
2
votes
1answer
48 views

Turing machines which halt after updating a cell for the second or third time

We say that a Turing machine is fragile, if it halts after changing the symbol of one of the tape cells for the third time. Is it true that every language that is solvable on a Turing machine will be ...
-1
votes
0answers
43 views

single-tape Turing machine

I am reading an introductory text on Turing machines( https://en.wikipedia.org/wiki/Turing_machine) and I have some questions. The first one is the following: Prove that there is a single-tape Turing ...
0
votes
0answers
29 views

Removal of null/epsilon productions

My question. Why there is a need of removing null/epsilon productions from the grammar?
1
vote
1answer
33 views

Language classification

I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R. The ...
0
votes
1answer
35 views

How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
4
votes
0answers
52 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
3
votes
1answer
32 views

Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
0
votes
1answer
16 views

Computation branches on NTM

I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string. $\text{Start: }(q_0) 011101 $ ...
0
votes
0answers
25 views

Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...
0
votes
2answers
30 views

Where is the error in this logic for halting Turing machines?

Let $\mathbb{H}$ be the set of all Turing machines that halt on all inputs. Consider the following Turing machine $T$. On input $\langle S \rangle$ where $S \in \mathbb{H}$ (note that the angle ...
-1
votes
2answers
53 views

How do we say there is A Turing machine when it does not halt

Generally we will say there is A DFA for a language if we give a string to that DFA and after processing it it will reach to DFA and DFA more or less stops at final state,so then we say there is a ...
1
vote
1answer
59 views

Why are Recursive Enumerable Languages closed under union?

Union of two REL is closed under union. I don't understand how is it closed. I followed this link. The have stated: Here the trick is to simulate both M1 and M2 “simultaneously”. In other words, we ...
2
votes
2answers
86 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
0
votes
1answer
68 views

Halts for all rejects, but might accept/loop otherwise?

If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified? Recognizability Decidability ${\langle L\rangle}$ ${\langle \overline{L}\rangle}$...
13
votes
5answers
5k views

How can a Turing machine compare two strings without modifying them?

In Sipser's Introduction to the Theory of Computation, the author explains that two strings can be compared by “zigzagging” back and forth between them and “crossing off” one symbol at a time (i.e., ...
0
votes
0answers
24 views

Polynomial time function vs polynomial time algorithm

In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as: Definition 1: A functional propositional proof system is any polynomial time ...
1
vote
2answers
101 views

Converting non-deterministic TM to deterministic TM using poly time SAT solver

Suppose there exist deterministic turing machine $M$ that could solve SAT in polynomial time. How can we construct a deterministic TM $N$ ,by using SAT solver $M$, that take as input a non-...
3
votes
1answer
56 views

Showing NP is closed under intersection

I was solving the following question: Show that $L_1 \cap L_2 \in \mathrm{NP}$ for $L_1,L_2 \in \mathrm{NP}$. I came a cross this solution on the internet which is: $M$: On input $w$ — Run $M_1$ ...
0
votes
2answers
70 views

is Turing machine the blue print for program (software) or computer (hardware)?

I often hear Turing machine is a mathematical model of computation. Sometimes, it's said to embody any computer program. Sometimes, it's said to be an idealised computing device consisting of a read/...
-1
votes
1answer
28 views

High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
0
votes
1answer
69 views

What does it mean for a computer to be general-purpose?

There is a lot of Turing machine out there. Most of them are purpose-specific. What make universal Turing machine universal? How do we know or prove if a computer is universal? Edited: Is ...
1
vote
1answer
34 views

Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain

Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any $L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why. I think the claim is incorrect, and I'm trying ...
0
votes
1answer
32 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...
4
votes
2answers
125 views

tautology vs satisfiability

I had a test that I failed to pass, and it had a question that I failed to do. This is the question: Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
2
votes
1answer
67 views

Complexity of the language that enters an infinite loop

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. This is the question Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | ...
0
votes
1answer
29 views

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$ I am trying to prove that $L$ is not in $RE$ by reduction ...
0
votes
0answers
17 views

Understand what this phrase is in the Turing

I had a test a few days ago and failed it. There was a question that was not clear to me. This is the question: For the purpose of describing the drawing on the tape of a Turing machine at each step ...
1
vote
1answer
26 views

M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M] $, there would be two ...
2
votes
0answers
54 views

A synctactic property of the complexity class P

In these lecture notes the authors mentions that P is a syntactic complexity class, as we can find a decidable set of encodings for all polynomial time Turing machines. Of course, given a ...
-1
votes
1answer
84 views

how can turing machines be universal models of computation if they can't perform binary search?

I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it ...
1
vote
2answers
78 views

P = NP ==> there exists no OWF: proof using NTM and binary tree

I read a proof in my script: If $P = NP\implies $ there exists no OWF $f$. A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$ Their proof was a bit messy so I want to ask if ...
1
vote
2answers
72 views

"Polynomial Counter" Turing Machine

I need some help with this question: Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ ...
0
votes
1answer
30 views

Prove/disprove that if $L_1, L_2\in RE$ then $L_1-\ L_2, L_1 - \bar{L_2}\in RE$

I need to prove\disprove that if $L_1, L_2\in RE$ then $L_1-\ L_2, L_1 - \bar{L_2}\in RE$. Trying to prove those statements I thought about using the turing machines $M_1, M_2$ of $L_1, L_2$ ...
1
vote
1answer
89 views

Turing machine for language $\{a^p | p~\text{is a prime number}\}$

I am trying to find a Turing Machine for the above language. I am trying to do it with one tape, to start with. However, I am not quite sure about how to keep track of the number of a's in the string. ...
2
votes
0answers
28 views

What was the original paper that showed a simulation of turing machines via circuits?

It is a very standard construction in most complexity theory courses to turn a turing machine into a circuit. I thought this was due to Cook, but it looks like he did the reduction to SAT not through ...
0
votes
1answer
16 views

Complementary language of $L\notin RE,coRE$

I mean if $L'$ defined as $L'=\overline{L}$, when $L\notin RE,coRE$. From the logic point of view it should be $L'\in RE \cup coRE$, isn't? But it's not make sense for me, where am I wrong?
-3
votes
2answers
104 views

Is this solution for the Turing's "halting" problem correct?

I think that Alan Turing's solution for the "halting" problem might be wrong. Turing's main premise is wrong, he assumed the only way to check whether a program halts is to run it. He didn't ...
2
votes
2answers
41 views

Confused about definition of a non-deterministic decider

Fallowing are some definitions from book "introduction to theory of computation" by sipser. a nondeterministic turing machine is a decider if all its computation branches halt on all input. ...
0
votes
1answer
27 views

Prove undecidable and recognizable

Is there a way that I can use If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$? to prove that $L=\big\{...
0
votes
1answer
27 views

Does TM $M$ exist, when $L_{\leq3} \subset L(M) \subset L_{\leq4}$

and $L_{\leq k} = \{\langle M \rangle : |L(M)|\leq k\}$ The solution that I saw is: Proof by contradiction, assume such $M$ exists. So reduction $f$ from $\overline{HP}$ to $L(M)$, when $\overline{HP}=...
0
votes
1answer
28 views

Prove decidable

L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s } T = "On input where M is encoded DFA" ...
0
votes
1answer
32 views

Convert a PDA with transition for a state to itself to another PDA

Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this? EDIT (My thoughts): I guess we can ...
0
votes
1answer
49 views

Recursive languages

I need to prove if the following languages are recursive: $A_1 \subseteq \{0, . . . , 9\}^∗ $ consists of all finite sequences of $\pi$ without the decimal point. We may thus write $A_1 = \{3,31,314,...
0
votes
1answer
22 views

Turing machine halts on input $a^m$ with $a^{m^2}$ written on tape

I am learning Turing machine in automata. Following problem might be simple, as that's the first question on Turing machines in my textbook, however I am not sure if I am doing it efficiently. Give ...
0
votes
0answers
18 views

Turing Machine to compute a function for binary alphabet

I am trying to formulate a TM to compute the function $f(x)=2x$, for $\Sigma=\{0, 1\}$. That is, the formulation should be for binary strings. The idea that I can think of is that the binary string ...
1
vote
1answer
21 views

NP problem: certificate concept clarification

When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c&...
0
votes
1answer
36 views

Multitape Turing Machine to shorten one's name

I am trying to formulate a multi-tape Turing Machine which converts one's name in the form of "(Firstname with the first letter in caps)(space)(Lastname with the first letter in caps)" to &...
-1
votes
2answers
31 views

algorithm that determines if a given number n is composite or not on input <n>

Consider the following algorithm that determines if a given number n is composite or not ...

1
2 3 4 5
43