Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,149
questions
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
...
