[Theory] Halting problem

[Stewart Gordon]

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.