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 ...
- 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 ...
- 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 ...
- 280
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 ...
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, ...
- 326
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 ...
- 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.
- 111
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 ...
- 76
Only top scored, non community-wiki answers of a minimum length are eligible