2 deleted 8 characters in body edited Oct 3 '12 at 23:49 Vor 10.4k11 gold badge2424 silver badges5454 bronze badges Just an extended (informal) comment. As explained in Yuval's answer the halting problem is not computable. But even if you were able to connect a Turing machine to a black-box (oracle) that solves it (i.e. the Turing machine sends a program $$M$$ and an input $$x$$ to the black-box and receives an answer whether $$m$$ halts on $$x$$ or not), you'll soon be in trouble again because the device TM+HALT black-box - a "hypercomputer" - cannot solve the "hyper-halting problem" for devices of its kind: i.e. given an hypercomputer program $$H$$ and an input $$x$$, an hypercomputer cannot decide if $$H$$ "hyper-halts"halts on $$x$$. You can continue adding more black-boxes but the halting-problem will always be with you :-) (see Wikipedia for references about the Arithmetic Hierarchy) Just an extended (informal) comment. As explained in Yuval's answer the halting problem is not computable. But even if you were able to connect a Turing machine to a black-box (oracle) that solves it (i.e. the Turing machine sends a program $$M$$ and an input $$x$$ to the black-box and receives an answer whether $$m$$ halts on $$x$$ or not), you'll soon be in trouble again because the device TM+HALT black-box - a "hypercomputer" - cannot solve the "hyper-halting problem" for devices of its kind: i.e. given an hypercomputer program $$H$$ and an input $$x$$, an hypercomputer cannot decide if $$H$$ "hyper-halts" on $$x$$. You can continue adding more black-boxes but the halting-problem will always be with you :-) (see Wikipedia for references about the Arithmetic Hierarchy) Just an extended (informal) comment. As explained in Yuval's answer the halting problem is not computable. But even if you were able to connect a Turing machine to a black-box (oracle) that solves it (i.e. the Turing machine sends a program $$M$$ and an input $$x$$ to the black-box and receives an answer whether $$m$$ halts on $$x$$ or not), you'll soon be in trouble again because the device TM+HALT black-box - a "hypercomputer" - cannot solve the "hyper-halting problem" for devices of its kind: i.e. given an hypercomputer program $$H$$ and an input $$x$$, an hypercomputer cannot decide if $$H$$ halts on $$x$$. You can continue adding more black-boxes but the halting-problem will always be with you :-) (see Wikipedia for references about the Arithmetic Hierarchy) 1 answered Oct 3 '12 at 23:40 Vor 10.4k11 gold badge2424 silver badges5454 bronze badges Just an extended (informal) comment. As explained in Yuval's answer the halting problem is not computable. But even if you were able to connect a Turing machine to a black-box (oracle) that solves it (i.e. the Turing machine sends a program $$M$$ and an input $$x$$ to the black-box and receives an answer whether $$m$$ halts on $$x$$ or not), you'll soon be in trouble again because the device TM+HALT black-box - a "hypercomputer" - cannot solve the "hyper-halting problem" for devices of its kind: i.e. given an hypercomputer program $$H$$ and an input $$x$$, an hypercomputer cannot decide if $$H$$ "hyper-halts" on $$x$$. You can continue adding more black-boxes but the halting-problem will always be with you :-) (see Wikipedia for references about the Arithmetic Hierarchy)