Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "standard" to use the notion of time-constructible function instead. This question has the aim to compare these two notions.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is fully time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps. See this question for more about (fully) time-constructible functions.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is real-time countable, if

  • $f$ is monotone increasing
  • there exists a deterministic multi-tape Turing machine $M$ that on empty input, on $n$-th step outputs 1 if $\exists m: f(m)=n$ and else outputs 0.

The second condition sais that started on empty input, $M$ on each step outputs 0 or 1, depending on whether the number of the step is in the image of $f$.

It is easy to see that the function $(n-2)^2+5$ is fully time-constructible. But it is not real-time countable, since it is not monotone increasing. It is also easy to see that the function, given recursively by $f(0)=1$, $$f(n)=\left\{\begin{array}{ll} f(n-1) & \mbox{if the turing machine encoded by }n \mbox{ halts on empty input}\\ f(n-1)+1 & \mbox{else} \end{array} \right.$$ is not recursive, thus not fully time-constructible. But it is real-time countable (consider a Turing machine that on each step outputs one).

Thus, the discussed notions are in general incomparable. But the reason just given is in some sense "primitive". Thus it is interesting to consider an injective real-time countable function and a monotone fully time-constructible function (I think that the essence of both definitions remains).

It is easy to see that all injective real-time countable functions are fully time-constructible: just wait for the $n$-th one to be outputted (it will be in the $f(n)$-th step). And the question that remains is:

Q: Is every monotone fully time-constructible function real-time countable?

I think that the answer to this question would somehow shed more light on which notion is "stronger". Note that fully time-constructibility of some function $f$ tells us that we can compute fast enough whether on the $f(n)$-th step we should output 1 or 0. But in the next step we need the information about $f(n+1)$ and then for $f(n+2)$ ...



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.