7
$\begingroup$

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.

          BB6JS
          (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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks; I was unfamiliar with Turing degrees. But suppose I alter a BB TM so that, on a nonempty tape, it halts without changing the input. Only on an empty tape does it execute its BB behavior. Wouldn't this TM have a low-complexity c.e. set, despite having an intricate behavior on one input? $\endgroup$
    – Joseph O'Rourke
    Commented May 5, 2016 at 0:59
  • 1
    $\begingroup$ AFAIK, any turing machine (including BB) only sees one symbol at a time, so it doesn't know whether the whole tape is empty; it only knows whether the symbol under the tape is empty (or $\Delta$ in the notation of the notes). $\endgroup$
    – Fan Zheng
    Commented May 5, 2016 at 1:19
  • 1
    $\begingroup$ What Fan says is correct, but nevertheless it is true that one can easily design programs that are trivial on some large class of inputs and complicated on others. I had interpreted your question broadly, as, What kind of hierarchies of complexity are associated with Turing machine programs, and the c.e. degrees are certainly an example of this. But computability theory and complexity theory are filled with numerous hierarchies of complexity, as mentioned also by Bjorn, and any of these would also be such a broad answer. $\endgroup$
    – Joel David Hamkins
    Commented May 5, 2016 at 1:37
  • $\begingroup$ I have a feeling that Joseph wants something like the Grzegorczyk hierarchy of primitive recursive functions. Is there a version of that for some subclass of Turing Machines? If so, you might add that to your answer. Gerhard "It Seems Not Like Busywork" Paseman, 2016.05.04. $\endgroup$
    – Gerhard Paseman
    Commented May 5, 2016 at 3:42
  • $\begingroup$ @JoelDavidHamkins I'm wondering if such a TM required by the OP exists. Suppose it behaves like a BB on the empty tape. Then there is $N$ such that the BB only touches at most $N$ places from the origin. Then what if I fed the TM with a tape that only has a nonempty symbol $N+1$ places from the origin? The TM could not see that symbol and would behave exactly as if it had been fed the empty tape, but that contradicts what the OP required. $\endgroup$
    – Fan Zheng
    Commented May 5, 2016 at 4:35
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. But suppose a TM only exhibits complex behavior on the empty tape, $n=0$. Otherwise it just halts immediately. $\endgroup$
    – Joseph O'Rourke
    Commented May 5, 2016 at 1:01
  • 1
    $\begingroup$ In that case, Joseph, do you want to say that machine is really complex, since it's really complex on the empty tape? or, do you want to say it's really simple, since it does something really simple on every possible input but one? $\endgroup$
    – Gerry Myerson
    Commented May 5, 2016 at 3:02
  • $\begingroup$ @GerryMyerson: Good question. It seems natural to me to take the max,its worst behavior. So: really complex. $\endgroup$
    – Joseph O'Rourke
    Commented May 5, 2016 at 10:25
  • $\begingroup$ @JosephO'Rourke Then the TM that looks at the symbol, and if it sees 1 moves right, and if it sees empty it halts and accepts, and if it sees 2 it halts and rejects, is arguably more complex under that metric: feed it a tape with a google-plex 1s on it and and it runs longer than the TM in the OP. I doubt that is what you want. You might want something about the max ratio between bits used to describe the tape and the number of steps the TM runs? $\endgroup$
    – Yakk
    Commented May 5, 2016 at 13:54
  • $\begingroup$ @Yakk: Yes, I think somehow a trace of execution must be involved, rather than just looking at input & output. $\endgroup$
    – Joseph O'Rourke
    Commented May 5, 2016 at 14:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .