Turing Machines, Bounded, Linear Bounded, Generalized Bounded
[Linear] Bounded Turing Machines
If the tape is limited to the input, no blank symbols, no extra scratch areas,
the tm is called a bounded touring machine (btm).
If the head tries to move off either end of the tape, the btm halts in a failure state.
Sometimes it is convenient to bracket the word between start and end markers, such as ^ $.
These can be separate characters in the language alphabet,
or they can be implicit in the first and last characters of the word.
In any case, these markers prevent the btm from sliding off the end of the tape.
As we shall see, a btm is not as powerful as a tm.
A linear bounded tm makes k times as much tape available for computation.
Multiply the length of the input by k and place the right marker there.
This is equivalent to a bounded tm with an enhanced alphabet.
Use one of k tracks for each of the k segments of the tape.
The first track holds the input and the remaining tracks hold the (initially blank) scratch areas.
Thus we will rarely distinguish between a btm and a linear btm.
Generalized Bounded Turing Machines
A generalized bounded tm, or gbtm,
applies a function f to the length of the input word, and uses only that much tape.
If the machine moves beyond this point, it magically halts in a failure state.
Sometimes a gbtm will place an end marker at the right, to make sure it doesn't go past its boundary.
The function f must be computable by a tm,
without consuming more than f(|w|) spaces on the tape.
well this is just about any function you've ever heard of.
For instance, you can compute 1217,
without writing down 1217 digits.
So one can build a gbtm for just about any mathematical function f.
Recursive
The language accepted by a bounded tm is always recursive,
since another tm can simulate the bounded tm and watch for a repeated
state/tape configuration (snapshot), which indicates an infinite loop.
If a btm falls into an infinite loop, the simulator can stop and declare failure.
Otherwise the simulation continues, waiting for the btm to declare success or failure.
This theorem holds for a gbtm as well.
Since the tape has a finite length that is a function of the length of the input,
the computations are corralled,
and the simulating tm can watch for an infinite loop.
The process will halt.
Fortunately there is an easy way to watch for an infinite loop.
Run two instances of the gbtm in parallel,
and let one run twice as fast as the other.
If the gbtm falls into an infinite loop,
the state/tape configuration at step 1 million may duplicate the state/tape configuration at 1 billion.
After the first simulated gbtm has run through x steps,
and the second has run through 2x steps, their configurations will agree.
(In this case x = 999000000.)
This strategy is used in a number of real-world applications.
Since the space consumed by the simulator is (roughly) twice the space of the original machine,
a btm that is not recursive can be converted into a linear btm that is recursive.
Upgrade the alphabet, and the linear btm becomes a btm once again.
If a language is accepted by a linear btm, it is accepted by a recursive btm.
Proof of recursion can be modified to support a nondeterministic bounded turing machine (nbtm),
or a nondeterministic generalized bounded turing machine (ngbtm).
As you recall, a nondeterministic tm can
be simulated by a deterministic tm.
The simulator maintains a stack of choices, made at each step.
When the ntm's tape is bounded, the number of steps is bounded.
More steps would lead to an infinite loop.
Thus the simulator's stack is bounded.
It grows exponentially with the length of the ngbtm's tape, but it is still bounded.
Therefore a gbtm, with considerably more blank tape at its disposal, simulates the ngbtm.
Both machines accept the same language,
and since the language of a gbtm is recursive,
the language of an ngbtm is recursive.
Equivalence
To complete the circle, let a recursive tm run its course,
and it is automatically a gbtm.
(If you are given a recursive ntm, convert it to a recursive tm.)
There are finitely many words of length k,
and for each one, the tm consumes a finite amount of tape.
Run the tm for all possible words of length k and see how much tape is used.
This is f(k), and it's computable.
However, if a simulator tries to compute it, there will be some overhead.
It may well consume more than f(k) squares on its tape, as it computes f(k).
Multiply f by a constant,
to accomodate the simulator's overhead.
The result is a computable bound on the original tm,
and our recursive tm is indeed a gbtm.
A language is recursive iff it is accepted by a gbtm,
iff it is accepted by an ngbtm.
There are recursive languages that cannot be processed by a btm.
We'll prove this later.