The challenge itself is here:
Do you have a similar experience using other languages or paradigms? what were your subjective challenges and the benefits compared with other languages?
A lot of the code I write in Prolog is written to demonstrate you can do practical things in Prolog without it turning into C or Pascal. I feel that Lisp managed to shed the "this is only for AI" stigma, thanks to books like Practical Common Lisp and partly thanks to Emacs itself. But Prolog is still sort of thought of as this freak language only really useful for solving Einstein puzzles and sudoku.
Prolog is not my strongest language, and I am far from an expert in it. But, I don't think you have to be an expert in it to use it productively and enjoy it. If I had tried to do this problem in Haskell or Python or Java, I would probably have solved it in a completely different way.
I don't know if this addresses your questions or not, but I'm glad to talk more.
Thanks for showing your code! I just placed my minimalist DSL tools and decided to use "Halt Problem" as an example. Here is my code: https://github.com/true-grue/dsl-tools
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.
(defun run (&optional (stream *standard-input*))
(let ((pc 0)
(mem (make-array 32 :element-type 'bit :initial-element 0))
(labels ((execute (code &optional a b)
(macrolet ((mref (idx) `(sbit mem ,idx)))
(and (setf (mref a) (logand (mref a) (mref b))))
(or (setf (mref a) (logior (mref a) (mref b))))
(xor (setf (mref a) (logxor (mref a) (mref b))))
(not (setf (mref a) (if (zerop (mref a)) 1 0)))
(mov (setf (mref a) (mref b)))
(set (setf (mref a) b))
(random (setf (mref a) (random 2)))
(jmp (setf pc (1- a)))
(jz (when (zerop (mref b)) (setf pc (1- a))))
(halt (setf halted t)))))
(loop for nil = (apply #'execute (aref codes pc)) and cycles from 1
do (incf pc)
until (or halted (>= cycles 100000))
finally (if halted
(format t "Program halts! ~a instructions executed.~%" cycles)
(format t "Unable to determine if program halts.~%"))))
(coerce (loop for pc below (parse-integer (read-line stream)) collect
(read-from-string (concatenate 'string "(" (read-line stream) ")")))
The rest in the example is an actual compiler.