Thank you very much! I decided to place my DSL tools (they contain a tiny amount of code, but I've used them successfully in a number of compiler projects) on github and just started looking for some illustrative examples. And your solution for Halt Problem (never heard about this problem before -- I mean this reddit challenge, of course, not Rice's theorem) appeared just in a right time. Thank you! :)

As a side note. It would be interesting to investigate power of a Prolog-like language which has terms, term variables, pattern matching (maybe even without full unification) and only local backtracking. Plus an ability to make user-defined execution strategies (tree traversals etc) in the form of combinators. I already use most of these constucts in dsl_match module and I got my inspiration mostly from Stratego/XT. Still it would be good to see similiar general-purpose language and compare its expressiveness with Prolog.