Activity for user53100
Type | On... | Excerpt | Status | Date |
---|---|---|---|---|
Question | — |
Computational hardness of the uniform halting problem How hard is the decision-problem of a plain Turing Machine halting on all inputs? I'm not sure of the terminology, but by "hard" I mean its location on the arithmetical hierarchy. It can be seen that a TM with a Halt-0 oracle (an oracle that can determine whether a plain TM halts) can co-decide th... (more) |
— | over 3 years ago |