5
$\begingroup$

Given the space A of all programs that could be possibly written in a given language and given the space B of all programs that could be possibly written in the same language but without any mutable state: can we be sure that with just B we can solve all the same problems we could solve with A ?

$\endgroup$
  • $\begingroup$ So you would move that "mutable state" as (non mutable) input parameters to programs in B? $\endgroup$ – CFrei Jun 28 '17 at 7:28
5
$\begingroup$

There is no general notion of "mutable state" for a generic language. I believe we need to restrict this question to some specific language.

For instance, consider a basic imperative language with arithmetic expressions ($*,+,-$), read input, write output, assignment, composition, conditional ($e=0$ guards), and while loop. No user-defined functions, hence no recursion. Unbounded-precision integer variables. Forbidding mutability would greatly affect the computational power. Unrestricted, it is Turing powerful, but after restriction becomes a very weak language which is able (I believe) to compute only piecewise polynomials / divergence.

If the language is instead a higher order functional language with recursion and assignment (e.g. Scheme), forbidding mutability will not affect its computational power: it was and remains Turing powerful. Mutable state can still be simulated without mutability. A way to do it is to encode state-mutating functions $f$ as pure functions $f({\sf input},{\sf old\_ state})=({\sf output},{\sf new\_state})$ (see the so-called "state monad" in functional programming).

Further, Turing & Church proved that the (pure) $\lambda$-calculus has the same power of the Turing machine. So this is a pretty established result! It is one of the very first discoveries that started computer science in the 30s.

$\endgroup$
  • $\begingroup$ In your example if you restrict the state to be mutable then the while loop may as well be a if. However if you allow Phi nodes then you suddenly have a SSA language. Though I don't know if that's cheating. $\endgroup$ – ratchet freak Jun 28 '17 at 12:02
  • $\begingroup$ @ratchetfreak Yes, it is an if, but it also allows to express non termination. Not that useful, but something that you can't achieve with if alone. $\endgroup$ – chi Jun 28 '17 at 13:00
3
$\begingroup$

Yes, there is such a transformation.

Consider a programming language which has a number of commands $c_1, \ldots, c_n$ that manipulate state. When we run a program, it starts in some initial state $s_0$. As commands are executed, they change the state so that it goes through a series of configurations $s_0, \ldots, s_k$ (the series may be infinite if the program runs forever).

Instead of there being one global state $s$ which changes with time, we will instead make sure that every command and every function takes in the current state and outputs the new state. We will then "pass along" the "current state" throughout the program in a systematic way. For instance, if there is a command $\mathtt{INCR}(\ell)$ which increases the counter at memory position $\ell$, we will change it to a stateless function $\mathtt{INCR}' : \mathtt{State} \times \mathtt{Location} \to \mathtt{State}$ which takes the "current state" and a location, and returns the new state. In general, any construct $c$ which takes as input $A$ and outputs $B$ will be transformed to a construct $c'$ which takes as input $\mathtt{State} \times A$ and outputs $\mathtt{State} \times B$.

This sort of transformation can be performed systmatically so that in the end we obtain a stateless program which takes as input the initial state and outputs the final state (as well as whatever output it was going to give). I did not explain all the details, but they are there and are well known. Various complications, such as local state, can be dealt with. A good exercise is this: take a language with a fixed number of stateful variables, say a, b, c, and think about transformations that replace the variables with state, say a triple (a,b,c), which is passed along (if there are any while loops they will have to be replaced with recursive functions).

In fact, this is how state is implemented in purely functional languages. Haskell has the state monad, for instance, which does precisely what I described above.

$\endgroup$
3
$\begingroup$

You need to define what "mutable state" means. In one interpretation space A is all Turing machines and space B is all the read-only Turing machines. Read-only Turing machines are only as powerful as DFAs.

If you allow one-time writing to new tape in space B then by copying the string over to new tape and making certain substitutions to the string, you can create a String Rewriting System which is Turing complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.