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):$
- compute $x \equiv m \pmod 3$
- if $x = 1$ return $0$
- if $x=2$ return $0$
- 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?
