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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
