# Tag Info

Accepted

### Are 2 independent PDAs equivalent to a turing machine?

No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $L = \{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\}$. I conjecture ...

### Are 2 independent PDAs equivalent to a turing machine?

What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages? The answer is no. To prove that, we can observe that, while the class of ...

### Are 2 independent PDAs equivalent to a turing machine?

The language $\{a^nb^nc^n | n \in \mathbb{N}\}$ belongs to a strict subset of context-sensitive languages that can be expressed in terms of an intersection of two context-free languages. Having two ...

### Compiler that compiles to a Turing machine?

Laconic This is the highest profile attempt I've heard of so far. It was announced on this paper by Adam Yedidia and Scott Aaronson: https://www.scottaaronson.com/busybeaver.pdf and on this blog post ...
Accepted

### Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Okay, as discussed in the comments, I will be assuming that the programming language has something like a "break" statement, which completely skips all the remaining iterations of a loop, ...

### Why there can't be two instances of a "reverse" program in the Halting problem?

The main point of the halting problem is that you are running programs on deterministic machines, that means that the execution is always the same. Given a program and an input, it either halts or it ...
1 vote

### Show that the language is undecidable

This follows immediately from Rice's theorem. However, if you don't know that theorem yet and you're asked to prove it by an explicit reduction, see oleshkowitz's answer.
1 vote

### Show that the language is undecidable

What languages are you familiar with? Are you familiar with the fact that $ALL_{TM}=\{\langle M\rangle : L(M)=\Sigma^*\}$ is not decidable? If so try a reduction from $ALL_{TM}$ where given a machine ...

Only top scored, non community-wiki answers of a minimum length are eligible