News for hackers. Stuff that matters.
Re:Why Lisp is a Big Hack (And Haskell is Doomed to Succeed) by jbapple on Monday January 03, 2011 @07:33AM (#2062928)
> If the Epigram is not Turing complete, then what kind of programs cannot be expressed in it?

I think one quick answer for questions like this is "an interpreter for $LANGUAGE". The reason is that, for a language in which all programs terminate, a type-checked program is a proof that the algorithm terminates. Thus, an interpreter for $SOMEPL in $LANGUAGE is a proof that there is an interpreter for $SOMEPL that terminates on all input.

If $SOMEPL is $LANGUAGE, you get a Goedel/Halting-problem problem.

This is all, of course, assuming that "interpreter" means "function taking as input a valid program and outputting some finite data containing its normalized form". If you define an interpreter to just be a function that performs one step of evaluation, you can get away with it.

There are no comments on this comment yet.