So we know that LBAs have a finite number of configurations, which makes the task of detecting loops much easier. My proposition is that if a given LBA is constructed to recognize a language, it also decides it since if there was a non-halting instance of the problem, we can detect it and terminate the computation. Is this correct? If not then what am I missing?

  • $\begingroup$ Note that the property of having a finite number of configurations is shared by TMs with bounded space complexity. When you say we can detect the loop, do you mean we looking at the LBA our that the LBA itself can detect its own loop? $\endgroup$ Sep 21, 2023 at 14:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.