5
Yes, because $\mathsf{SAT}$ is $\mathsf{NP}$-complete.
Let $L\in\mathsf{NP}^\mathsf{NP}$. This means that there exists $A\in\mathsf{NP}$ such that $L\in\mathsf{NP}^A$. But you can replace any oracle query to the set $A$ with a polynomial-time deterministic computation that uses oracle queries to $\mathsf{SAT}$. Thus, $L\in\mathsf{NP}^\mathsf{SAT}$.
4
This is an answer to an attempt at understanding a previous version of the question, and is no longer relevant to the latest question.
Your question is: What happens when you use a simulating halt decider and (...)?
The answer is: You can't. The question has a faulty premise. A simulating halt decider does not exist, so there is no meaningful answer to ...
4
We always measure the running time of a machine with respect to input size. For this reason, your language is in P. Given a sequence of moves, you can easily check in polynomial time that the sequence is valid.
You can construct a language in $R \setminus \mathit{NP}$ using diagonalization. This is the content of the nondeterministic time hierarchy theorem.
3
The reduction is sketched on Wikipedia.
3
There is indeed an extension of regular expressions that accepts the language of two-stack push-down automata, which has the same expressive power as Turing machines.
First off, to make the algebra more obvious, I'm going to define the operators using Kleene algebra notation.
$0$ is the empty set and $1$ is the zero-length string. Juxtaposition, or $\cdot$, ...
3
Appearance checking is a concept in the theory of regulated grammars.
In an ordinary (context-free) grammar we may appay a production to a string if its right-hand side occurs in that string.
So for $\pi: A\to \alpha$ we write $x \Rightarrow_\pi y$ if $x= w_1 A w_2$ and $y = w_1\alpha w_2$.
In a regulated grammar we may specify the order in which the ...
2
In response to an earlier version:
You have misunderstood their proof, which is not very well presented (imho); but you also seem to have cut off the end, where they establish the contradiction.
They do not state anywhere that $M$ is simulated, at all.
$\hat H$ simulates $H'$ and $H'$ simulates $H$. Now, $H$ is assumed -- towards a contradiction -- to be ...
2
Any language that is accepted by a FSA can be accepted by a regular expression, and vice versa.
Any language that is accepted by a Turing machine can be accepted by an unrestricted grammar, and vice versa.
See the Chomsky hierarchy.
If you literally mean that you just want a string that describes a Turing machine, it is easy to obtain one: convert the ...
1
The difference here comes from the requirement to halt.
An algorithm that returns "true", must always do so in finite time, hence, it will never be able to go through all strings in $\Sigma^*$ and confirm that it is either generated not by both CFGs.
However, for the complement problem, the requirement changes drastically: It is enough to show one ...
1
I finally understood what was blocking me.
We only need a TM that recognizes an undecidable language so we just have to take a TM $M'$ that recognizes $A_{TM}$ for example and return it when $M$ accepts $w$.
We have $L(M') = A_{TM}$ which is undecidable.
1
Maybe try to use Rice' theorem, instead of reducing from $\overline{A_{TM}}$.
Only top voted, non community-wiki answers of a minimum length are eligible
