New answers tagged

4

You're confusing a few concepts. "General-purpose computer" is a high-level, not very well defined term. It's used to refer to computer hardware that is not designed for a specific task and should be able to accommodate most of today's usual (consumer) workloads with reasonable performance and efficiency. Most commercially sold computers and ...


2

The statement is incorrect*. Consider that $$ RE = \{L(M) \mid M \text{ is a turing machine} \} $$ Thus $$\{ \langle M \rangle \mid M \text{ is a turing machine}\} \subseteq L \implies S_L =\{\ L(M) \mid \langle M \rangle \in L \} = RE$$ Therefore if I set $$L = \{ \langle M \rangle \mid M \text{ is a turing machine}\} \cup \{ \#\langle M \rangle \mid M \...


2

While @nir shahar's answer is not wrong, your question is about the complexity of TAUTOLOGY when we have no assumptions on the structure of the formula. In the special case of Conjunctive Normal Form (CNF, a AND of OR clauses), you can solve TAUTOLOGY in polynomial time, as Shahar says. However, there are other special cases for which TAUTOLOGY is co-NP-...


3

You are asking whether there is a concrete TM for which we know that its halting is equivalent to $\mathrm{P} = \mathrm{NP}$. An alternative phrasing is whether we know $\mathrm{P} = \mathrm{NP}$ to be equivalent to specific $\Sigma_1$-statement. The answer is no. We know that $\mathrm{P} = \mathrm{NP}$ is equivalent to "There exists a polynomial-time ...


1

Saying that a "language reaches the state of reject" is meaningless. Languages don't have states. Turing machines and automatons do. That said, your language is undecidable. Given $\langle M,w \rangle$ you can compute the pair $\langle M',w \rangle$ where $M'$ behaves exactly as $M$ except for the following: every transition that halts the machine ...


-1

1 The problem is somewhat more complicated in spirit to Goldbach and similar problems (FLT, ZFC): You certainly can invent a TM that solves instances of 3-SAT (in exp time) as you can check instances of Goldbach. 2 You want to know however whether there is a faster TM and which is the fastest one. Since there are faster and faster machines (eg by recoding) ...


2

From what I understand in the question, there is a language that accepts Turing machines that go into an endless loop. We do not say a language "accepts" something. Rather the language contains all pairs of turing machines and words, where the TM runs forever (which I take "infinite loop" to mean) on the word. Also, note that you can ...


5

The main "key" here is to understand how a formula is structured. Assuming the formulas of TAUTOLOGY are in CNF, then there exists a polynomial algorithm: Let $\varphi=\bigwedge_{i=1}^{k}\limits C_i$ where each $C_i$ is described as an $\lor$ of multiple literals. Notice, that in order for an assignment $\rho$ to satisfy $\varphi$, we need $\rho$ ...


1

The "key" here is to make $f$ construct a new machine $M'$ that will contain all of the primes assuming that $w\notin L(M)$, and otherwise, there will be at least one prime it rejects. Now, the reduction $f$ will work by taking $\langle M, w\rangle$ and outputting the following TM $M'$: On input $z$, run the following: Emulate $M$ on $w$ for $|z|$ ...


1

Assuming words cant overlap, we will prove that the statement is false. Lets try to think about $\Sigma^*$ and see what happens (since as you said, it could be used to create a polynomial counter for all other languages in $P$). Without loss of generality, we can assume that the polynomial counter will contain the words in increasing lexicographical ordering ...


1

The following assumes that words cannot overlap on the output tape. Let $\Sigma=\{0,1\}$, pick $\Sigma^* \in \mathsf{P}$ as your language and suppose that there is a polynomial counter $T$ for $\Sigma^*$. Let $p(|w|) = |w|^{c_1} + c_2$ with $c_1, c_2 \ge 0$ be a polynomial for such that a word $w \in L$ starts in position at most $p(|w|)$ on the output tape ...


1

Even with your restriction $D$ is undecidable. You can still reduce the halting problem of a TM $A$ on a word $x$ to $D$. Construct a TM $B$ that simulates $A$ on $x$. If $A$ halts, $B$ accepts its input. Otherwise $B$ runs forever. Clearly then $A$ halts on $x$ iff $B \not\in D$. Note that you can always construct $B$ such that $B \neq M_D$ by performing ...


6

Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two different things. Roughly speaking, computability is about what we are able to compute in a given model of computation. We believe Turing machines to be an universal ...


2

The core idea is good. You might want to elaborate more on how this process is done in detail: Let us keep in mind that an OWF is a function $F$ that can be computed in $poly(n)$ time but $F^{-1}$ cannot be computed in polynomial time. Assume that $P=NP$. Therefore, to prove that there is no OWF, we will show that no function $F$ can be a OWF. Notice that it ...


0

$f$ is a one way function if given $x, y = f(x)$ can be calculated in polynomial time in the size of $x$, but given $y$ knowing that $y = f(x)$, $x$ cannot be calculated in polynomial time in the size of $y$. $NP$ is only about yes/no questions, but if we ignore that then the problem of finding $x$ is (kind of) in $NP$, because all we need to do is guess the ...


0

For the statement which is false, you take your easiest example of a non-r.e. language (ie the complement of the Halting problem), and then show how it is expressible in the respective form. For the statement which is true, you take semidecision procedures for $L_1$, $L_2$ and built one for the relevant language. If you do this properly, then the forever-...


0

There is a very slow turing program that works on binary numbers at http://morphett.info/turing/turing.html (just go to the example programs); it could easily be adapted to unary.


0

you can simulate Standard-TM -> "TM without left option" S.T. a) put a new alphabet at the first place (leftmost) of the tape b) shift all other written into one place right for each init move we go left until we reach out new alphabet you can simulate "TM without left option" -> Standard-TM S.T. for every time you needed a left ...


