How could you recognize a halting oracle if you saw one?
Sure, so (ignoring physical limitations) your machine will notice whenever its input is NOT an infinite string of 1s.
-
-
so what I'm saying is that with a suitable translation, there are physical things that represent TMs
-
or computable bit strings. But I don't know how to represent a halting oracle as anything meaningful
-
How about a TM that runs all TMs and writes 1 on nth output bit when nth TM halts? Halting oracle is limit of output tape.
-
I'll have to think about whether that satisfies. I'm not sure whether the fact that this TM doesn't show that anything...
-
doesn't halt is a problem
-
Of course, this only works for Delta^0_2. The arithmetical hierarchy goes a lot higher.
-
after thinking, my main problem with your suggestions is that they are two different mathematical objects...
-
you can't replace one with the other in proofs, though maybe you'd be able to adapt the proofs
- 4 more replies
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.