[Haskell-cafe] Theoretical question: are side effects necessary?

[Tillmann Rendel]

Hi,

Christopher Svanefalk wrote:
> Are there any problems which *cannot* be solved a side effect-free language
> (such as Haskell)?

No. Haskell is expressive enough.

One way to prove that is to implement an interpreter for a language with 
side effects in Haskell. Now if there's a program P to solve a problem 
in the language-with-side-effects, we can run that interpreter on P to 
solve the same problem in Haskell. The interpreter could use a Data.Map 
to associate variable names with values. That would probably not be the 
fastest or the most memory efficient implementation of the 
language-with-side-effects, but it would work.

The same trick of implementing one language in the other can be done for 
almost every pair of "reasonably expressive languages", so they are all 
equally expressive in a sense. It is even widely believed that no even 
more expressive language can exist. That means that if a problem can be 
solved by a computer at all, it can also be solved using any of these 
"reasonably expressive languages". That is the Church-Turing-Hypothesis.

(And the other way around: if the hypothesis is true, and a problem can 
not be solved in one of these languages, that problem cannot be solved 
with a computer at all. Unfortunately, many interesting problems are 
like that).

   Tillmann