New answers tagged computation-models
1
vote
Transition System vs State Machines
From each DFA or NFA, you can obtain a labelled transition system, by ignoring which states are the initial or final states.
If you have a labelled transition system with a finite set of states and a ...

D.W.♦
- 143k
1
vote
If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?
It cannot be true simultaneously that A is undecidable, A can be reduced to B, and B is decidable. Assume there are three "proofs" for each of these three facts, then at least one of the ...
0
votes
If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?
Discovering that $B$ is decidable may mean one of two things:
There is an error somewhere: either in the proof of decidability of $B$, or in the proof of undecidability of $A$, or in the reduction ...
0
votes
Accepted
Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous
Sometimes explicit induction can be avoided by using contradiction. Assume there is a smallest pair of different derivation(trees) that derive the same string. Since the pair is different, we can also ...
Top 50 recent answers are included
Related Tags
computation-models × 490turing-machines × 143
computability × 112
complexity-theory × 60
automata × 57
turing-completeness × 46
finite-automata × 36
algorithms × 34
simulation × 25
terminology × 23
formal-languages × 21
reference-request × 19
nondeterminism × 18
lambda-calculus × 17
context-free × 16
programming-languages × 16
parallel-computing × 15
pushdown-automata × 14
quantum-computing × 14
time-complexity × 13
computer-architecture × 13
undecidability × 12
regular-languages × 10
church-turing-thesis × 10
algorithm-analysis × 9