In class we defined what it meant for a language to be decidable in space t(n). To properly define what it means for a function to be computable in space t(n), we need to use multitape Turing Machines. We treat tape 1 as a read-only input tape, tape 3 as a write-only output tape, tape 2 as a read/write work tape, and we only count the space used on tape 2 Formally, a function f is computable in space t (n) if there exists a 3-tape Turing Machine M with the following property: for every w E y, if M is started with w written on tape 1, then M halts with f(w) written on tape 3, while touching at most t(Iwl) cells on tape 2, never writing to tape 1, and never reading from tape 3 Notice that it is possible to perform non-trivial computations while using sub-linear space In fact, many important functions can be computed using only O(log n) space