Refuting Tianrong Lin's arXiv:2110.05942 "Resolution of The Linear-Bounded Automata Question"
Thomas Preu · arXiv (Cornell University) · 2021
In the preprint mentioned in the title Mr. Tianrong claims to prove $\textrm{NSPACE}[n] eq\textrm{DSPACE}[n]$, resolving a longstanding open problem in automata theory called the LBA question. He claims to achieve this by showing more generally $\textrm{NSPACE}[S(n)] eq\textrm{DSPACE}[S(n)]$ for suitable $S(n)$. We demonstrate that his proof is incomplete, even wrong, and his strategy cannot be repaired. Update to include recent developments of Mr. Tianrong's preprint.