Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
My answer was bad, so I will delete it. But I wanted to save the two enlighting comments to my answer: Goodstein's theorem is a statement of the form $\forall\exists$ (i.e. $\Pi_2$) so unfortunately it's not $\Pi_1$. – user76284 The standard combinatorial statements from the 80s can all be stated as claims that some recursive function is total. Any such statement is $\Pi_2$, and all the famous examples of this kind are properly $\Pi_2$. – Andrés E. Caicedo
+1: I changed my mind after considering Gil Kalai's comments and re-reading the accepted answer. Those nonlinear lower bounds are only known if the tapes are conceptually infinite only to the right (akin to the set $\mathbb N$) and not bi-infinite (like the set $\mathbb Z$). Somehow this provably causes overhead for moving the read/write head. For random access machines, moving the read/write head comes "for free" by definition.
Thanks for commenting years after your answer! The accepted answer cites a superlinear lower bound for multitape Turing machines. I agree that circuit lower bounds are important, but it is a different model than what was asked for.
Great! I knew about the two conjectures and also toyed around with those problems when I was introduced to knot theory (and to mathematical proof in general) by Colin Adams' book. But I learned only now about the disproof.
@jmite: First, the requested reference: R. Book, S. Even, S. Greibach and G. Ott, Ambiguity in graphs and expressions, IEEE Transactions on Computers 20(2) (1971) 149–153. To your 2nd question: yes, one-unambiguous regular expressions are those whose position automaton is deterministic; they capture only a subset of the regular languages. For instance, the languages $(a+b)^*a(a+b)^n$, for $n\ge 1$, cannot be denoted by any one-unambiguous regular expression whatsoever. See A. Brüggemann-Klein and D. Wood, One-unambiguous regular languages, Information and Computation 140(2) (1998) 229 – 253.
