title: Log-space computable function
text: # Log-space computable function
  
  In computational complexity theory, a log-space computable function is a function $f\colon \Sigma ^{\ast }\rightarrow \Sigma ^{\ast }$ that requires only $O(\log n)$ memory to be computed (this restriction does not apply to the size of the output). The computation is generally done by means of a log-space transducer.
  
  ## Log-space reductions
  
  The main use for log-space computable functions is in log-space reductions. This is a means of transforming an instance of one problem into an instance of another problem, using only logarithmic space.
  
  ## Examples of log-space computable functions
  
  * Function converting a problem of a non-deterministic Turing machine that decides a language A in log-space to ST-connectivity.
  