[Solved]: Relation between space and time complexity for machines with write once read many (WORM) memory

What are the keywords to google for available material related to these questions?

The Wang B-machine is a very simple Turing machine with only WORM memory. A Turing machine with only WORM memory is commonly referred to as a “non-erasing Turing machine”.

What is known about the relation between space and time complexity for machines with WORM memory?

Let’s assume a Turing machine with $q$ internal states and a binary tape alphabet. If the machine halts after $t$ steps, having written $m$ marks on the tape and “visited” $p$ positions of tape, then $t leq (m+1) cdot pq$. The reasoning behind this bound is simple. As long as the machine doesn’t write a new mark, there are only $pq$ distinct configurations. As the machine didn’t cycle, it can have taken at most $pq$ steps between two write events, and there were only $m$ such write events.

Do we known whether the time complexity will remain the same, if a small (for example C*log(WORM memory)^n) amount of normal memory is added?

Already Wang himself showed that a non-erasing Turing machine can simulate a normal Turing machine with only a polynomial slowdown. It was shown recently that the same is also true for the Wang B-machine. Hence it’s not really interesting to investigate the change of time complexity when adding a small amount of normal memory to the machine. It would be more interesting to investigate (for different algorithms) how much the normal space complexity can be reduced by allowing for a separate non-erasable space complexity. Not sure how to apply this to pure functional programming.