Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity.

Whether the tape has two ends or is cyclic doesn't matter, for placing a special dot on cyclic tape is like a two-end tape, and running back at the end on a two-end tape makrs cyclic.

Also it can solve its own halting problem by testing the running time. The conflict program is invalid, it has no result limit.

What's more?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Linear_bounded_automaton $\endgroup$ – j_random_hacker Jan 9 '19 at 14:27
  • 3
    $\begingroup$ Could you be more precise about what the model of computation is? What do you mean by "long enough"? With any fixed length tape, you can only accept inputs up to that length (the input goes on the tape, after all), so it's just a DFA. If the tape length is some fixed function of the input, you just end up with an analogue of space-bounded complexity classes. $\endgroup$ – David Richerby Jan 9 '19 at 14:27
  • $\begingroup$ @DavidRicherby That's a series of LBA. Any finite amount of results don't matter, but only the infinity far ones with long tape do. Sticking mind on the first few is bad $\endgroup$ – l4m2 Jan 9 '19 at 14:36
  • $\begingroup$ @l4m2 No, an LBA is just the case where the fixed function is the identity function. $\endgroup$ – David Richerby Jan 9 '19 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.