# Tag Info

### Connection between NAND gates and Turing completeness

Its because nand is another statement for distinction/contradiction --- contradictions are bad in logic because they make 'every possible statement true and its possible to build a contradiction out ...
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 ...

### 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 ...

### 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 ...

The source of the confusion is that recognizability is defined in terms of a "there exists" statement. Recognizability is "one-sided" in regards to "yes" instances and &...
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 ...
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 ...