Simulate the concatenation of two log-space programs in log-space

Question

I've got two log-space programs $F$ and $G$.

• Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
• Program $G$ will get as input $B$ as created by $F$ and create from it the output array $C[1..n]$.

I have to write a proof that there exist a log-space program $H$, which will get input Array $A$ and create from it corresponding array $C$. But I can't find the correct way to write it. How is this done?

---

A log-space program is a program which uses $O(\log n)$ bits of memory. Here are some conditions you have to keep:

1. You have to use only variables which have simple integer type (for example int in C++, longint in Pascal).

2. Allowed range of integer is defined: if $n$ is the size of the input we can save into variables only values which are polymonial sized based on $n$.

   For example: we can have variables which can takes on values in $[-n...n]$, $[-3n^5...3n^5]$ or also values $[-4...7]$, but we can't have variables which will take on values in $[ 0...2^n]$. No other types of variables are allowed, neither are arrays and iterators.

3. Exceptions from the rules about are input and output. Input will be available in special variables (mostly arrays) which your program can only read from, and the output can only be written to other special variables. So you can't read from output, and you can't increase values of input variables etc.

4. Your programs can't use recursion.

Example of log-space program written in Pascal (so everyone can understand it) which will find the largest number in the array of integer

    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

The only two variables here are j and i and they evidently take values in $[1...n]$. Therefore all conditions are fulfilled and it really is a log-space program.

Answer 1

The idea here is that we can't compute the output of the first algorithm completely because it can take more than logarithmic space (it can be polynomially large). But we don't need to if we are intelligent. What we can do is simulate the second algorithm and produce the bits it needs from the output of the first algorithm on-line. In other words, we will simulate the second machine, when it wants to read bit $i$ from its input, i.e. the bit $i$ from the output of the first machine, we stop the simulation of the second machine, simulate the first and count (but not store) the bits it outputs until it outputs the $i$th bit at which time we can stop the simulation of the first machine and continue with the simulation of the second machine as we now have the value of what it wanted to read.