# Logarithmic space and time computable function for sequences over $\{0,1\}$

Given $$\sigma_1 \dots \sigma_n$$ a sequence or word of length $$n$$ over $$\{0,1\}$$ I was wondering if there is a computable function to calculate $$\sigma_m$$ in $$\log(P(n))$$ time where $$P(n)$$ is some polynomial of degree $$Q(n)$$ for some other polynomial $$Q$$ and with $$\log(P(n))$$ space with regard to some global endocing using a fixed number of symbols $$s_1, \dots , s_r$$.

I could find such a function that runs in polynomial time and uses polynomial space:

Given $$\sigma_1 \dots \sigma_n$$ Assuming $$0^0 = 1$$, let $$i=i_1, \dots , i_k$$ the indices for which $$\sigma_i = 1$$.

Then define $$f$$ as:

$$f(m) = 0^{(m-i_1) \dots (m-i_k)} = \sigma_m$$ for all $$m=1, \dots, n$$ (power here is mathematical power and not the number of repetitions function)

So $$f$$ is basically evaluating a polynomial of degree at most $$n$$, so it runs in polynomial time with regard to $$n$$ and clearly takes $$O(n)$$ and hence polynomial space.

Can there be a computable logarithmic time and space (logarithmic space to hold $$f$$ i.e. $$|\langle f \rangle | = O(\log n)$$) function with regard to $$n$$?

We can also simply take $$f= \{(1, \sigma_1), \dots (n, \sigma_n)\}$$. then $$f$$ runs in $$\Omega(n)$$ and takes $$\Omega(n)$$ space.

Some sequences can clearly have such $$f$$. E.g. take the sequence $$\sigma_1 \dots \sigma_n = 0 \dots 0$$ then $$f \equiv 0$$ is constant space to encode and constant time to compute.

Another simple example take the sequence $$001001 \dots 001$$ and define $$f$$ as:

$$f(m):$$

1. compute $$x \equiv m \pmod 3$$
2. if $$x = 1$$ return $$0$$
3. if $$x=2$$ return $$0$$
4. return $$1$$

This is also constant space representation for $$f$$ and constant time to compute.

But if for example we take the sequence to be the first $$n$$ digits of an irrational number in binary, can there be such $$f$$? and in general?

• You are looking for a way to calculate $\sigma_m$ in time and spacing depending on $n$. What is the relation between $m$ and $n$, if any? Aug 6, 2021 at 22:18
• It seems that $f(m) = 0$ for all $m > n$. The constant zero function is easy to compute. Aug 6, 2021 at 22:19
• What is the input, and what is the required output? Your post doesn't make that clear. Aug 6, 2021 at 22:19
• $m \in \{1, \dots, n\}$, the input is a word $\sigma_1 \dots \sigma_n$ over $\{0,1\}$ and the output is a computable function $f: \{1, \dots, n\} \to \{0,1\}$ that takes logarithmic time with regard to $n$ to calculate $\sigma_m$, for arbitrary $m \in \{1, \dots, n \}$ Aug 6, 2021 at 23:28
• If $f$ only accepts finitely many inputs, it is computable in constant space. Aug 7, 2021 at 3:07