New answers tagged turing-machines
-3
votes
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 ...
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
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 ...
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
0
votes
Confused about Turing Recognizability
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 &...
- 280
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
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
Top 50 recent answers are included