Imagine a stupid computing device with very limited powers…
What is the simplest computational problem you could ask it to
- not the addition of two numbers
- not sorting
- it’s telling two inputs apart – distinguishing them
This problem will be featured in Jeffrey Shallit’s invited talk entitled Separating Words With Automata.