automata - Find a linear bounded automaton that accepts the language L = { a^{n!} : n >= 0 }

Question

I need to construct linear bounded automaton for the language L = { a^{n!} : n >= 0 }. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a. I might want to hear a few suggestions, as I am experiencing difficulty in developing the specific LBA for it.

Answer 1

A linear bounded automaton is a multi-tape non-deterministic Turing machine whose tape length is bounded by some fixed linear function of the input length. That is, the amount of tape available to work with must be known in advance from the length of the input and that length must grow linearly with input size. If we can determine a Turing machine for this language and show we know exactly how much tape will be used as a function of the input length, and that function is linear. we have shown the TM to be an LBA.

Consider the following multi-tape non-deterministic Turing machine for checking whether the input it a^(n!):

1. if the input tape is empty, halt-reject
2. write a on the second tape
3. scan the input tape and if there is only one instance of a remaining, halt-accept
4. otherwise, go back to the beginning of input
5. then, cross off (n-1) instances of a in the input for every n instances you find. to do this, move the second tape head right to count up to n-1, and when you reach the blank after the last a on the second tape, leave the a you are at on the input tape alone, reset the second tape head, and continue the process
6. if you end up running out of instances of a on the input tape while attempting to cross off all but every n'th one during step 5, halt-reject, since the input tape was greater than (n-1)! but was not evenly divisible by n.
7. otherwise, if you run out of instances of a at the same time you complete a full counting of the second tape, reset both tape heads, write another a to the end of the second tape, and continue the process from step 3.

Here's an example of how this TM functions:

Input:  #aaaaaa#    #aaaaaa#    #xaaaaa#    #xaaaaa#
         ^       =>  ^       =>   ^      =>    ^
Second: ########    #a######    #a######    #a######
         ^           ^            ^          ^
       
        #xaxaaa#    #xaxaaa#    #xaxaxa#    #xaxaxa#
   =>       ^    =>      ^   =>       ^  =>   ^
        #a######    #a######    #a######    #aa#####
          ^          ^            ^          ^

        #xxxaxa#    #xxxxxa#
   =>       ^    =>       ^  => halt-accept since we are at the end
        #aa#####    #aa#####    of the tape and looking at a blank
          ^            ^        on the second tape and only one a
                                remains

A simple analysis of the way this TM works shows that the number of additional tape cells used cannot be more than the number of tape cells used by the input. Because we only use additional tape cells for writing down the current divisor, and all divisors of sufficiently large values of n! are smaller than n!, the total number of tape cells in play (including input) is certainly less than 2*|input|. But 2*|input| is a linear function of the input size |input|, so this TM is also a LBA.