7
Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.
Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this ...
4
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.
You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always ...
3
No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).
3
NP-completeness is a category of decision problems, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete.
There are other types of problems around. The three most common ones are optimization problems, function problems and search problems.
Optimization ...
3
Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression ...
2
Check Belare and Goldwasser, "The complexity of decision versus search", SIAM J. Of Computing, 23:1 (feb 1994), pp. 97-119. Belare has notes for a class.
2
Enumerate the c.e. set, keep only entries that appear in increasing lexocographic order. As the c.e. set is infinite, there will be new elements larger than the last kept one (thus the subset is infinite). To decide the subset, enumerate until hitting the element or a larger one.
2
A slightly weaker form of Gödel's first incompleteness theorem can be derived from the undecidability of the Halting problem with a short proof. The full incompleteness theorems also have a short proof which is similar to the one for undecidability of the Halting problem. I highly recommend the whole series (or at least the previous part) for context. The ...
1
Since $M_0$ and $w_0$ are fixed parameters of the problem, the answer is yes: for every fixed $M_0$ and $w_0$, there exists a Turing machine $M_{M_0, w_0}$ (depending on $M_0$ and $w_0$) such that, for the input $(M_0, w_0)$, $M_{M_0, w_0}$ returns $1$ if $M_0(w_0)$ halts and 0 otherwise.
In particular one such Turing machine $M_{M_0, w_0}$ must be one of ...
1
Suppose that your PDA is reading $011$.
At the beginning, the PDA is at state $q_1$, and the stack is empty. The only move the PDA can make is to put $\$$ on the stack and to transition to state $q_2$.
Since the next symbol to be read is $0$, the only move the PDA can make now is the self-loop on $q_2$ which puts $0$ on the stack. The input is now $11$, ...
1
Here is a proof sketch. We will show that the given formula is unsatisfiable iff there exists a cycle containing both $x$ and $\lnot x$, for some variable $x$.
Suppose first that there exists a cycle containing both $x$ and $\lnot x$. The existence of a path $x \to^* y$ in the implication graph means that in a satisfying assignment, if $x$ holds then so ...
1
In the answer by @LukeMathieson it is proved, that non-deterministic two-stack pushdown automaton is as powerful as Turing Machine. A stronger statement is also true:
Deterministic two-stack pushdown automaton is as powerful as Turing Machine
Proof:
Because it is known that deterministic queue automaton is equivalent to Turing machine all we need is to ...
Only top voted, non community-wiki answers of a minimum length are eligible
