Hacker News Reader

> By the way Conway proved [0] that any computer program can be rewritten in the form of these collatz like functions. So they are pretty prowerful.

I don't think that article supports that claim, but maybe I'm misunderstanding it.

View on HN

The wikipedia article doesn't do full justice perhaps though the essence is there. The reason the halting problem is equivalent to solving collatz like problems is because you can rewrite any turing machine in terms of a generalized collatz function. The Fractran wikipedia page has more info.

(the original conway article itself is also very readable: FRACTRAN: A SIMPLE UNIVERSAL PROGRAMMING LANGUAGE FOR ARITHMETIC)

Reply on news.ycombinator.com