1

What you are complementing is the language, not $RE$ or $co-RE$. $RE$ and $co-RE$ are families of languages. Complementing a language is not the same as complementing the family its in. For instance, if we have a family of sets: $\mathcal{F}:=\{\{1,2\},\{3,4,5\},\{1,5\}\}$, when the "world" we live in only has $5$ elements: $W:=\{1,2,3,4,5\}$, then ...


0

Given a Turing machine, and an input $x$ written on tape: language decision means that the Turing machine halts in one of its accepting states if $x \in L$, otherwise it halts in a rejecting state. language acceptance means that the Turing machine halts in one of its accepting states if $x \in L$; it may loop forever otherwise. For a deterministic Turing ...


1

You basically have the right intuition. Let's expand the definitions one more step, to see it more clearly. detrminstic decider: if $x\in L$, the decider will stop on YES (there is only a single branch for $x$) non-detrminstic decider: if $x\in L$, there exists a branch on which the decider will stop on YES (there are multiple possible branches for $x$ ...


3

Please feed this program (pseudo-code) into yours. for every integer n > 3: has_solution := false for every prime p < 2*n: if (2*n - p) is a prime: has_solution := true break from inner loop if not has_solution: halt Congratulations! You have solved the Goldbach's conjecture! A step-by-step analysis of your program when it is ...


2

The halting problem asks whether a particular Turing Machine will halt if given a particular input. If you don't consider the input, you can't claim to solve the halting problem; a given program might halt for some inputs and not for others. You can substitute the input with a static initialisation without altering the sense of this objection. It's not ...


1

To prove that the language is recognizable simply enumerate all words $w_1, w_2, \dots,$ and execute $L_1$ and $L_2$ on $w$ in dovetail fashion (perform one step of $M_1$ and $M_2$ on $w_1$; perform one step of $M_1$ and $M_2$ on $w_2$ and one additional step on $w_1$; perform one step of $M_1$ and $M_2$ on $w_3$, one more step on $w_2$, and one more step ...


0

Let $L$ be your language $L$ is context free since the following CFG generate all possible strings in $L$ S -> 1KK | KK1 | K1K | K | Ɛ K -> S0S $L$ is decidable since $L$ is context free and all context languages are also decidable $L$ isn't regular since it doesn't respect the Pumping Lemma: For a lenght $k$ we can chose the word $w = 0^{2k} 1^k \in ...


1

To fix the solution you just need to accept any 3 elements of your choice in $M_x$. Now, $M_x$ will look something like that: If $w$ (the input) is $0,1$ or $00$, accept . Otherwise, emulate $M$ on $x$. Accept if $M$ halted. Now, you are guaranteed to have exactly 3 elements in $L(M_x)$ if $M$ doesnt halt on $x$, and otherwise $L(M_x)=\Sigma^*$. You can ...


1

No, this proof is not correct. You can't iterate through all inputs $x\in \Sigma^*$ since it would take you "infinite time". The correct way to do this is to construct the complement of $D$ (as a pushdown automaton! as @Steven mentioned), which we will call $D^c$, then construct the intersection PDA $D^c\cap M$ (notice that this can be done since $...


Top 50 recent answers are included