Three Of My Favorite Open Problems
I will discuss some open problems that I have worked on forever. I think these problems should be solvable but progress is very limited. The first is essentially the halting problem for linear automata. It has been called a shame that we cannot prove it is either decidable or not. I will report on some partial results. The other two problems I will leave as a surprise, but they are both related to our P vs NP question.