Complexity of Turing Machine behavior If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}write, head{-}movement, state > \;.
$$
Some of the $q$-state TMs are, however, rather
more complex than others:
the Busy Beaver (BB) TMs.
These TMs exectute an immense number of steps on an empty
tape before halting.
For example, there is a $6$-state BB that takes
more than $10^{36534}$ steps before halting.

          


          

(Image from 
Jeffrey Shallit's notes (PDF).)


My question is:


Is there some measure that captures the complexity/intricacy of
  a TM's behavior?

One can replace TM by "computer program" here.
I am looking for something beyond the complexity of the 
description of the program, and which instead captures its possibly
complex behavior on certain inputs.
It seems the Kolmogorov complexity would treat a $q$-state
BB as equally complex to a mundane $q$-state TM.
One possibility would be to run the TM on all inputs up to
some length beyond which the TM could not distinguish,
and form a measure from the number of steps before halting.
(Or perhaps: also before looping?)
Have such measures been considered in the literature?
 A: Here is one proposal. 
A set of natural numbers is computably enumerable if it can be enumerated by a Turing machine program, that is, if the set is the range of a Turing computable function. Two such sets are said to be Turing equivalent, if each of them can be computed from an oracle relative to the other, and the resulting collection of c.e. Turing degrees is an extremely rich and intensely studied hierarchy. 
Since every Turing machine program can be viewed as enumerating some c.e. set, we can naturally classify the complexity of the programs by the complexity of these c.e. sets that they enumerate, as points in the Turing degrees. 
It was the famous Post's problem that asked whether indeed there were any c.e. degrees other than the decidable sets and the halting problem, but it was found that there is indeed a very rich hierarchy of intermediate c.e. degrees.
A: If you restrict attention to TMs that always halt, then:
One measure of complexity of a Turing machine is its running time, the maximum number of steps taken before it halts on inputs of length $n$, as a function of $n$. If this is $O(n^c)$, i.e., bounded by a polynomial, then we get the notion of polynomial time, and so forth.
That's time complexity. Then there's also space complexity, the maximum number of tape cells inspected during computation.
