4 ms·
> It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity. There is, isn't there? A TM plus an oracle can so
by Sharlin 5y ago
> It’s almost as if there’s “sizes” of uncomputability much the same as there are distinct sizes of infinity.
There is, isn't there? A TM plus an oracle can solve the halting problem for the original TM but is just as susceptible to a halting problem of its own, and this goes on ad infinitum.