# Tag Info

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 ...
• 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 ...
• 25.5k
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 ...