On 09/10/2010 18:58, %u wrote:
Just to be clear about this, the halting problem is only unsolvable for Turing machines.
<snip>
No, it's unsolvable for any computational class that's at least as powerful as a Turing machine. In its most general form, the unsolvability theorem states that, given a computational class X, no algorithm in X can correctly determine whether an arbitrary algorithm in X fed arbitrary input will halt.
You can, however, consider a computational class X', a superset of X that includes a means of determining whether an arbitrary algorithm in X will halt. But no matter how powerful X' is, it will never be able to determine whether an arbitrary algorithm in X' will halt - you'll need X'' for that.
There are a few esolangs designed around this principle which, sadly, we aren't likely to see implementations of any time soon.
http://esoteric.voxelperfect.net/wiki/Brainhype http://esoteric.voxelperfect.net/wiki/Banana_Scheme Stewart.
