7 votes
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 ...
Kai's user avatar
  • 614
6 votes

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 ...
bebidek's user avatar
  • 161
3 votes

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 ...
Ṃųỻịgǻňạcểơửṩ's user avatar
3 votes

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 ...
Ciro Santilli OurBigBook.com's user avatar
2 votes
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, ...
Сергей Макеев's user avatar
2 votes

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 ...
Nathaniel's user avatar
  • 12.3k
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.
Jean Abou Samra's user avatar
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 ...
oleshkowitz's user avatar

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