Actually, the halting problem has been proven impossible, for if third order logic can be used to determine if/when a turing machine halts, a turing machine could run that on itself, but would take necessarily more than N steps to determine that it halts (where N is the number of steps it halts in), which contradicts. Third-order logic may be able to do the inconceivable, but not the noncomputable.
That’s not the standard proof, at least not the one I know: You haven’t proven that it would necessarily take more than N steps. The way it goes is that you assume there is a machine that halts iff the machine you give it runs forever given itself as input; now if you run it on itself, if it halts, it is wrong, and if it doesn’t halt, it is also wrong, meaning our assumption was wrong.
Turing machines can’t use third order logic. That might be a limitation of the programmer, or it might be a limitation of deterministic machines. A Turing machine can’t ever compute anything about it’s own output; third order logic might allow deterministic machines which can compute the results of their own output.
I suspect that there is a halting problem where the halting status of machines which only use second order logic cannot be computed in third order logic, just like limits cannot be computed in Peano arithmetic.
Actually, the halting problem has been proven impossible, for if third order logic can be used to determine if/when a turing machine halts, a turing machine could run that on itself, but would take necessarily more than N steps to determine that it halts (where N is the number of steps it halts in), which contradicts. Third-order logic may be able to do the inconceivable, but not the noncomputable.
That’s not the standard proof, at least not the one I know: You haven’t proven that it would necessarily take more than N steps. The way it goes is that you assume there is a machine that halts iff the machine you give it runs forever given itself as input; now if you run it on itself, if it halts, it is wrong, and if it doesn’t halt, it is also wrong, meaning our assumption was wrong.
Turing machines can’t use third order logic. That might be a limitation of the programmer, or it might be a limitation of deterministic machines. A Turing machine can’t ever compute anything about it’s own output; third order logic might allow deterministic machines which can compute the results of their own output.
I suspect that there is a halting problem where the halting status of machines which only use second order logic cannot be computed in third order logic, just like limits cannot be computed in Peano arithmetic.