Hillel proposed on Twitter today: “Expressiveness” is how easily we can ‘do’ things in a system. “Tractability” is how easily we can assert properties on things we ‘do’. F.ex DFAs are tractable, Turing machines are expressive. The expressiveness vs tractability tradeoff is one of the most fundamental in CS …
