How could you recognize a halting oracle if you saw one?
-
-
what even is a halting oracle then if we can't in principle experience one? They seem to be formally useful...
-
in particular, there is Post's theorem, and sentences with more than one type of quantifier seem meaningful
-
There is a vast difference between meaningful and computable.
-
And keep in mind that you asked how to perform an unreasonably difficult task.
-
How could you recognize an infinite string of "1"s if you saw one? You can't, because there could always be a 0 later.
-
I can give you an algorithm that describes that sequence.
-
I can point to physical machines and say that these compute the same thing as this Turing machine up to a certain size input
-
and that if you keep expanding its memory, it will only diverge from the TM for physical reasons, not formal ones
- 1 more reply
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.