I have very high confidence that the following question will not make your imagination explode. However, if you are at all worried about that, please stop reading.
What do you imagine the magic box will do if you feed it the algorithm: “Feed this algorithm to the magic box. If it says it halts, then go into an infinite loop. If it says it doesn’t halt, then halt.”
If you presuppose that the universe is not “mathematically possible”, you can’t really prove that it is possible for anyone to ask it that question. For that matter, it might just say “it halts” and be right. (It’s a mathematically impossible world, and you’re using math both when you’re deciding what the algorithm will do and what the box should answer.)
By the way, the usual statement for the halting problem is that you can’t make an algorithm that solves it, and by algorithm it usually means something a Turing machine, i.e. everything the algorithm does can be done by a Turing machine. In this case, assuming it makes sense to use math to reason about it, “Feed this algorithm to the magic box” is not actually something a Turing machine can do (it only has heads and tapes, no magic boxes). If you also give it the magic box it’s no longer just a Turing machine, it’s a [Turing machine + Turing oracle], which is something a bit different.
Imagine the magic box accepts algorithms expressed in Lisp (which theoretically allows unlimited memory). How do you express “feed something to the magic box” in Lisp?
By the way, does anyone know if it’s proven impossible (or even if discussed) to build a limited halting-problem solving algorithm that works for all algorithms except those that contain (complete or limited) halting solver algorithms as subroutines, in which case they also halt but say something like “don’t be an ass”?
Maybe we have different definitions for the term imagine. As far as I’m concerned, by describing your question you imagined it. If you are worried about it being logically inconsistent in this particular universe, imagine a universe where an algorithm’s halting behavior changes after it’s been fed through the magic box in question. My universe—my rules. Or lack thereof.
I think we have different definitions of the term “consistency”. If you define it as “lack of contradiction in the classical first-order logic”, then sure, but why be so restrictive?
Doesn’t that just mean your imagination is self-contradictory?
In what sense? It does not make me go mad or anything, it’s just one of the many programs my brain runs.
I have very high confidence that the following question will not make your imagination explode. However, if you are at all worried about that, please stop reading.
What do you imagine the magic box will do if you feed it the algorithm: “Feed this algorithm to the magic box. If it says it halts, then go into an infinite loop. If it says it doesn’t halt, then halt.”
If you presuppose that the universe is not “mathematically possible”, you can’t really prove that it is possible for anyone to ask it that question. For that matter, it might just say “it halts” and be right. (It’s a mathematically impossible world, and you’re using math both when you’re deciding what the algorithm will do and what the box should answer.)
By the way, the usual statement for the halting problem is that you can’t make an algorithm that solves it, and by algorithm it usually means something a Turing machine, i.e. everything the algorithm does can be done by a Turing machine. In this case, assuming it makes sense to use math to reason about it, “Feed this algorithm to the magic box” is not actually something a Turing machine can do (it only has heads and tapes, no magic boxes). If you also give it the magic box it’s no longer just a Turing machine, it’s a [Turing machine + Turing oracle], which is something a bit different.
Imagine the magic box accepts algorithms expressed in Lisp (which theoretically allows unlimited memory). How do you express “feed something to the magic box” in Lisp?
By the way, does anyone know if it’s proven impossible (or even if discussed) to build a limited halting-problem solving algorithm that works for all algorithms except those that contain (complete or limited) halting solver algorithms as subroutines, in which case they also halt but say something like “don’t be an ass”?
And your point is?
Well, either your magic box can’t cope with algorithms that talk about the magic box itself, or there’s a contradiction going on.
And what’s so bad about that?
Nothing’s bad about it, but I don’t think you can actually imagine the thing you said you could!
Maybe we have different definitions for the term imagine. As far as I’m concerned, by describing your question you imagined it. If you are worried about it being logically inconsistent in this particular universe, imagine a universe where an algorithm’s halting behavior changes after it’s been fed through the magic box in question. My universe—my rules. Or lack thereof.
Okay, at this point I think we have different definitions for “universe”. The one you’re describing can’t be consistently described.
I think we have different definitions of the term “consistency”. If you define it as “lack of contradiction in the classical first-order logic”, then sure, but why be so restrictive?